One-way Functions In Reversible Computations
Abstract
Description
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.
In REVTEX 3.0, with one figure. Minor changes. To appear in Cryptologia
In REVTEX 3.0, with one figure. Minor changes. To appear in Cryptologia