Does cryptography have an inherent thermodynamic cost?

Question

Reversible computing is a computational model that only allows thermodynamically reversible operations. According to Landauer's principle, which states that erasing a bit of information releases $kT \ln(2)$ joules of heat, this rules out transition functions that are not one-to-one (e.g., the Boolean AND and OR operators). It is well known that quantum computation is inherently reversible because the allowed operations in quantum computation are represented by unitary matrices.

This question is about cryptography. Informally, the notion of "reversibility" seems anathema to the fundamental goals of cryptography, thus suggesting the question: "Does cryptography have an inherent thermodynamic cost?"

I believe that this is a different question than, "Can everything be done in quantum?"

In his lecture notes, Dr. Preskill states, "There is a general strategy for simulating an irreversible computation on a reversible computer. Each irreversible gate can be simulated by a Toffoli gate by fixing inputs and ignoring outputs. We accumulate and save all 'garbage' output bits that are needed to reverse the steps of the computation."

This suggests that these reversible quantum simulations of irreversible operations take an input as well as some "scratch" space. Then, the operation generates output along with some "dirty" scratch bits. The operations are all reversible with respect to the output plus garbage bits, but at some point, the garbage bits are "thrown away" and not considered further.

Since cryptography depends on the existence of trapdoor one-way functions, an alternative statement of the question might be, "Are there any trapdoor one-way functions that can be implemented using only reversible logical operations, without additional scratch space?" If so, is it also possible to COMPUTE an arbitrary trapdoor one-way function using only reversible operations (and no scratch space)?

Answer 1

As I mentioned in my comment above, and as you allude to in the question, every computation can be made reversible, and by simply retaining the extra bits, there is no inherent thermodynamic cost.

Every circuit generated by using Toffoli gates and ancillas to replace irreversible gates becomes as efficient to reverse as it is to compute assuming you have access to all output bits. This is clearly not the case for the functions considered in cryptography, since many ancillae are used and discarded. It is by keeping secret this extra bits that makes the computation hard to reverse.

However, by computing the function reversibly, making a copy of the subset of bits corresponding to the output, and then inverting the function the total energy cost for computing and inverting the function will be zero, while the only cost incurred will be in making the copy of the output bits, which depends only on the number of output bits and not the function being computed. This is clearly the best you can do, since it costs the same energy as simply writing the output string to an empty register.

Turning to your restated question:

"Are there any trapdoor one-way functions that can be implemented using only reversible logical operations, without additional scratch space?"

The answer is trivially no. If you apply the inverse of each gate in reverse order you compute the inverse of the function. Assuming a model where gates act on a fixed number of qubits at a time, then the inverse of each elementary reversible gate can be applied in constant time. Hence such a function is as easy to invert as to compute (up to a multiplicative constant), and hence is not a trapdoor function.