King's College London

Standardisation efforts for post-quantum public-key encryption and signatures are close to completion. At the same time, the past decade has seen the large-scale deployment of more advanced cryptographic algorithms for which no efficient post-quantum candidates currently exist. These algorithms, for example, enable strong guarantees even after some parties have been compromised, as well as privacy-preserving contact lookups, credentials, and e-cash. This project will tackle the challenge of “lifting” such constructions to the post-quantum era by pursuing three guiding questions:    

• What is the cost of solving lattice problems with and without hints on a quantum computer? Answers to this question will provide confidence in the entire stack of lattice-based cryptography from “basic” to “advanced”. Studying the presence of hints tackles side-channel attacks and advanced constructions.
• What are the lattice assumptions that establish feature parity and (near) performance-parity with pre-quantum cryptography? Standard lattice assumptions do not seem to establish feature parity with pairing-based or even some Diffie-Hellman-based pre-quantum constructions, how can we achieve efficient and secure advanced practical post-quantum solutions?        
• How efficient is a careful composition of lattice-base cryptography with other assumptions? If we want to deploy our post-quantum solutions in practice, we will need to design hybrid schemes that are secure if either of their pre- or post-quantum part is secure and to deploy many advanced lattice-based primitives in practice we need to carefully compose them with zero-knowledge proofs to rule out some attacks.      

Lattice-based cryptography has established itself as a key technology to realise both efficient basic primitives like post-quantum encryption and advanced solutions such as computation with encrypted data and programs. It is thus well positioned to tackle the middle ground of advanced yet practical primitives for phase 2 of the post-quantum transition.