International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Limits on the Efficiency of (Ring) LWE-Based Non-interactive Key Exchange

Siyao Guo
Pritish Kamath
Alon Rosen
Katerina Sotiraki
DOI: 10.1007/s00145-021-09406-y
Search ePrint
Search Google
Abstract: $$\mathsf {LWE}$$ LWE -based key-exchange protocols lie at the heart of post-quantum public-key cryptography. However, all existing protocols either lack the non-interactive nature of Diffie–Hellman key exchange or polynomial $$\mathsf {LWE}$$ LWE -modulus, resulting in unwanted efficiency overhead. We study the possibility of designing non-interactive $$\mathsf {LWE}$$ LWE -based protocols with polynomial $$\mathsf {LWE}$$ LWE -modulus. To this end, we identify and formalize simple non-interactive and polynomial $$\mathsf {LWE}$$ LWE -modulus variants of the existing protocols, where Alice and Bob simultaneously exchange one or more (ring) $$\mathsf {LWE}$$ LWE samples with polynomial $$\mathsf {LWE}$$ LWE -modulus and then run individual key reconciliation functions to obtain the shared key. We point out central barriers and show that such non-interactive key-exchange protocols are impossible in either of the following cases: (1) the reconciliation functions first compute the inner product of the received $$\mathsf {LWE}$$ LWE sample with their private $$\mathsf {LWE}$$ LWE secret. This impossibility is information theoretic. (2) One of the reconciliation functions does not depend on the error of the transmitted $$\mathsf {LWE}$$ LWE sample. This impossibility assumes hardness of $$\mathsf {LWE}$$ LWE . We show that progress toward either a polynomial $$\mathsf {LWE}$$ LWE -modulus $$\text {NIKE}$$ NIKE construction or a general impossibility result has implications to the current understanding of lattice-based cryptographic constructions. Overall, our results show possibilities and challenges in designing simple (ring) $$\mathsf {LWE}$$ LWE -based non-interactive key-exchange protocols.
  title={Limits on the Efficiency of (Ring) LWE-Based Non-interactive Key Exchange},
  journal={Journal of Cryptology},
  author={Siyao Guo and Pritish Kamath and Alon Rosen and Katerina Sotiraki},