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 the hardness of module-LWE with binary secret
- Almost tight security in lattices with polynomial moduli -- PRF, IBE, all-but-many LTF, and more
- Tight adaptive simulation security for identity-based inner-product FE in the (quantum) random oracle model
- Worst-case to average-case hardness of LWE: an alternative perspective
- Sparse linear regression and lattice problems
- Solving LWR via BDD Strategy: Modulus Switching Approach
- More efficient functional bootstrapping for general functions in polynomial modulus
- Low communication threshold fully homomorphic encryption
- Matrix PRFs: constructions, attacks, and applications to obfuscation
- Augmented Learning with Errors: The Untapped Potential of the Error Term
- Fiat-Shamir for repeated squaring with applications to PPAD-hardness and VDFs
- SO-CCA secure PKE from pairing based all-but-many lossy trapdoor functions
- TFHE: fast fully homomorphic encryption over the torus
- A new Gaussian sampling for trapdoor lattices with arbitrary modulus
- mrNISC from LWE with polynomial modulus
- A simple provably secure AKE from the LWE problem
- Another round of breaking and making quantum money: how to not build it from lattices, and more
- Constraint-Hiding Constrained PRFs for NC $$^1$$ from LWE
- Post-quantum insecurity from LWE
- The informativeness of the gradient revisited
- Reducing the number of qubits in solving LWE
- Discrete Gaussian sampling for BKZ-reduced basis
- Module learning with errors with truncated matrices
- FHE circuit privacy almost for free
- Trapdoors for ideal lattices with applications
- On solving LPN using BKW and variants, Implementation and analysis
- A framework for cryptographic problems from linear algebra
- Ring packing and amortized FHEW bootstrapping
- Indistinguishability obfuscation from well-founded assumptions
- Post-quantum forward-secure onion routing (future anonymity in today's budget)
- A multi-key SMC protocol and multi-key FHE based on some-are-errorless LWE
- Quantum key search for ternary LWE
- A black-box approach to post-quantum zero-knowledge in constant rounds
- On the ring-LWE and polynomial-LWE problems
- On the asymptotic complexity of solving LWE
- Secure statistical analysis using RLWE-based homomorphic encryption
- Fully selective opening secure IBE from LWE
- Generic constructions of master-key KDM secure attribute-based encryption
- Improved security proofs in lattice-based cryptography: using the Rényi divergence rather than the statistical distance
- Deniable Attribute Based Encryption for Branching Programs from LWE
- Extremal set theory and LWE based access structure hiding verifiable secret sharing with malicious-majority and free verification
- Concrete analysis of approximate ideal-SIVP to decision ring-LWE reduction
- How (not) to instantiate ring-LWE
- Fully secure functional encryption for inner products, from standard assumptions
- Zero-knowledge arguments for matrix-vector relations and lattice-based group encryption
- On the hardness of learning with rounding over small modulus
- On the hardness of learning with errors with binary secrets
- Zero-knowledge arguments for matrix-vector relations and lattice-based group encryption
- 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
- Almost tight security in lattices with polynomial moduli -- PRF, IBE, all-but-many LTF, and more
- Limits on the efficiency of (ring) LWE-based non-interactive key exchange
- How to meet ternary LWE keys
- Smoothing out binary linear codes and worst-case sub-exponential hardness for LPN
- The projection games conjecture and the hardness of approximation of Super-SAT and related problems
- Attribute-based signatures from lattices: unbounded attributes and semi-adaptive security
- Leveled Hierarchical Identity-Based Fully Homomorphic Encryption from Learning with Rounding
- On the multi-user security of LWE-based NIKE
- The polynomial approximate common divisor problem and its application to the fully homomorphic encryption
- Learning with errors and extrapolated dihedral cosets
- Faster Dual Lattice Attacks for Solving LWE with Applications to CRYSTALS
- A new post-quantum multivariate polynomial public key encapsulation algorithm
- Hardness of LWE on general entropic distributions
- Algebraically structured LWE. Revisited
- Key-homomorphic pseudorandom functions from LWE with small modulus
- Integer version of ring-LWE and its applications
- Watermarking cryptographic functionalities from standard lattice assumptions
- Bi-homomorphic Lattice-Based PRFs and Unidirectional Updatable Encryption
- Cryptographic assumptions: a position paper
- Classical verification of quantum computations
- Fully homomorphic encryption with auxiliary inputs
- Multi-key FHE from LWE, revisited
- Improved classical and quantum algorithms for the shortest vector problem via bounded distance decoding
- Algebraically structured LWE, revisited
- G+G: a Fiat-Shamir lattice signature based on convolved Gaussians
- Separating semantic and circular security for symmetric-key bit encryption from the learning with errors assumption
- Lattice-based SNARGs and their application to more efficient obfuscation
- Private puncturable PRFs from standard lattice assumptions
- Hardness of SIS and LWE with small parameters
- Entropic hardness of Module-LWE from module-NTRU
- How to sample a discrete Gaussian (and more) from a random oracle
- Collusion resistant traitor tracing from learning with errors
- Lattice-Based DAPS and Generalizations: Self-enforcement in Signature Schemes
- Turing machines with shortcuts: efficient attribute-based encryption for bounded functions
- Universal product learning with errors: a new variant of \textsf{LWE} for lattice-based cryptography
- Exploiting the symmetry of \(\mathbb{Z}^n\): randomization and the automorphism problem
- Efficient updatable public-key encryption from lattices
- Balanced non-adjacent forms
- Towards a ring analogue of the leftover hash lemma
- Collusion-resistant identity-based proxy re-encryption: lattice-based constructions in standard model
- Problem of learning with errors and modern cryptosystems
- Revocable identity-based encryption with bounded decryption key exposure resistance: lattice-based construction and more
- Signature Schemes with Efficient Protocols and Dynamic Group Signatures from Lattice Assumptions
- Puncturable Identity-Based Encryption from Lattices
- Towards a simpler lattice gadget toolkit
- Efficient identity-based encryption with tight adaptive anonymity from RLWE
- Properties of lattice isomorphism as a cryptographic group action
- Lattice-Based Group Encryption with Full Dynamicity and Message Filtering Policy
- Efficient FHEW bootstrapping with small evaluation keys, and applications to threshold homomorphic 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)
