Quantum walk-based search algorithms have demonstrated an
asymptotic quadratic speedup compared to classical search
meth- ods. Formulating a generic search problem as a (quantum)
search over a graph makes the efficiency of the algorithm to
be closely dependent on the properties of the graph itself. In
this work, we present a com- plete implementation of a quantum
walk search procedure on Johnson graphs, speeding up the
solution of the Subset Sum Problem, a well- known
computational problem with applications in resource
allocation, scheduling, and cryptanalysis. We provide a
detailed design of each sub-circuit, quantifying their costs
in terms of gate count, circuit depth, and qubit width, and
exhibit all figures of merit as a function of the problem
parameters. Our approach includes two distinct implementa-
tions: one that minimizes qubit usage and another focused on
optimizing circuit depth. We compare our solutions against the
unstructured Grover based quantum search algorithm,
demonstrating a reduction of the cost on terms of T-count and
T-depth, for practically solvable instances. The proposed
design serves as a foundational building block for the devel-
opment of efficient quantum search algorithms that can be
modeled on Johnson graphs, bridging the gap with existing
theoretical complexity analyses.
@article{lancello2025SolvingSubsetSumJour,title={Solving the Subset Sum Problem via Quantum Walk Search},author={Lancellotti, Giacomo and Perriello, Simone and Barenghi, Alessandro and Pelosi, Gerardo},year={2026},journal={IEEE Transactions on Computers},shortjournal={IEEE Trans. Comput.},doi={10.1109/TC.2025.3625044},}
C8
Quantum Walks for Collision-Based Information Set Decoding
Code-based cryptography is central for post-quantum cryptography,
with security grounded in the hardness of the Syndrome
Decoding Problem (SDP). The most effective attacks are
variants of Information Set Decoding (ISD), which remain
exponential-time even in the quantum setting, where known
techniques provide at most quadratic speedups via quantum
amplitude amplification (QAA). In this work, we present the
first gate-level realization of quantum walks (QW) for
Stern-like collision-based ISD, and present a novel circuit
for the update operator of the QW, correcting issues in prior
proposals, while avoiding the use of exponential quantum
random-access memory. Our construction enables a circuit-level
complexity analysis under realistic cost models and allows a
direct comparison between QW-based and QAA-based ISD. We
evaluate our approach on the cryptographic schemes that
reached the final stages of international standardization.
Despite the richer algorithmic structure of QW, we show that
they do not outperform plain QAA-based ISD for practical
instances of the SDP, as the Gauss–Jordan elimination
subroutine dominates the overall cost. More generally, we
provide circuit-level evidence that QW offer an advantage over
QAA only when the oracle cost is asymptotically smaller than
the cost of the QW operations themselves. These results
clarify the practical algorithmic limits of QW techniques and
contribute to a more accurate assessment of quantum speedups
for structured search problems in cryptanalysis.
@inproceedings{10.1145/3801487.3801826,author={Perriello, Simone and Barenghi, Alessandro and Pelosi, Gerardo},title={Quantum Walks for Collision-Based Information Set Decoding},year={2026},isbn={9798400725685},publisher={Association for Computing Machinery},address={New York, NY, USA},url={https://doi.org/10.1145/3801487.3801826},doi={10.1145/3801487.3801826},booktitle={Proceedings of the 23rd ACM International Conference on Computing
Frontiers},pages={254–262},numpages={9},Decoding},location={
},series={CF '26},}
C7
Quantum Walks Design of Collision-Based Information Set Decoding
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{perriell2025QuantumCircuitDesignConf,title={Quantum Circuit Design for Finding K-{{Cliques}} via Quantum Amplitude Amplification Strategies},booktitle={Proceedings of the 22nd {{ACM}} International Conference on Computing Frontiers, {{CF}} 2025, Cagliari, Italy, May 28-30, 2025},author={Perriello, Simone},editor={Palumbo, Francesca and Tumeo, Antonino and Varbanescu, Ana Lucia and Simmhan, Yogesh},year={2025},pages={55--63},publisher={ACM},doi={10.1145/3719276.3725200},}
E1
Efficient QC-MDPC Cryptosystems with Bounded Decoding Failure Rate – Extended Version
Niederreiter-style post quantum cryptosystems based on QC-MDPC
codes, such as BIKE, have shown promising efficiency figures
and enjoy a straightforward reduction to conjectured-hard
problems in coding theory. The longstanding issue in their
design is having a closed form Decoding Failure Rate (DFR)
analysis of the iterative decoder employed by their decryption
primitive, as decoding failures leak information on the
private key. State of the art models either provide loose
bounds, or do not consider the decoding algorithm employed in
practice, using the behavior of a simpler one as a proxy. In
this work, we provide a closed-form estimate of the DFR for
the practically employed three-iterations parallel decoder,
applied to QC-MDPC codes. This result constitutes the first
closed form DFR model targeting both the same code family and
the same decoder employed in the cryptosystem. Leveraging our
estimation technique, we design the parameters for a QC-MDPC
based Niederreiter encryption scheme, obtaining a improvement
in public key and ciphertext size w.r.t. the previous best
cryptosystem design with DFR closed-form bounds,
LEDAcrypt-KEM. Furthermore, we show that our new parameters
yield up to 30% smaller public key size and 2.2\times to
4.4\times smaller ciphertexts w.r.t. HQC, the code based key
encapsulation method selected by the US NIST for
standardization, and achieve up to 3\times speedup with
respect to BIKE in ephemeral and long-term key usage.
@misc{annechini2025DesigningQCMDPCPublicJour,title={Efficient {QC}-{MDPC} Cryptosystems with Bounded Decoding Failure Rate -- Extended Version},author={Annechini, Alessandro and Barenghi, Alessandro and Pelosi, Gerardo and Perriello, Simone},year={2025},journal={IACR Cryptol. ePrint Arch.},url={https://eprint.iacr.org/2025/1043},bibsource={dblp computer science bibliography, https://dblp.org},}
2024
C5
A Quantum Circuit to Execute a Key-Recovery Attack Against the DES and 3DES Block Ciphers
Quantum computing enabled cryptanalytic techniques are able to concretely reduce the security margin of existing cryptographic primitives. While this reduction is only polynomial for symmetric cryptosystems, it still provides a quantifiable reduction in their security margin. In this work, we propose a detailed quantum circuit designed to cryptanalyze both the Data Encryption Standard (DES) cryptosystem, and its successor Triple-DES (3DES), currently standardized in ISO/IEC 18033-3, and still widely employed in satellite data and bank card encryption. To do so, we introduce the first quantum circuit implementation of the 8 substitution tables (a.k.a. S-boxes), applying a bitslicing strategy, which is currently the most efficient classical combinatorial circuit design in terms of number of two inputs Boolean gates. Secondly, we present the complete quantum circuits required to attack both DES and 3DES leveraging Grover’s algorithm. We provide finite equations, delineating the circuits complexities in terms of the number of qubits, gates, depth, and number of qubits multiplied by depth. The complexity analysis is based on two distinct gate sets: a NOT-CNOT-Toffoli (NCT) extended with the Hadamard gate; and the fault-tolerant Clifford+T. Finally, akin to the classical attack to the 3DES, we introduce a meet-in-the-middle strategy relying on an exponential amount of Quantum Random Access Memory. Our findings show that the 3DES with keying option 2, the most widely employed variant of 3DES, can be attacked with a circuit depth of approximately 2^67 and less than a thousand qubits. This aligns closely with the 2^64 value suggested by NIST for the depth achievable sequentially by a single quantum computer in a decade; our technique can be further sped up parallelizing the approach onto multiple devices.
@inproceedings{perriello2024AQuantumCircuitToExecuteAK,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, {{Montréal}}, {{Québec}}, {{Canada}}, {{September}} 15-20, 2024},author={Perriello, Simone and Barenghi, Alessandro and Pelosi, Gerardo},editor={Culhane, Candace and Byrd, Greg and Muller, Hausi and Alexev, Yuri and Sheldon, Sarah},year={2024},pages={1--12},publisher={{IEEE}},doi={10.1109/QCE60285.2024.00011},}
C4
Quantum Circuit Design for the Lee-Brickell Based Information Set Decoding
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{perriello2024QuantumCircuitDesignConfa,title={Quantum Circuit Design for the Lee-Brickell Based Information Set Decoding},booktitle={Applied Cryptography and Network Security Workshops},author={Perriello, Simone and Barenghi, Alessandro and Pelosi, Gerardo},editor={Andreoni, Martin},year={2024},pages={8--28},publisher={Springer Nature Switzerland},location={{Abu Dhabi, UAE}},doi={10.1007/978-3-031-61489-7_2},url={https://doi.org/10.1007/978-3-031-61489-7_2},isbn={978-3-031-61489-7},}
C3
Design of a Quantum Walk Circuit to Solve the Subset-Sum Problem
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},year={2024},publisher={ACM},doi={10.1145/3649329.3657337},url={https://doi.org/10.1145/3649329.3657337},}
PhD
Quantum Circuits for Information Set Decoding : Quantum Cryptanalysis of Code-Based Cryptosystems
The emergence of quantum computing represents a profound challenge to the security of widely-adopted public-key cryptographic systems, which rely on the computational complexity of tasks such as factoring large integers or solving discrete logarithms. To confront this challenge, esteemed organizations like the U.S. National Institute of Standards and Technology (NIST), the Chinese Association for Cryptologic Research (CACR), and the European Telecommunications Standards Institute (ETSI) are actively engaged in the formulation of cryptographic primitives capable of withstanding both classical and quantum attacks. These novel cryptographic systems, collectively termed post-quantum cryptosystems, are at the forefront of standardization efforts. Among the leading contenders in this standardization endeavor, linear code-based cryptosystems, deriving their strength from the computational complexity of the Syndrome Decoding Problem (SDP), have gained significant recognition. The SDP is defined as the task of retrieving an error vector when provided with the parity check matrix of a randomly generated linear block error correction code and the syndrome of the error, as computed through the same matrix. Classically, the most effective technique for solving the SDP is the Information Set Decoding (ISD) method, which, notably, exhibits exponential complexity with respect to the parameters of the cryptosystems. Current quantum approaches to the SDP, on the other hand, do not surpass the quadratic speedup offered by adapting Grover’s algorithm to the ISD technique, and provide only asymptotic estimates of their computational cost, potentially hiding non-trivial constant and polynomial factors. The central focus of this study revolves around the precise computational complexity evaluation of quantum solvers for the SDP, tailored to cryptography-grade code parameters. Our approach introduces quantum circuits designed for universal quantum gate-based computing models, that are build upon the foundations laid by classic ISD techniques. Our scrutiny extends to both complete quantum solutions to the SDP and hybrid methodologies that effectively partition the computational load between classical and quantum computing resources. In our investigation, the approach stemming from Prange’s approach to the ISD technique stands out, as it displays a substantial enhancement in computational efficiency. Notably, it leads to a reduction in both the depth of quantum circuits and the depth-times-width metric by factors ranging from 2¹² to 2²⁴ applicable to concrete cryptography-grade parameters. Surprisingly, our findings reveal that the gains achieved through the approach inspired by Lee and Brickell’s ideas, which materialize as a hybrid classical-quantum algorithm, are somewhat modest. These enhancements range from 2¹⁰ to 2²⁰ for the same cryptographic parameters, a result contrary to expectations based on classical counterparts, where Lee and Brickell’s approach prevails over Prange’s one. However, the hybrid approach substantially reduces the size and depth of quantum circuits, rendering the estimates more realistic and facilitating parallel execution on separate quantum computing platforms. Our quantitative analysis of computational costs brings forth a significant conclusion: all code-based cryptoschemes under the scrutiny of esteemed organizations such as NIST, particularly BIKE, HQC, and McEliece, unequivocally surpass the predefined threshold for computational hardness. Put simply, they prove to be computationally more demanding than the task of breaking a corresponding symmetric cipher with appropriately-sized key lengths. Furthermore, a critical vulnerability in the Classic McEliece cryptoscheme is unveiled. Parallelizing this algorithm across multiple quantum processing units erodes its security, plunging it below the targeted security threshold by a factor of 16. An ancillary contribution of this research is the development of a set of quantum circuits capable of solving common algebraic and algorithmic problems, including Gauss-Jordan Elimination over finite fields, bit string sorting, and Hamming weight computation, which may be of independent interest in the field of quantum computing.
@thesis{perriello2024QuantumCircuitsInformationThes,type={monograph},title={Quantum Circuits for Information Set Decoding : {{Quantum}} Cryptanalysis of Code-Based Cryptosystems},author={Perriello, Simone},year={2024},institution={Politecnico di Milano}}
2023
J1
Improving the Efficiency of Quantum Circuits for Information Set Decoding
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
C2
A Complete Quantum Circuit to Solve the Information Set Decoding Problem
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},timestamp={Tue, 30 Nov 2021 17:31:17 +0100},}
C1
A Quantum Circuit to Speed-up the Cryptanalysis of Code-Based Cryptosystems
In Security and Privacy in Communication Networks - 17th EAI International Conference, SecureComm 2021, Virtual Event, September 6-9, 2021, Proceedings, Part II, May 2021
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://hdl.handle.net/10589/220713},bibsource={dblp computer science bibliography, https://dblp.org},biburl={https://dblp.org/rec/conf/securecomm/PerrielloBP21.bib},timestamp={Wed, 15 Dec 2021 10:32:56 +0100},}