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 polynomialLWE-modulus, resulting in unwanted efficiency overhead. We study the possibility of designing non-interactive LWE-based protocols with polynomialLWE-modulus. To this end, we identify and formalize simple non-interactive and polynomial LWE-modulus variants of the existing protocols, where Alice and Bob simultaneously exchange one or more (ring) LWE samples with polynomial 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 LWE sample with their private LWE secret. This impossibility is information theoretic. (2) One of the reconciliation functions does not depend on the error of the transmitted LWE sample. This impossibility assumes hardness of LWE. We show that progress toward either a polynomial LWE-modulus 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) LWE-based non-interactive key-exchange protocols.

Limits on the efficiency of (ring) LWE-based non-interactive key exchange

Rosen, Alon
;
2022

Abstract

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 polynomialLWE-modulus, resulting in unwanted efficiency overhead. We study the possibility of designing non-interactive LWE-based protocols with polynomialLWE-modulus. To this end, we identify and formalize simple non-interactive and polynomial LWE-modulus variants of the existing protocols, where Alice and Bob simultaneously exchange one or more (ring) LWE samples with polynomial 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 LWE sample with their private LWE secret. This impossibility is information theoretic. (2) One of the reconciliation functions does not depend on the error of the transmitted LWE sample. This impossibility assumes hardness of LWE. We show that progress toward either a polynomial LWE-modulus 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) LWE-based non-interactive key-exchange protocols.
2022
2021
Guo, Siyao; Kamath, Pritish; Rosen, Alon; Sotiraki, Katerina
File in questo prodotto:
File Dimensione Formato  
Guo2021_Article_LimitsOnTheEfficiencyOfRingLWE.pdf

non disponibili

Tipologia: Pdf editoriale (Publisher's layout)
Licenza: NON PUBBLICO - Accesso privato/ristretto
Dimensione 424.45 kB
Formato Adobe PDF
424.45 kB Adobe PDF   Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11565/4045463
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 8
  • ???jsp.display-item.citation.isi??? 7
social impact