How many reversible gates (said counting [Toffoli][1] and [Controlled NOT][2], with free NOT) would be required to reversibly implement $(K,P)\mapsto(G,C)$ for the block cipher [DES][3]?

$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_][4], in [proceedings of DTIS 2013][5]. 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_][6], in [proceedings of PQCrypto 2016][7], 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.

  [1]: https://en.wikipedia.org/wiki/Toffoli_gate
  [2]: https://en.wikipedia.org/wiki/Controlled_NOT_gate
  [3]: https://en.wikipedia.org/wiki/Data_Encryption_Standard#Description
  [4]: https://www.cs.cornell.edu/~vishal/papers/dtis_2013.pdf
  [5]: https://doi.org/10.1109/DTIS.2013.6527794
  [6]: https://arxiv.org/pdf/1512.04965.pdf#page=9
  [7]: https://doi.org/10.1007/978-3-319-29360-8_3