dorsal/arxiv
View SchemaOne-way Functions In Reversible Computations
| Authors | H. F. Chau, H. -K. Lo |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/9506012 |
| URL | https://arxiv.org/abs/quant-ph/9506012 |
Abstract
One-way functions are used in modern cryto-systems as doortraps because their inverse functions are supposed to be difficult to compute. Nonetheless with the discovery of reversible computation, it seems that one may break a one-way function by running a reversible computer backward. Here, we argue that reversible computation alone poses no threat to the existence of one-way functions because of the generation of ``garbage bits'' during computations. Consequently, we prove a necessary and sufficient condition for a one-to-one function to be a one-way in terms of the growth rate of the total number of possible garbage bit configurations with the input size.
{
"annotation_id": "e4e66751-3efc-4252-bdc0-77d3d61f8cc2",
"date_created": "2026-03-02T18:02:38.023000Z",
"date_modified": "2026-03-02T18:02:38.023000Z",
"file_hash": "6e55dcfba0d417b19247e564f44f099db22faaecc9193cd00d22b2658f5b7397",
"private": false,
"record": {
"abstract": "One-way functions are used in modern cryto-systems as doortraps because their\ninverse functions are supposed to be difficult to compute. Nonetheless with the\ndiscovery of reversible computation, it seems that one may break a one-way\nfunction by running a reversible computer backward. Here, we argue that\nreversible computation alone poses no threat to the existence of one-way\nfunctions because of the generation of ``garbage bits\u0027\u0027 during computations.\nConsequently, we prove a necessary and sufficient condition for a one-to-one\nfunction to be a one-way in terms of the growth rate of the total number of\npossible garbage bit configurations with the input size.",
"arxiv_id": "quant-ph/9506012",
"authors": [
"H. F. Chau",
"H. -K. Lo"
],
"categories": [
"quant-ph"
],
"title": "One-way Functions In Reversible Computations",
"url": "https://arxiv.org/abs/quant-ph/9506012"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "8367affa-f668-42e9-a7b8-ce6c9ec1a830",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}