Limits on the efficiency of (ring) LWE-based non-interactive key exchange
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.
- Limits on the efficiency of (ring) LWE based non-interactive key exchange
- Constant-round group key exchange from the ring-LWE assumption
- Application of algebraic-ring in key exchange protocol
- Tree-Based Ring-LWE Group Key Exchanges with Logarithmic Complexity
- Improved attacks against key reuse in learning with errors key exchange
- (Leveled) fully homomorphic encryption without bootstrapping
- Classical hardness of learning with errors
- Efficient public key encryption based on ideal lattices (extended abstract)
- How to use indistinguishability obfuscation
- scientific article; zbMATH DE number 3960854 (Why is no real title available?)
- scientific article; zbMATH DE number 799789 (Why is no real title available?)
- Key-homomorphic pseudorandom functions from LWE with small modulus
- Large modulus ring-LWE \(\geq \) module-LWE
- Lattice cryptography for the internet
- Multiparty key exchange, efficient traitor tracing, and more from indistinguishability obfuscation
- New and improved key-homomorphic pseudorandom functions
- New directions in cryptography
- On ideal lattices and learning with errors over rings
- On lattices, learning with errors, random linear codes, and cryptography
- On measures of dependence
- On Sequences of Pairs of Dependent Random Variables
- On the asymptotic complexity of solving LWE
- On the hardness of learning with rounding over small modulus
- On the ring-LWE and polynomial-LWE problems
- Pseudorandom functions and lattices
- Spectra of graphs with transitive groups
- Worst-case to average-case reductions for module lattices
- An efficient and generic construction for signal's handshake (X3DH): post-quantum, state leakage secure, and deniable
- An attack on a non-interactive key exchange from code equivalence
- Limits on the efficiency of (ring) LWE based non-interactive key exchange
- Application of algebraic-ring in key exchange protocol
- Fine-grained non-interactive key-exchange: constructions and lower bounds
- Error correction and ciphertext quantization in lattice cryptography
- On the multi-user security of LWE-based NIKE
- Private set operations from multi-query reverse private membership test
- Lower bounds for lattice-based compact functional encryption
- MODRED: a code-based non-interactive key exchange protocol
- Fine-grained non-interactive key-exchange without idealized assumptions
- Fine-grained non-interactive key exchange, revisited
- SoK: how (not) to design and implement post-quantum cryptography
This page was built for publication: Limits on the efficiency of (ring) LWE-based non-interactive key exchange
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2051406)
