Abstract
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.
Alessandro Barenghi
Associate Professor
Alessandro Barenghi holds an M.Sc. (2007) and Ph.D. (2011) from Politecnico di Milano. His research focuses on computer, embedded, and network security, particularly applied cryptography. He also works on formal languages and compilers, specifically techniques for parallel parsing using operator precedence grammars.
Gerardo Pelosi
Associate Professor
Gerardo Pelosi received the Laurea degree in Telecommunications Engineering in 2003 and the Ph.D. degree in Computer Engineering and Information Technology in 2007 from Politecnico di Milano. His research fields cover (1) the area of information security and privacy including access control models, models for encrypted data management in relational databases, and secure data outsourcing; (2) the area of applied cryptography including side-channel cryptanalysis, system-level attacks, and efficient hardware and software design of cryptographic algorithms; other research interests are in designing security support into computer architectures and the logic synthesis of combinatorial circuits.