Computationally asymmetric transformations and reversible logic circuits
The concept of one-way function is crucial to the modern cryptography. However, there are no rigorousproofs of the existence or even the possibility of constructing such functions at the moment. In this paper weconsider one approach that allows to look in a new way at the phenomenon of one-wayness. The essence ofthis approach is to use reversible circuits to implement computationally asymmetric transformations. Weconsider reversible circuits implementing linear and nonlinear asymmetric transformations, binary addition/subtraction, multiplication/division in the field of polynomials of characteristic 2. We show that the difference in the complexity of the direct and inverse transformations in some cases is linked to the difference inthe complexity of the sub-circuits, cleaning the computational garbage. Basing on the considered reversiblecircuits, we make an assumption about the structure of the computationally asymmetric transformations.