On the Security of the Learning with Errors Problem with Side Information

Abstract

Modern-day cryptosystems rely on mathematical problems that are easy to construct, but computationally infeasible even for large supercomputers to solve, such as factoring enormous numbers. However, the advent of quantum computing poses a threat to several cryptosystems which are standardized and currently in wide use. As quantum computers operate on different mathematical principles than classical computers, they could theoretically crack these math problems with ease and render private encrypted data vulnerable. As such, new systems are being designed in order to guarantee security even in the post-quantum age. Many post-quantum cryptosystems rely on the Learning with Errors (LWE) problem, which is believed to be secure against attacks from both classical and quantum adversaries. As several of these algorithms are in the process of being standardized, it is critical to scrutinize LWE in order to identify and remedy any potential weaknesses. In our work, we investigate the robustness of the LWE problem in the situation where some side information about the secret key is leaked. We abstractly model this side information as mathematical hints in order to contribute to a flexible framework for estimating the security of various LWE-based cryptosystems, and we apply this framework to the CRYSTALS-Kyber public-key cryptosystem and the CKKS approximate fully homomorphic encryption scheme. The framework models the underlying LWE problem as a high-dimensional ellipsoid, and side information as geometric constraints on this ellipsoid.