Return to Answer

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

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.

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 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 my quarter-baked AES-128 replacement with easy implementation as Toffoli 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 that would be for DES.

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

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 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 my quarter-baked AES-128 replacement with easy implementation as Toffoli 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.

For some algorithms, making things easily reversible would be a huge design change, likely to compromise security. That applies in particular to many Feistel block ciphers using large non-reversible round function, which I guess are quite hard to re-express as reversible. I asked how costly that would be for DES.

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 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 my quarter-baked AES-128 replacement with easy implementation as Toffoli 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 that would be for DES.