Information Theory and Cryptography share a common foundation in Shannon’s pioneering work. These fields are deeply interconnected and have the potential to mutually enhance one another. The advent of Post-Quantum Cryptography (PQC) offers a unique opportunity to reunite these disciplines. In this work, we uncover a novel connection between information theory and the Learning With Errors (LWE) problem. Specifically, we introduce Learning With Quantization (LWQ), a new problem closely related to LWE and Learning With Rounding (LWR). LWQ establishes a tight security reduction from LWE while enabling efficient ciphertext compression. Notably, we demonstrate that the compression rate is ultimately governed by the capacity of the “LWE channel,” thereby unifying the concepts of information-theoretic compression and computational security.
Paper: https://eprint.iacr.org/2024/714
Cong Ling is a Professor of Information Theory and Cryptography at Imperial College London. His research focuses on the study of lattices and their applications to coding and cryptography, as well as exploring their connections with number theory and quantum information.