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 with non-trivial key width, 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)$.
With that conception of reversible cipher allowing to discard garbage the width of the key, I tentatively answer:
- Yes. My quarter-baked AES-128 replacement designed for easy implementation as Toffoli 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 for mainstream algorithms. Algorithms with a clear design tend to either be clearly reversible, or purposely use transformations that seem hard, perhaps in practice impossible to reverse; in the later case, making things reversible would be a huge design change, likely to compromise security. That applies in particular to many Feistel block ciphers using non-reversible round function, which I guess are quite hard to re-express as reversible. I asked how costly that would be for DES.