Return to Question

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
    • if not in the last round
      • 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 1488 C-NOT for the rest. 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.

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

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.

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.

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
    • if not in the last round
      • 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 1488 C-NOT for the rest. 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.

How many Toffoli or Controlled NOT gates 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 with non trivial key width, the function $(K,P)\mapsto(G,C)$ with $G$ the same width as $K$ can be implemented reversibly using Toffoli and C-NOT gates (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.

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.