publications

2024

Conference Articles

1. Quantum Circuit Design for the Lee-Brickell Based Information Set Decoding

   Perriello, Simone, Barenghi, Alessandro, and Pelosi, Gerardo

   Doi: 10.1007/978-3-031-XXXXX-XXX

   In Applied Cryptography and Network Security Workshops - ACNS 2024 Satellite Workshops, ACNS

   Abs Bib HTML

   In the race for quantum-safe cryptography, fostered by the ongoing National Institute of Standards and Technology (NIST) post-quantum standardization process, it is crucial to assess the security of the emerging cryptoschemes. In this work, we propose a fully quantum algorithm to accelerate the Lee-Brickell’s Information Set Decoding (ISD) on binary error correcting codes — one of the main cryptanalytic techniques used for assessing the security of code-based cryptoschemes. Our solution relies on a careful scheduling of the quantum gates included in the circuit design, coupled with a strategy that applies multiple times the oracle-reflection, from a Grover-like search, within a single Grover iteration. Compared with the state-of-the-art alternatives, our solution shows a reduction of the circuit depth ranging between 2^3 and 2^26, when considering the parameters sets for code-based cryptosystems advanced to the fourth round of the NIST process. Denoting as t and t-p the two sets of bit flips tackled by the Lee-Brickell’s strategy, as an additional noteworthy fact we show that our solution exhibits 1 as the best value for p instead of 2 as it is the case for the classic ISD.

   @inproceedings{perriello2024QuantumCircuitDesign,
     title = {Quantum Circuit Design for the Lee-Brickell Based Information Set Decoding},
     booktitle = {Applied {{Cryptography}} and {{Network Security}} Workshops - {{ACNS}} 2024 Satellite Workshops, {{ACNS}}},
     author = {Perriello, Simone and Barenghi, Alessandro and Pelosi, Gerardo},
     date = {2024},
     series = {Lecture Notes in Computer Science},
     pages = {to appear},
     publisher = {{Springer}},
     location = {{Abu Dhabi, UAE}},
     doi = {10.1007/978-3-031-XXXXX-XXX},
   }

2. Design of a Quantum Walk Circuit to Solve the Subset-Sum Problem

   Lancellotti, Giacomo,  Perriello, Simone, Barenghi, Alessandro, and Pelosi, Gerardo

   Doi: 10.1145/3649329.3657337

   In 61st ACM/IEEE Design Automation Conference, DAC 2024, San Francisco, CA, USA, July 23-27, 2024

   Abs Bib

   Search algorithms based on quantum walks have emerged as a promising approach to solve computational problems across various domains, including combinatorial optimization, and cryptography. Stating a generic search problem in terms of a (quantum) search over a graph makes the efficiency of the algorithmic method depend on the structure of the graph itself. In this work, we propose a complete implementation of a quantum walk search on Johnson graphs, speeding up the solution of the subset-sum problem. We provide a detailed design of each sub-circuit, quantifying their cost in terms of gate number, depth, and width. We compare our solution against a Grover quantum search, showing a reduction of the T-count and T-depth for practically solvable problems. The proposed design provides a building block for the construction of efficient quantum search algorithms that can be modelled on Johnson graphs, filling the gap with the existing theoretical complexity analyses.

   @inproceedings{lancellotti2023DesignQuantumWalkConf,
     title = {Design of a Quantum Walk Circuit to Solve the Subset-Sum Problem},
     booktitle = {61st {{ACM}}/{{IEEE}} Design Automation Conference, {{DAC}} 2024, San Francisco, {{CA}}, {{USA}}, July 23-27, 2024},
     author = {Lancellotti, Giacomo and Perriello, Simone and Barenghi, Alessandro and Pelosi, Gerardo},
     date = {2024},
     publisher = {ACM},
     doi = {10.1145/3649329.3657337},
     url = {https://doi.org/10.1109/DAC56929.2023},
   }

2023

Journal Articles

1. Improving the Efficiency of Quantum Circuits for Information Set Decoding

   Perriello, Simone, Barenghi, Alessandro, and Pelosi, Gerardo

   Doi: 10.1145/3607256

   ACM Transactions on Quantum Computing Jul 2023

   Abs Bib HTML Code

   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,
   }

2021

Conference Articles

1. A Complete Quantum Circuit to Solve the Information Set Decoding Problem

   Perriello, Simone, Barenghi, Alessandro, and Pelosi, Gerardo

   Doi: 10.1109/QCE52317.2021.00056

   In IEEE International Conference on Quantum Computing and Engineering, QCE 2021, Broomfield, CO, USA, October 17-22, 2021 Jul 2021

   Abs Bib HTML Code

   Providing strong security margins ag ainst cryptanalytic attackers equipped with quantum computers is a major research direction fostered by the US National Institute of Standards and Technology (NIST) Post-quantum Cryptography Standardization process. Among the viable candidates, code-based asymmetric cryptosystems are one of the prominent approaches. In this work, we propose the first fully detailed quantum circuit to compute the solution to the Information Set Decoding problem, the main cryptanalytic tool against such cryptosystems. We evaluate the cryptanalytic effort with our circuit design on actual parameters from cryptosystems admitted to the final stage of the NIST standardization process and compare it with the previous conservative asymptotic estimates. We show that the actual computational effort of our solution is smaller than the one estimated via asymptotics by a factor of \(2^4\). We also perform a comparison of our results with the quantum-computational effort of breaking the AES cipher, following the guidelines of the US NIST in evaluating the security of the ciphers. To do this, we translate our design on gates of the Clifford+T gate set only, one of the most promising candidate for fault-tolerant quantum computation, and report that the parameter choices for Classic McEliece and BIKE, two candidates admitted to the final round of the NIST standardization process provide an adequate security margin with respect to our ISD solution technique.

   @inproceedings{DBLP:conf/qce/PerrielloBP21,
     title = {A Complete Quantum Circuit to Solve the Information Set Decoding Problem},
     booktitle = {{{IEEE International Conference}} on {{Quantum Computing}} and {{Engineering}}, {{QCE}} 2021, {{Broomfield}}, {{CO}}, {{USA}}, {{October}} 17-22, 2021},
     author = {Perriello, Simone and Barenghi, Alessandro and Pelosi, Gerardo},
     editor = {M{\"u}ller, Hausi A. and Byrd, Greg and Culhane, Candace and Humble, Travis},
     year = {2021},
     pages = {366--377},
     publisher = {{IEEE}},
     doi = {10.1109/QCE52317.2021.00056},
     url = {https://doi.org/10.1109/QCE52317.2021.00056},
     bibsource = {dblp computer science bibliography, https://dblp.org},
     biburl = {https://dblp.org/rec/conf/qce/PerrielloBP21.bib},
   }

2. A Quantum Circuit to Speed-up the Cryptanalysis of Code-Based Cryptosystems

   Perriello, Simone, Barenghi, Alessandro, and Pelosi, Gerardo

   Doi: 10.1007/978-3-030-90022-9_25

   In Security and Privacy in Communication Networks - 17th EAI International Conference, SecureComm 2021, Virtual Event, September 6-9, 2021, Proceedings, Part II Jul 2021

   Abs Bib HTML

   The significant interest in cryptographic primitives providing sound security margins when facing attacks with quantum computers is witnessed by the ongoing USA National Institute of Standards and Technology Post-quantum Cryptography Standardization process. Sound and precise evaluation of the amount of computation required to break such cryptographic primitives by means of quantum computers is required to be able to choose the cryptosystem parameters. We present a full description of a quantum circuit to accelerate the computation of the solution of the Information Set Decoding problem , which is currently the best known non-structural attack against code-based cryptosystems. We validate our design running it on small instances of error correction codes, which allowed a complete validation on the AtoS QLM quantum computer simulator. We detail the circuit accelerating the exponential complexity search phase in the Lee and Brickell variant of the ISD solver, and provide its computational complexity for cryptographically relevant parameters taken from the third round candidates in the USA post-quantum standardization process.

   @inproceedings{DBLP:conf/securecomm/PerrielloBP21,
     title = {A Quantum Circuit to Speed-up the Cryptanalysis of Code-Based Cryptosystems},
     booktitle = {Security and Privacy in Communication Networks - 17th {{EAI}} International Conference, {{SecureComm}} 2021, Virtual Event, September 6-9, 2021, Proceedings, Part {{II}}},
     author = {Perriello, Simone and Barenghi, Alessandro and Pelosi, Gerardo},
     editor = {{Garc{\'i}a-Alfaro}, Joaqu{\'i}n and Li, Shujun and Poovendran, Radha and Debar, Herv{\'e} and Yung, Moti},
     year = {2021},
     series = {Lecture Notes of the Institute for Computer Sciences, Social Informatics and Telecommunications Engineering},
     volume = {399},
     pages = {458--474},
     publisher = {{Springer}},
     doi = {10.1007/978-3-030-90022-9_25},
     url = {https://doi.org/10.1007/978-3-030-90022-9_25},
     bibsource = {dblp computer science bibliography, https://dblp.org},
     biburl = {https://dblp.org/rec/conf/securecomm/PerrielloBP21.bib},
   }