# How many reversible gates would DES require?

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:

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

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.

• Any bijection of $\{0,1\}^{k}$ can be computed using Toffoli gates as long as you have 3 ancilla bits scottaaronson.com/papers/gates.pdf Theorem 23. If you do not have ancilla bits, then every Toffoli gate is an even permutation, and therefore you can only perform even transformations (Proposition 9). – Joseph Van Name Feb 15 '18 at 23:04
• @35093731895230467514051: many thanks for the reference bringing some rigor to my hand-waving. – fgrieu Feb 16 '18 at 6:57
• DES as a single f(R,K) round's worth of hardware with a state machine sequencer and key scheduler can be implemented in approximately 4700 NAND gate equivalents (reducing AND-ORs for S Boxes, using L, R, C, D and a state register). – user1430 Feb 16 '18 at 19:12
• @user1430: but NAND is not reversible. Thus the minimizations obtained with NAND are not directly usable (hence the question's last phrase). – fgrieu Feb 20 '18 at 11:36
• cs.cornell.edu/~vishal/papers/dtis_2013.pdf This link does not exist – pushpen.paul Dec 11 '18 at 12:27