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.

  • 1
    $\begingroup$ 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). $\endgroup$ Feb 15, 2018 at 23:04
  • $\begingroup$ @35093731895230467514051: many thanks for the reference bringing some rigor to my hand-waving. $\endgroup$
    – fgrieu
    Feb 16, 2018 at 6:57
  • $\begingroup$ 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). $\endgroup$
    – user1430
    Feb 16, 2018 at 19:12
  • $\begingroup$ @user1430: but NAND is not reversible. Thus the minimizations obtained with NAND are not directly usable (hence the question's last phrase). $\endgroup$
    – fgrieu
    Feb 20, 2018 at 11:36
  • $\begingroup$ cs.cornell.edu/~vishal/papers/dtis_2013.pdf This link does not exist $\endgroup$
    – hola
    Dec 11, 2018 at 12:27


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.