Skip to main content
2 of 11
Polish
fgrieu
  • 145.4k
  • 12
  • 319
  • 611

We can think of encryption as a deterministic function producing ciphertext $C$ from plaintext $P$, key $K$, and for other than deterministic encryption an extra input $R$ for randomness/Initialization Vector. That function $(P,K,R)\mapsto C$ can't be both secure and reversible. Proof: it would be possible to obtain $(P,K,R)$ 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.


For some crypto algorithms, we can however implement all steps reversibly, except discarding some of the final result. In particular, for some existing ciphers, we can reasonably implement $(P,K,R)\mapsto(C,K,R)$ reversibly, then discard $K$ and $R$ from the output. That's possible for the common modern block cipher AES-128, with in the order $2^{17}$ Toffoli gates: 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 implements $(P,K)\mapsto(C,K')$ where all variables are 128 bits, and the transformation $K\mapsto K'$ is reversible and requires only a fraction of the gates.

With a conception of reversible cryptography allowing to remove some of the final outputs, limited to how many bits of key there was:

  1. Yes. My quarter-baked AES-128 replacement designed for easy implementation as Toffoli gates qualifies.
  2. Yes. The AES block cipher is a well-studied example, and if we accept to discard key and IV, and restrict to plaintext multiple of 128-bit, all its standard modes qualify.
  3. Rather no for mainstream algorithms. Algorithms with a clear design tend to either be clearly reversible, or purposely use transformations that seem hard, perhaps impossible to reverse; in the later case, making things reversible would be a huge design change, likely to compromise security.

Note: I believe it would be possible to design a secure block cipher with no key scheduling at all; that would allow $(P,K)\mapsto(C,K)$ with bits of $K$ only going thru the unchanged inputs $x$ and $y$ of Toffoli gates.

fgrieu
  • 145.4k
  • 12
  • 319
  • 611