Which symmetric encryption systems, pseudorandom number generators, and hash functions are best suited for reversible computers? Reversible computing refers to the type of computing where one minimizes the the amount of data to be deleted usually to save energy (Reversible computing could also thwart side-channel attacks). Energy efficient reversible computers do not exist yet in the free market although some have constructed prototypes and they should become the computers of the future.  In reversible computing, the AND and OR gates are forbidden since they delete data (the AND gate has 2 inputs but 1 output so one bit is necessarily deleted). 

With purely reversible computing, only the bijective logic gates are allowed for computation since non-bijective gates delete information. For example, the CNOT $(x,y)\mapsto(x,x\oplus y)$, Toffoli $(x,y,z)\mapsto(x,y,(x\wedge y)\oplus z)$, and Fredkin
$(0,y,z)\mapsto(0,y,z),(1,y,z)\mapsto(1,z,y)$ gates are all reversible gates.

While reversible computing theoretically should save energy, it typically takes more steps to compute something reversibly than it does to perform the same computation irreversibly. However, in symmetric cryptography, one could potentially design cryptosystems such as encryption systems, hash functions, (cryptographic and non-cryptographic) pseudorandom number generators which do not contain any such algorithmic overhead (the only irreversibility that is required in a cryptographic hash function is that unless one wants to keep the hash around forever, one must eventually delete the hash).

1) Are there any symmetric cryptosystems which are specifically designed to be used by reversible computers? 

2) Are there any symmetric cryptosystems which were not necessarily designed to be used by reversible computers but which just-so-happen to be reversible? 

3) Are there any symmetric cryptosystems which are nearly reversible and which can potentially be modified slightly to become reversible?

Here are some characteristics that one would like in reversible cryptosystem.

-The cryptosystem should ideally be computed using solely reversible gates without any garbage bits, ancilla bits, uncomputation, or irreversible gates.

-The inverses of all parts included in the cryptosystem should be computed in exactly the same way as the forward direction (for example, the inverse $\chi$ in Keccak is computed differently than the forward direction; $\chi$ has algebraic degree 2 while the inverse of $\chi$ has algebraic degree 3 (see page 16 of these slides)).

-The cryptosystem must not require any uncomputing. Uncomputing is an overhead that arises in reversible computing even though irreversible computing does not require any uncomputing.

-The cryptosystem should not use any lookup tables.

-The cryptosystem should not use modular multiplication, finite field multiplication, or finite field inversion at all these operations require uncomputing.
We can think of encryption as a deterministic function producing ciphertext $C$ from key $K$, plaintext $P$, and for other than deterministic encryption an extra input $R$ for randomness/Initialization Vector. That function $(K,R,P)\mapsto C$ can't be both secure and reversible. Proof: it would be possible to obtain $(K,R,P)$ from $C$ because of reversibility, and from that extract $P$, which goes straight against the security goal.

The same reasoning shows that a fully reversible TRNG can't be secure, or a fully reversible hash function first-preimage resistant.



However, we can implement all steps reversibly, except discarding some of the final result. In particular, for any size-preserving symmetric cipher, in principle we can reversibly implement $(K,R,P)\mapsto(G,C)$, with garbage $G$ the same width as $K$ (and $C$ the same width as $R$ and $P$ combined), and discard $G$ from the output. For a block cipher, that is $(K,P)\mapsto(G,C)$ (proof and/or straightening welcome; Scott Aaronson, Daniel Grier, Luke Schaeffer's The Classification of Reversible Bit Operations would be a useful reference).

With that conception of reversible cipher allowing to discard garbage the width of the key, I tentatively answer:


Yes, if your AES-128 replacement with easy implementation as Toffoli-like gates qualifies.
Yes. The AES block cipher is a well-studied example, and all its standard modes qualify. For the reversible construction of AES-128, see


Kamalika Datta, Vishal Shrivastav, Indranil Sengupta, Hafizur Rahaman's Reversible Logic Implementation of AES Algorithm, in proceedings of DTIS 2013. My reading is that it reports implementing $(K,P)\mapsto(G,C)$ for AES-128 using less than $2^{17}$ Toffoli gates.
Markus Grassl, Brandon Langenberg, Martin Roetteler, Rainer Steinwandt's Applying Grover’s Algorithm to AES: Quantum Resource Estimates, in proceedings of PQCrypto 2016, seem just over $2^{20}$ Toffoli gates using a different approach.

Rather no. Making things easily reversible when they are not would be a huge design change, likely to compromise security. That applies in particular to Feistel block ciphers using large non-reversible round functions, which I guess are quite hard to re-express as reversible.


I asked how costly DES would be.