Code-based cryptosystems are a promising option for Post-Quantum Cryptography (PQC), as neither classical nor quantum algorithms provide polynomial time solvers for their underlying hard problem. Indeed, to provide sound alternatives to lattice-based cryptosystems, NIST advanced all round 3 code-based cryptosystems to round 4 of its Post-Quantum standardization initiative. We present a complete implementation of a quantum circuit based on the Information Set Decoding (ISD) strategy, the best known one against code-based cryptosystems, providing quantitative measures for the security margin achieved with respect to the quantum-accelerated key recovery on AES, targeting both the current state-of-the-art approach and the NIST estimates. Our work improves the state-of-the-art, reducing the circuit depth by 219 to 230 for all the parameters of the NIST selected cryptosystems, mainly due to an improved quantum Gauss-Jordan elimination circuit with respect to previous proposals. We show how our Prange’s based quantum ISD circuit reduces the security margin with respect to its classical counterpart. Finally, we address the concern brought forward in the latest NIST report on the parameters choice for the McEliece cryptosystem, showing that its parameter choice yields a computational effort slightly below the required target level.
@article{perriello2023ImprovingEfficiencyQuantum,author={Perriello, Simone and Barenghi, Alessandro and Pelosi, Gerardo},title={Improving the Efficiency of Quantum Circuits for Information Set Decoding},year={2023},publisher={Association for Computing Machinery},address={New York, NY, USA},issn={2643-6809},url={https://doi.org/10.1145/3607256},doi={10.1145/3607256},journal={ACM Transactions on Quantum Computing},month=jul,}
conference and workshop papers
2025
Conference Articles
C6
Quantum Circuit Design for Finding k-Cliques via Quantum Amplitude Amplification Strategies
Simone
Perriello
In Proceedings of the 22nd ACM International Conference on Computing
Frontiers, CF 2025, Cagliari, Italy, May 28-30, 2025, Jul 2025
The k-clique problem, which involves identifying complete subgraphs of size k within a graph, is a fundamental challenge in combinatorial optimization with applications in network analysis, bioinformatics, and cryptography. As the number of nodes n grows, classical algorithms become computationally intractable, motivating the exploration of quantum computing to address these limitations. This work introduces two quantum algorithms for solving the k-clique problem: one based on Quantum Amplitude Amplification (QAA) and another leveraging Quantum Walks (QW) over the Johnson graph J(n, k). By exploiting the regular structure of the Johnson graph, the QW approach achieves the same quadratic speedup of the QAA approach over classical algorithms, while remaining applicable to arbitrary undirected, unweighted graphs. We provide detailed quantum circuit designs for both approaches, analyzing their performance in terms of qubit count, gate count, and circuit depth under the NOT-CNOT-Toffoli + arbitrary rotations and Clifford + T gate sets. Compared to state-of-the-art quantum algorithms, our methods achieve significant improvements in scaling, particularly for dense graphs, with speedups ranging from 2^5 to 2^20.
@inproceedings{DBLP:sp_cf25_tmp,author={Perriello, Simone},title={Quantum Circuit Design for Finding k-Cliques via Quantum Amplitude Amplification Strategies},booktitle={Proceedings of the 22nd {ACM} International Conference