I have to remind all of you that NIST has butchered cryptographic functions such as SHA-256 and AES by standardizing low quality irreversible cryptographic functions rather than the reversible ones (or partially reversible in the case of SHA-256). I have to give NIST a grade of F- for this egregious oversight.
Correct me if I am wrong, but AES, being a symmetric encryption function, is reversible by design.
-Invertibility and reversibility are not exactly the same thing. Reversibility means that the optimal algorithm for computing such a function is an algorithm where there is no computational complexity overhead that results from using a reversible computer rather than an irreversible computer. There are many functions that are invertible but which I would not want to compute on a reversible computer. I can give of many examples of invertible functions that are not reversibility friendly.
Example 1: Consider the operation x->Ax where A is an invertible matrix on a finite field. This operation is invertible, but it is much easier to compute the original function than its inverse since the inverse may be way more complicated than the original function. SHA-256 uses invertible matrices where the inverse is much more complicated than the original function. This means that SHA-256 is not reversibility friendly.
Example 2: Let f be a function where f(a) is always an invertible matrix over a finite field. Then the operation (a,x)->(a,f(a)x) is always invertible, but the inverse operation
(a,x)->(a,f(a)^(-1)x) may be much harder to compute than the original function. The problem of finding an inverse of an n by n matrix takes O(n^3) steps using Gauss-Jordan elimination. There are some faster algorithms for matrix inversion such as the Strassen algorithm, but there are no O(n^2.001) algorithms for matrix inversion that we know about.
Example 3: Let q be an integer. Let a<q, and suppose gcd(a,q)=1. Consider the operation from the ring Z_q to Z_q given by z->a*z. This operation is invertible, but the inverse may be more complicated than the original function. For example, if q=2^32 and a=3, then the operation z->a*z is much easier to compute than its inverse.
Example 4: If f is an arbitrary function, then the mapping (x,y)->(x,y XOR f(x)) is invertible, but this function is not reversibility friendly. For example, when transforming x to f(x) on a reversible computer, one typically produces garbage information G(x). On a reversible computer, one will need to do the following to compute our function:
(x,y)->(G(x),f(x),y)->(G(x),f(x),y XOR f(x))->(x,y XOR f(x)). This construction is used in Feistel ciphers in cryptography. This means that while Feistel ciphers are useful for cryptography, they are not reversibility friendly.
Example 5: One way permutations are permutations f where x->f(x) can be computed in a reasonable amount of time but where the inversion f(x)->x has no known polynomial time algorithm. This means that the inversion f(x)->x cannot be computed in practice. This kind of function is not reversibility friendly.
Example 6: In the mix-columns step in AES, to encrypt, we perform the transformation f(x)->a(x)f(x) mod x^4+1 where f(x) is a degree 3 polynomial over the field with 256 elements and a(x) is a fixed polynomial for AES. Here, the developers of the AES chose a(x) so that the coefficients of a(x) and a(x)^(-1) are both simple. This means that f(x)->a(x)f(x) mod x^4+1 and f(x)->a(x)^(-1)f(x) mod x^4+1 are both relatively easy to compute. The problem is that we do not simply compute f(x)->a(x)^(-1)f(x) mod x^4+1 by running f(x)->a(x)f(x) mod x^4+1 in reverse. This means that a reversible computer must have some computational complexity overhead when performing the MixColumns step of AES encryption.
I remember that someone asked for the energy efficiency of biological processes. And the energy efficiency of transcription of DNA into RNA is lower than Landauers limit. Here is an excerpt from Charles Bennett's 1989 paper on time/space tradeoffs in reversible computation "However, a few thermodynamically efficient data processing systems do exist, notably genetic enzymes such as RNA polymerase, which, under appropriate reactant concentrations, can transcribe information from DNA to RNA at a thermodynamic cost considerably less than kT per step."
-Joseph Van Name Ph.D.
