Limits on the efficiency of (ring) LWE-based non-interactive key exchange
type: Item
instance of: scholarly article
title: Limits on the efficiency of (ring) LWE-based non-interactive key exchange
zbMATH Open document ID: 1479.94183
author: Siyao Guo
author: Pritish Kamath
author: Alon Rosen
author: Katerina Sotiraki
published in: Journal of Cryptology
publication date: 2021-11-24T00:00:00Z
review text: Making non-interactive an interactive protocol, i.e. achieving the security goal in a single-round communication, is a common practice in the realm of public key cryptography. A practice that, at the time of writing, does not seem apply to key-exchange protocols based on the learning with errors problem (LWE), where all protocols are interactive. In this paper, the authors investigates the case of LWE-based key exchange protocols, with modulus polynomial in the security parameter, where key reconciliation is used from the parties to agree on the secret key, with the aim of proving that the intrinsic nature of the construction will force the protocol to be interactive, and to provide a non-interactive construction otherwise. The authors consider different natural reconciliation scenarios, proving that in each case the underlying protocol cannot be made non-interactive, i.e. it will require additional steps: in the first one, discussed in Section 4, they assume that the reconciliation function is defined as the product of the received LWE sample with the private LWE secret. It is information theoretically proved that, no matter the computational efficiency of the function, such a reconciliation cannot exists. In the second scenario (see Section 5), they consider the case of reconciliation functions not depending on the noises \(e_1\), \(e_2\), and they prove, assuming the hardness of LWE, that this is again not possible. In the last case of Section 6, they observe that the existence of a reconciliation which depends on all the inputs cannot be ruled out. However, some concerns on the computational complexity of the reconciliation function are raised.
reviewed by: Roberto Civino
Mathematics Subject Classification ID: 94A60
zbMATH DE Number: 7432891
zbMATH Keywords: learning with errors
zbMATH Keywords: key-exchange
zbMATH Keywords: non-interactive protocols
describes a project that uses: FrodoKEM
MaRDI profile type: Publication
full work available at URL: s00145-021-09406-y
OpenAlex ID: W3208745782
cites work: Large modulus ring-LWE \(\geq \) module-LWE
cites work: On the Hardness of Learning with Rounding over Small Modulus
cites work: (Leveled) fully homomorphic encryption without bootstrapping
cites work: Classical hardness of learning with errors
cites work: New and Improved Key-Homomorphic Pseudorandom Functions
cites work: Pseudorandom Functions and Lattices
cites work: Multiparty key exchange, efficient traitor tracing, and more from indistinguishability obfuscation
cites work: New directions in cryptography
cites work: Q3729902
cites work: On the asymptotic complexity of solving LWE
cites work: Key-homomorphic pseudorandom functions from LWE with small modulus
cites work: Spectra of graphs with transitive groups
cites work: On Ideal Lattices and Learning with Errors over Rings
cites work: Worst-case to average-case reductions for module lattices
cites work: Lattice Cryptography for the Internet
cites work: On lattices, learning with errors, random linear codes, and cryptography
cites work: On measures of dependence
cites work: On the ring-LWE and polynomial-LWE problems
cites work: Q4847941
cites work: Efficient Public Key Encryption Based on Ideal Lattices
cites work: How to use indistinguishability obfuscation
cites work: On Sequences of Pairs of Dependent Random Variables
DOI: 10.1007/S00145-021-09406-Y
description: scientific article; zbMATH DE number 7432891