Single-query Quantum Hidden Shift Attacks

This is the code of the paper "Single-query Quantum Hidden Shift Attacks"
(Xavier Bonnetain & André Schrottenloher) available here
and published in ToSC 2024 issue 3.

Requirements

• Python 3.10.11 to run the script success_probability_optimization.py
• sympy 1.2.1 to run the script equations.py

This code is likely to be compatible with more versions, although we haven't tested this.

Contents

• equations.py : Uses basic symbolic computations in Sympy to print formulas
  for the output ciphertexts in Rocca, Rocca-S, Tiaoxin and AEGIS (the designs
  that were studied in the paper), depending on the input message blocks and the
  state words.

• success_probability_optimization.py : Finds the values of G and M, and the
  associated probabilities of success p and p', for the different attacks detailed
  in Section 4 of the paper.

How to run

• To generate the formulas for 3 rounds of Rocca-S and AEGIS-128 as readable text in the terminal,
  run:

  python3 equations.py -r 3 rocca-S aegis-128

  The starting state blocks are denoted S[i] (T_i[j] for Tiaoxin), with
  the same notations as in the paper. For the case of AEGIS-128L, note that the
  formulas of the paper use the state T which is the state after one round, while
  the formulas displayed here depend on S which is the starting state.

• To generate the formulas for 3 rounds of all designs in a single LateX document,
  run:

  python3 equations.py -alr 3 >> document.tex

  This will create document.tex which should then be compiled with pdflatex,
  though the equations will be too large for the page width.

• To obtain the parameters (G, M, p, p', in log_2) of the query-optimal attack
  on Rocca (Section 4.1), run:

  python3 success_probability_optimization.py rocca-queries

  Here the output 'cost' will be the total probability of success (p times p').

• To obtain the parameters (G, M, p, p') of the time-optimal attack on Rocca
  (Section 4.2, see Eq. (21)), run:

  python3 success_probability_optimization.py rocca-time

  Here the output 'cost' will be a number of Toffoli gates.

• To obtain the parameters (G, M, p, p') of the time-optimal attack on Rocca-S
  (Section 4.3, see Eq. (26)), run:

  python3 success_probability_optimization.py rocca-S-time

  Here the output 'cost' will be a number of Toffoli gates.

• To obtain the parameters (G, M, p, p') of the attack on AEGIS-128L
  (Section 4.5, see Eq. (29)), run:

  python3 success_probability_optimization.py aegis-128L

  Here the output 'cost' will be a number of Toffoli gates.

Acknowledgments

This work has been partially supported by the French Agence Nationale de la Recherche
through the OREO project under Contract ANR-22-CE39-0015, and through the France
2030 program under grant agreement No. ANR-22-PETQ-0007 EPiQ and ANR-22-PETQ-0008 PQ-TLS.