On the hardness of module learning with errors with short distributions
The paper provides new results about the Learning With Errors (LWE) problem. Given two positive integers \(d\) and \(q\), and a secret vector \(s\in Z^d_q\), an LWE\(_{d,q,\psi}\) sample is defined as \((a, b = q^{-1}\langle a, s\rangle + e\bmod \mathbb{Z})\), where \(a\) is sampled from the uniform distribution over \(Z^d_q\), and \(e\) an error term sampled from a distribution \(\psi\) over \(\mathbb{R}\). The search version of LWE asks to recover the secret \(s\) given arbitrarily many samples of the LWE distribution. Its decision counterpart asks to distinguish between LWE samples and the same number of samples drawn from the uniform distribution over \(Z^d_q\times T\), where the torus is defined by \(\mathbb{T} = \mathbb{R}/\mathbb{Z}\). The authors focus in particular on the Module Learning With Errors (M-LWE) problem similar to LWE where the set of integers \(\mathbb{Z}\) is replaced by the ring of algebraic integers \(R\) of a number field \(K\). The integer \(n\) denotes the degree of the number field, \(d\) denotes the module rank, and \(q\) the modulus. Further, let \(\psi\) be a distribution on the field tensor product \(K_\mathbb{R} = K\otimes _\mathbb{Q}\mathbb{R}\), and let \(s\in R^d_q\) be a secret vector, where \(R_q = R/q R\). An M-LWE\(_{n,d,q,\psi}\) sample is given by \((a, q^{-1}\langle a,s\rangle + e\bmod R)\), where \(a\) is uniform in \(R^d_q\), and \(e\) is sampled from \(\psi\). The search version asks to find \(s\) given arbitrarily many samples, while the decision version asks to distinguish such samples from uniformly random ones over \(R^d_q\times\mathbb{T}\), where the torus is \(\mathbb{T} = K_\mathbb{R}/R\). In this paper, the authors provide three main contributions to the hardness of M-LWE with small secret and/or error, i.e., with coefficients bounded by some positive integer \(\eta\ll q\). The first one is the computational hardness of \(\eta\)-M-LWE. The next one is pseudorandomness of \(\eta\)-M-LWE. The authors provide a more involved proof of hardness for the decision version of \(\eta\)-M-LWE through a reduction from M-LWE to \(\eta\)-M-LWE. This reduction applies to the decision versions, and it also slightly improves the noise rate of the reduction as it no longer depends on the number of samples \(m\), as opposed to the first contribution. The third contribution is the one-ways of M-LWE with small error. It focuses on the hardness of M-SLWE when the error distribution is uniform over \(\eta\)-bounded elements instead of Gaussian.
- (Leveled) fully homomorphic encryption without bootstrapping
- A toolkit for ring-LWE cryptography
- Algebraically structured LWE. Revisited
- An efficient and parallel Gaussian sampler for lattices
- An improved BKW algorithm for LWE with applications to cryptography and lattices
- Better key sizes (and attacks) for LWE-based encryption
- Classical hardness of learning with errors
- Effective algorithms with circulant-block matrices
- Efficient public key encryption based on ideal lattices (extended abstract)
- Fast Cryptographic Primitives and Circular-Secure Encryption Based on Hard Learning Problems
- FHEW: bootstrapping homomorphic encryption in less than a second
- Generalized compact knapsacks, cyclic lattices, and efficient one-way functions
- GGHLite: more efficient multilinear maps from ideal lattices
- Hardness of LWE on general entropic distributions
- Hardness of SIS and LWE with small parameters
- scientific article; zbMATH DE number 3173999 (Why is no real title available?)
- scientific article; zbMATH DE number 1942427 (Why is no real title available?)
- Improved security proofs in lattice-based cryptography: using the Rényi divergence rather than the statistical distance
- Large modulus ring-LWE \(\geq \) module-LWE
- Lattice signatures without trapdoors
- Limits on the hardness of lattice problems in \(\ell_{p}\) norms
- Lossiness and entropic hardness for ring-LWE
- New Algorithms for Learning in Presence of Errors
- Noise-tolerant learning, the parity problem, and the statistical query model
- On ideal lattices and learning with errors over rings
- On lattices, learning with errors, random linear codes, and cryptography
- On lattices, learning with errors, random linear codes, and cryptography
- On the hardness of learning with errors with binary secrets
- On the hardness of module-LWE with binary secret
- On the ring-LWE and polynomial-LWE problems
- On the RLWE/PLWE equivalence for cyclotomic number fields
- Pseudorandom knapsacks and the sample complexity of LWE search-to-decision reductions
- Pseudorandomness of ring-LWE for any ring and modulus
- Public-key cryptosystems from the worst-case shortest vector problem
- Revisiting the hardness of binary error LWE
- Rényi Divergence and Kullback-Leibler Divergence
- Short, invertible elements in partially splitting cyclotomic rings and applications to lattice-based zero-knowledge proofs
- Shorter lattice-based zero-knowledge proofs via one-time commitments
- Solving BDD by enumeration: an update
- Towards classical hardness of module-LWE: the linear rank case
- Trapdoors for hard lattices and new cryptographic constructions
- Trapdoors for lattices: simpler, tighter, faster, smaller
- Worst-case to average-case reductions for module lattices
- Worst‐Case to Average‐Case Reductions Based on Gaussian Measures
- Lattice signature with efficient protocols, application to anonymous credentials
- Hardness of (M)LWE with semi-uniform seeds
- Spherical Gaussian leftover hash lemma via the Rényi divergence
- Identity-based encryption from lattices using approximate trapdoors
- \textsf{SMAUG}: pushing lattice-based key encapsulation mechanisms to the limits
- Two-round threshold signature from algebraic one-more learning with errors
- Improved lattice blind signatures from recycled entropy
- Two-round threshold signature from algebraic one-more learning with errors
- Module learning with errors with truncated matrices
- Leftover hash lemma(s) over cyclotomic rings
- Refined modelling of the primal attack, and variants against Module-LWE
- Revisiting module lattice-based homomorphic encryption and application to secure-MPC
- Hardness of M-LWE with general distributions and applications to leaky variants
- Towards post-quantum bitcoin blockchain using Dilithium signature
- On the hardness of module-LWE with binary secret
This page was built for publication: On the hardness of module learning with errors with short distributions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2677644)
