This document accompanies the paper submitted to QCE 2024 named

A Quantum Circuit to Execute a Key-Recovery Attack Against the DES and 3DES Block Ciphers (S. Perriello, A. Barenghi, G. Pelosi)

and provides installation notes, usage instructions, and references to the associated code repository.

Overview of the paper

The paper [PBP24] presents the full design and implementation of quantum circuits to attack the symmetric encryption schemes DES and 3DES (including all its variants) using Grover’s quantum amplitude amplification framework. It evaluates the cost of such attacks by employing fully reversible circuits that do not rely on Quantum Random Access Memory (QRAM), and additionally provides metrics for a meet-in-the-middle attack on variant 2 of 3DES that does rely on QRAM.

The work reports detailed complexity metrics, including the number of gates, circuit depth, and number of qubits required for each design. It also introduces aggregate metrics obtained by multiplying the number of gates by the circuit depth, and the number of qubits by the circuit depth, providing a more comprehensive view of the trade-offs between space and time resources. All metrics are provided for both a reversible quantum gate set augmented with the Hadamard gate (NCT + H) and a fault-tolerant universal gate set (Clifford + T).

This supplementary repository contains the reversible implementations of the DES S-boxes, which represent the only non-trivial component of the DES encryption routine. While all other parts of the DES encryption and decryption processes can be implemented straightforwardly using simple depth-1 layers of CNOT gates to emulate XOR operations and depth-0 qubit relabeling to represent permutations and shifts, the S-boxes require non-linear access to a lookup table. To obtain reversible versions of these boxes, the implementation relies on the bitslice construction proposed by Kwan in [Kwan00].

In addition to the S-box implementations, the repository includes the code used to generate the complexity metrics reported in the paper, allowing full reproducibility of the results presented in [PBP24].

Installation

All the provided code has been implemented and tested using Python 3.12. To run the provided code, please install the myQLM library, freely available at https://myqlm.github.io/.

Once installed, clone the repository from github https://github.com/paper-codes/2024-QCE

git clone https://github.com/paper-codes/2024-QCE

Tests

All quantum routine tests can be executed using:

REVERSIBLE_ON=1 pytest -s

This command runs the full suite of tests validating the quantum implementation of the S-boxes. Specifically, they compare the output of the classical (non-reversible) DES S-box implementation, and the reversible quantum-circuit implementation.

Both implementations are tested across all possible inputs to assert identical output behavior.

A reversible simulator is used to perform these computations efficiently, avoiding the significant memory overhead typically associated with quantum simulation.

Example Usage

Running the following command

python -m examples.kwan_des_sboxes

will produce two different outputs. The first output refers to the complexity metrics of all the S-boxes, for both the parallel variant (low-depth in [PBP24]) and sequential variant (low-width in [PBP24]).

S-boxes parallel measures
***********************************************************************
{'W': 496, 'G': {'custom gate': 0, 'CNOT': 443, 'X': 560, 'C-C-X': 214},
'D': 62, 'D-CCNOT': 19.0}
***********************************************************************
S-boxes sequential measures
***********************************************************************
{'W': 114, 'G': {'custom gate': 0, 'CNOT': 443, 'X': 560, 'C-C-X': 214},
'D': 248, 'D-CCNOT': 81.0}
***********************************************************************

The second output refers to the complexity metric of the whole circuit to attack DES and all 3DES variants, compared to AES-128, Camellia-128, SEED and HIGHT. The result is presented in latex table format.

The results of such metrics are presented in Tables I and II of the paper [PBP24].

# Bibliography [Kwan00] Matthew Kwan: Reducing the Gate Count of Bitslice DES. IACR Cryptol. ePrint Arch. 2000: 51 (2000)

[PBP24] Simone Perriello, Alessandro Barenghi, Gerardo Pelosi: A Quantum Circuit to Execute a Key-Recovery Attack Against the DES and 3DES Block Ciphers. QCE 2024: 1-12

BibTex of [PBP24]

Please find below the bibtex associated to [PBP24] for your convenience.

@inproceedings{DBLP:conf/qce/PerrielloBP24,
  author       = {Simone Perriello and
                  Alessandro Barenghi and
                  Gerardo Pelosi},
  editor       = {Marek Osinski and
                  Brian La Cour and
                  Lia Yeh},
  title        = {A Quantum Circuit to Execute a Key-Recovery
                  Attack Against the {DES}
                  and 3DES Block Ciphers},
  booktitle    = {{IEEE} International Conference on Quantum
                   Computing and Engineering,
                  {QCE} 2024, Montreal, QC, Canada,
                  September 15-20, 2024},
  pages        = {1--12},
  publisher    = {{IEEE}},
  year         = {2024},
  url          = {https://doi.org/10.1109/QCE60285.2024.00011},
  doi          = {10.1109/QCE60285.2024.00011},
}