Hardness foundation of efficient lattice-based cryptography – HELO

Post-quantum cryptography aims to design the cryptographic primitives that can be executed by classical computers, but resist to attacks by quantum computers. Lattice-based cryptography, standardized by the American National Institute of Standards and Technology, will be deployed in our daily life in the near future.

One of the most appealing property in lattice-based cryptography is that its security is based on the hardness of worst-case lattice problems. However, for practical reason, the highly efficient cryptographic schemes are used to be instantiated with extremely small parameters or even with some additional leakage on the secret information. In such case, the security foundation on the worst-case lattice problems is no more present.

In this project, we aim to study the hardness of these problems without worst-case connection. Our investigation will be made in two ways. First, we will try to re-establish the worst-case connection in case the additional leakage does not invalidate the hardness of the problems. Second, we will keep improving the best existing solving algorithms or proposing new algorithms by integrating these additional leakages about secret.

Last, there is little knowledge about the quantum hardness of lattice problems, especially about their algebraic variants. Our last research axis will focus on the quantum hardness of lattice problems, in particular the ones with algebraic structures and small parameters. The main idea will be to establish the connection/equivalence between lattice problems and quantum problems. Such connection will provide us new direction for analyzing the hardness of lattice problems.