Classical hardness of learning with errors
From MaRDI portal
Abstract: We show that the Learning with Errors (LWE) problem is classically at least as hard as standard worst-case lattice problems, even with polynomial modulus. Previously this was only known under quantum reductions. Our techniques capture the tradeoff between the dimension and the modulus of LWE instances, leading to a much better understanding of the landscape of the problem. The proof is inspired by techniques from several recent cryptographic constructions, most notably fully homomorphic encryption schemes.
Recommendations
Cited in
(only showing first 100 items - show all)- On basing search SIVP on \(\mathbf{NP}\)-hardness
- Traitor-tracing from LWE made simple and attribute-based
- Two-message statistically sender-private OT from LWE
- On the ring-LWE and polynomial-LWE problems
- Scalable zero knowledge via cycles of elliptic curves
- Hardness of \(k\)-LWE and applications in traitor tracing
- On the asymptotic complexity of solving LWE
- Zero-knowledge arguments for matrix-vector relations and lattice-based group encryption
- The polynomial approximate common divisor problem and its application to the fully homomorphic encryption
- Improved security proofs in lattice-based cryptography: using the Rényi divergence rather than the statistical distance
- Learning with errors and extrapolated dihedral cosets
- A simple provably secure AKE from the LWE problem
- A multi-key SMC protocol and multi-key FHE based on some-are-errorless LWE
- A framework for cryptographic problems from linear algebra
- Verifying solutions to LWE with implications for concrete security
- Towards a ring analogue of the leftover hash lemma
- Collusion-resistant identity-based proxy re-encryption: lattice-based constructions in standard model
- Limits on the efficiency of (ring) LWE-based non-interactive key exchange
- Optimal broadcast encryption from pairings and LWE
- Tweaking the asymmetry of asymmetric-key cryptography on lattices: KEMs and signatures of smaller sizes
- Decentralized multi-authority \textbf{\textsf{ABE}} for \textbf{\textsf{DNF}}s from \textbf{\textsf{LWE}}
- A \(2^{n/2}\)-time algorithm for \(\sqrt{n} \)-SVP and \(\sqrt{n} \)-Hermite SVP, and an improved time-approximation tradeoff for (H)SVP
- New lattice two-stage sampling technique and its applications to functional encryption -- stronger security and smaller ciphertexts
- Multiparty reusable non-interactive secure computation from LWE
- Chosen ciphertext attacks secure inner-product functional encryption from learning with errors assumption
- On the integer polynomial learning with errors problem
- Exact lattice sampling from non-Gaussian distributions
- Round-optimal verifiable oblivious pseudorandom functions from ideal lattices
- Identity-based encryption with security against the KGC: a formal model and its instantiations
- Incompressible encodings
- Rounding in the rings
- A new post-quantum multivariate polynomial public key encapsulation algorithm
- Fiat-Shamir for repeated squaring with applications to PPAD-hardness and VDFs
- Quantum key search for ternary LWE
- Hardness of LWE on general entropic distributions
- Key-homomorphic pseudorandom functions from LWE with small modulus
- Two-round oblivious transfer from CDH or LPN
- Compact ring signatures from learning with errors
- A black-box approach to post-quantum zero-knowledge in constant rounds
- How to meet ternary LWE keys
- Smoothing out binary linear codes and worst-case sub-exponential hardness for LPN
- Attribute-based signatures from lattices: unbounded attributes and semi-adaptive security
- Universal product learning with errors: a new variant of \textsf{LWE} for lattice-based cryptography
- Attribute-based conditional proxy re-encryption in the standard model under LWE
- Lattice-based HRA-secure attribute-based proxy re-encryption in standard model
- On the higher-bit version of approximate inhomogeneous short integer solution problem
- Puncturable identity-based and attribute-based encryption from lattices
- On the lattice isomorphism problem, quadratic forms, remarkable lattices, and cryptography
- Algebraically structured LWE. Revisited
- Matrix PRFs: constructions, attacks, and applications to obfuscation
- Generalized approach for analysing quantum key distribution experiments
- Revocable identity-based encryption with bounded decryption key exposure resistance: lattice-based construction and more
- Computational fuzzy extractors
- Extremal set theory and LWE based access structure hiding verifiable secret sharing with malicious-majority and free verification
- The projection games conjecture and the hardness of approximation of Super-SAT and related problems
- On the complexity of the BKW algorithm on LWE
- TFHE: fast fully homomorphic encryption over the torus
- A new Gaussian sampling for trapdoor lattices with arbitrary modulus
- Worst-case to average-case reductions for module lattices
- Estimation of the hardness of the learning with errors problem with a restricted number of samples
- Error analysis of weak poly-LWE instances
- Efficient and fully secure lattice-based IBE with equality test
- On the hardness of module learning with errors with short distributions
- Computational fuzzy extractor from LWE
- Adaptively secure inner product encryption from LWE
- Finding collisions in a quantum world: quantum black-box separation of collision-resistance and one-wayness
- Towards classical hardness of module-LWE: the linear rank case
- Direct computation of branching programs and its applications to more efficient lattice-based cryptography
- Secret handshakes: full dynamicity, deniability and lattice-based design
- On solving LPN using BKW and variants, Implementation and analysis
- Finding shortest lattice vectors in the presence of gaps
- Post-quantum forward-secure onion routing (future anonymity in today's budget)
- On the hardness of learning with rounding over small modulus
- Cryptographic assumptions: a position paper
- Adaptive security with quasi-optimal rate
- A lattice-based group signature scheme with message-dependent opening
- Turing machines with shortcuts: efficient attribute-based encryption for bounded functions
- How (not) to instantiate ring-LWE
- FHE circuit privacy almost for free
- Three’s Compromised Too: Circular Insecurity for Any Cycle Length from (Ring-)LWE
- Circular Security Separations for Arbitrary Length Cycles from LWE
- Spooky Encryption and Its Applications
- Fully secure functional encryption for inner products, from standard assumptions
- Hardness of SIS and LWE with small parameters
- FHEW with Efficient Multibit Bootstrapping
- Augmented Learning with Errors: The Untapped Potential of the Error Term
- Zero-knowledge arguments for matrix-vector relations and lattice-based group encryption
- Signature Schemes with Efficient Protocols and Dynamic Group Signatures from Lattice Assumptions
- Towards tightly secure lattice short signature and id-based encryption
- Faster fully homomorphic encryption: bootstrapping in less than 0.1 seconds
- On error distributions in ring-based LWE
- Multi-bit leveled homomorphic encryption via dual LWE-based
- A practical post-quantum public-key cryptosystem based on spLWE
- Approximate-deterministic public key encryption from hard learning problems
- Multi-key FHE from LWE, revisited
- Deniable Attribute Based Encryption for Branching Programs from LWE
- Targeted homomorphic attribute-based encryption
- On the efficacy of solving LWE by reduction to unique-SVP
- Secure statistical analysis using RLWE-based homomorphic encryption
- Bi-homomorphic Lattice-Based PRFs and Unidirectional Updatable Encryption
This page was built for publication: Classical hardness of learning with errors
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5495828)
