How many reversible gates (said counting Toffoli and Controlled NOT, with free NOT) would be required to reversibly implement $(K,P)\mapsto(G,C)$ for the block cipher DES?
$P$ is the plaintext, $C$ the ciphertext, both 64-bit; $K$ is the 56-bit key; $G$ is any 56-bit "garbage".
For any block cipher, the function $(K,P)\mapsto(G,C)$ with $G$ the same width as $K$ can be implemented reversibly (rigorous proof and/or straightening welcome).
For AES, this was studied:
- 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)$ 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.
Towards an answer: an expression of DES's $(K,P)\mapsto(G,C)$ using reversible operations is
- a sequence of 16 rounds, each
- repeating, for each of 8 S-boxes
- temporarily XORing 6 keys bits with 6 bits of the 64-bit block
- for each of 4 other bits of the 64-bit block
- XORing that bit with some function of the 6 (modified) key bits
- restore the 6 key bits by XORing with the same 6 bits
- repeating, for each of 8 S-boxes
The center operation is executed 512 times, and certainly represents most of the gates. There are 1480 C-NOT for the rest (accounting for the fact that the last restore of each key bit can be skipped). The 4 functions of the same 6 bits in the center loop are neither quite independent nor arbitrary. I know several minimization attempts for these, but none using reversible gates.
