Quantum computing allows the invention of some algorithms that are much more efficient than classical algorithms at solving specific problems. In particular, Shor’s algorithm [Shor97] allows a sufficiently powerful quantum computer to recover private keys from public keys for legacy cryptosystems, by factoring RSA public moduli [Ekerå21] and breaking the (EC)DLP [RNSL17].
The security of post-quantum cryptosystems remains a subject of interest in order to establish safe parameter sets, particularly for concrete instances – rather than asymptotic estimates – for the more recent problems in so-called lattice-based cryptography [APS15]. This is not only relevant to standardized primitives, but especially for cryptosystems that are still under development for advanced applications, such as threshold signatures, functional encryption, multiparty computation, and homomorphic encryption.
The candidate’s research will focus on an assessment of the level of security of concrete instances of post-quantum cryptosystems, through cryptanalytic techniques as well as practical software simulation of quantum information algorithms [LM21][PBP21].
References
[APS15] Martin R. Albrecht, Rachel Player and Sam Scott. On the concrete hardness of Learning with Errors. Journal of Mathematical Cryptology. Volume 9, Issue 3, Pages 169–203, ISSN (Online) 1862-2984, ISSN (Print) 1862-2976 DOI: 10.1515/jmc-2015-0016, October 2015. https://eprint.iacr.org/2015/046. https://github.com/malb/lattice-estimator
[Ekerå21] Ekerå, M. (2021). On completely factoring any integer efficiently in a single run of an order-finding algorithm. Quantum Information Processing, 20(6). https://doi.org/10.1007/s11128-021-03069-1
[LM21] Li, B., Micciancio, D. (2021). On the Security of Homomorphic Encryption on Approximate Numbers. In: Canteaut, A., Standaert, FX. (eds) Advances in Cryptology – EUROCRYPT 2021. EUROCRYPT 2021. Lecture Notes in Computer Science(), vol 12696. Springer, Cham. https://doi.org/10.1007/978-3-030-77870-5_23. https://eprint.iacr.org/2020/1533.
[PBP21] Perriello, S., Barenghi, A., Pelosi, G. (2021). A Quantum Circuit to Speed-Up the Cryptanalysis of Code-Based Cryptosystems. In: Garcia-Alfaro, J., Li, S., Poovendran, R., Debar, H., Yung, M. (eds) Security and Privacy in Communication Networks. SecureComm 2021. Lecture Notes of the Institute for Computer Sciences, Social Informatics and Telecommunications Engineering, vol 399. Springer, Cham. https://doi.org/10.1007/978-3-030-90022-9_25
[RNSL17] Roetteler, M., Naehrig, M., Svore, K. M., and Lauter, K. (2017). Quantum resource estimates for computing elliptic curve discrete logarithms. Cryptology ePrint Archive, Paper 2017/598. https://eprint.iacr.org/2017/598
[Shor97] Shor, P. W. (1997). Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing, 26(5), 1484–1509. https://doi.org/10.1137/s0097539795293172
Ideal candidate:
MSc in Mathematics or Computer Science w
