Which symmetric encryption systems, pseudorandom number generators, and hash functions are best suited for reversible computers?

Question

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.

Answer 1

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:

1. Yes, if your AES-128 replacement with easy implementation as Toffoli-like gates qualifies.

2. 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.

3. 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.

Answer 2

It seems like most symmetric cryptosystems could be modified to make completely reversible cryptosystems without the need for garbage or ancilla bits in such a way that the security level is likely to increase rather than decrease.

Reversible computing takes in clean bits of data and returns garbage data which must be cleaned up through the process of uncomputing. However, for the purpose of encryption, it does not make much sense to clean up any garbage data generated since that garbage data provides confusion and diffusion. It also does not make too much sense to insist on using clean 0 bits on the inputs of the ancilla bits because using dirty ancilla bits could also provide confusion and diffusion. Of course, these modifications will change the design of the block cipher, so they will need to be investigated and optimized, but these modifications may increase the security of the block cipher.

Suppose that $S:\{0,1\}^{n}\rightarrow\{0,1\}^{n}$ is an $S$-box or other bijective function used in a symmetric encryption-decryption algorithm.

Suppose now that one has an efficient reversible circuit $C:\{0,1\}^{n}\times\{0,1\}^{m}\rightarrow\{0,1\}^{n}\times\{0,1\}^{m}$ such that $C(\mathbf{x},\mathbf{0})=(S(\mathbf{x}),G(\mathbf{x}))$ (here $G(\mathbf{x})$ is the garbage data that has been produced from computing $S(\mathbf{x})$). Then to make the block cipher reversible, one would replace the $S$-box $\mathbf{x}\mapsto S(\mathbf{x})$ with the function $(\mathbf{x},\mathbf{y})\mapsto C(\mathbf{x},\mathbf{y})$.

Similarly, if $D$ is a reversible circuit such that $D(\mathbf{x},\mathbf{0})=(S^{-1}(\mathbf{x}),H(\mathbf{x}))$, then one could replace the $S$-box $\mathbf{x}\mapsto S(\mathbf{x})$ with the reversible mapping $(\mathbf{x},\mathbf{y})\mapsto D^{-1}(\mathbf{x},\mathbf{y})$.