Colloquia 2022: Breakthrough in Quantum Cryptanalysis of Code-Based Cryptosystems 🔐

Concrete Quantum Cryptanalysis of Code-Based Cryptosystems
Simone Perriello

Code-based cryptosystems are among the most promising candidates for Post-Quantum Cryptography, as witnessed by NIST decision to advance all the code-based proposals to the last round of its Post-Quantum standardization initiative. By adapting Grover’s framework, we designed concrete quantum circuits to attack such cryptoschemes, providing the first quantitative analysis of the required computational complexity. The proposed circuits solve a general combinatorial problem, since the problem addressed can be seen as a binary constraint satisfaction problem. In the process, we developed quantum circuits to permute matrix columns, to compute the Hamming weight of a given bitvector, and to perform Gauss-Jordan Elimination on a matrix.