4
$\begingroup$

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.

$\endgroup$
  • 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$ – Joseph Van Name Feb 15 '18 at 23:04
  • $\begingroup$ @35093731895230467514051: many thanks for the reference bringing some rigor to my hand-waving. $\endgroup$ – fgrieu Feb 16 '18 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 '18 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 '18 at 11:36
  • $\begingroup$ cs.cornell.edu/~vishal/papers/dtis_2013.pdf This link does not exist $\endgroup$ – pushpen.paul Dec 11 '18 at 12:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.