PROJECT
From Classical to Quantum Cryptoanalysis of Post-Quantum Cryptography
DOCTORAL CANDIDATE
Supervisors
May (RUB), Walter (RUB), Güneysu (RUB), Schaffner (UvA), Kashefi (SU), Daum (Genua).
Objectives
Design new quantum attacks for the post-quantum cryptosystems in NIST standardization.
Expected Results
Precise definition of quantum bit-security level, possibly requiring adaptation of current parameter settings.
Description
NIST will soon announce winners of their post-quantum cryptographic standardization process. For encryption, these will be coding- and lattice-based cryptosystems. While the classic hardness of these schemes has been studied thoroughly, their hardness against quantum attacks is way less understood. As an example, classical decoding algorithms have seen tremendous improvements within the last decade with implications to McEliece parameter selection, while the best known quantum attack on McEliece is still a simple Groverversion of a decoding algorithm from 1962. Also in lattices, in the last decade there were plenty of algorithmic improvements on the classical side, including sieving and locality sensitive hashing, while the speedup from quantum algorithms is almost negligible. We will design new quantum attacks directly on PQC, and provide a concrete quantum security bit estimator software for coding- and lattice-based cryptosystems.
Methodology
We build on typical quantum tools for algorithm design, such as quantum random walks. Whenever possible, we focus on algorithmic tools with small quantum memory consumption.
Risks
If we fail to find asymptotic improvements for quantum cryptanalytic algorithms, as a fallback, we will concentrate on second order improvements and on improved implementations. Improvements in these areas are also highly relevant to the current post-quantum standardization process.
