Classical hardness of learning with errors
From MaRDI portal
Publication:5495828
DOI10.1145/2488608.2488680zbMath1293.68159arXiv1306.0281OpenAlexW2089477764WikidataQ57484383 ScholiaQ57484383MaRDI QIDQ5495828
Zvika Brakerski, Chris Peikert, Damien Stehlé, Adeline Roux-Langlois, Oded Regev
Publication date: 7 August 2014
Published in: Proceedings of the forty-fifth annual ACM symposium on Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1306.0281
Analysis of algorithms and problem complexity (68Q25) Cryptography (94A60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (only showing first 100 items - show all)
Adaptive Simulation Security for Inner Product Functional Encryption ⋮ Constraining and Watermarking PRFs from Milder Assumptions ⋮ Almost Tight Security in Lattices with Polynomial Moduli – PRF, IBE, All-but-many LTF, and More ⋮ Fully Homomorphic Encryption with Auxiliary Inputs ⋮ Trapdoors for Ideal Lattices with Applications ⋮ Towards a Simpler Lattice Gadget Toolkit ⋮ Classical Verification of Quantum Computations ⋮ Lattice-Based Group Encryption with Full Dynamicity and Message Filtering Policy ⋮ Faster Dual Lattice Attacks for Solving LWE with Applications to CRYSTALS ⋮ Batch bootstrapping. I: A new framework for SIMD bootstrapping in polynomial modulus ⋮ Just how hard are rotations of \(\mathbb{Z}^n\)? Algorithms and cryptography with the simplest lattice ⋮ Privately puncturing PRFs from lattices: adaptive security and collusion resistant pseudorandomness ⋮ Efficient FHEW bootstrapping with small evaluation keys, and applications to threshold homomorphic encryption ⋮ A thorough treatment of highly-efficient NTRU instantiations ⋮ Solving LWR via BDD Strategy: Modulus Switching Approach ⋮ Fiat-Shamir signatures based on module-NTRU ⋮ Relaxed Lattice-Based Signatures with Short Zero-Knowledge Proofs ⋮ More efficient adaptively secure lattice-based IBE with equality test in the standard model ⋮ Classical reduction of gap SVP to LWE: a concrete security analysis ⋮ Lattice-based signatures with tight adaptive corruptions and more ⋮ mrNISC from LWE with polynomial modulus ⋮ mrNISC from LWE with polynomial modulus ⋮ \textsc{Hawk}: module LIP makes lattice signatures fast, compact and simple ⋮ New and improved constructions for partially equivocable public key encryption ⋮ Full quantum equivalence of group action DLog and CDH, and more ⋮ Another round of breaking and making quantum money: how to not build it from lattices, and more ⋮ Generic constructions of master-key KDM secure attribute-based encryption ⋮ Balanced non-adjacent forms ⋮ Leveled Hierarchical Identity-Based Fully Homomorphic Encryption from Learning with Rounding ⋮ How to sample a discrete Gaussian (and more) from a random oracle ⋮ Entropic hardness of Module-LWE from module-NTRU ⋮ Generic construction of trace-and-revoke inner product functional encryption ⋮ Quantum search-to-decision reduction for the LWE problem ⋮ Toward practical lattice-based proof of knowledge from Hint-MLWE ⋮ Lattice-based authenticated key exchange with tight security ⋮ A lower bound for proving hardness of learning with rounding with polynomial modulus ⋮ Hardness of (M)LWE with semi-uniform seeds ⋮ Collusion Resistant Traitor Tracing from Learning with Errors ⋮ Just Take the Average! An Embarrassingly Simple $2^n$-Time Algorithm for SVP (and CVP) ⋮ Ring Packing and Amortized FHEW Bootstrapping ⋮ LP Solutions of Vectorial Integer Subset Sums – Cryptanalysis of Galbraith’s Binary Matrix LWE ⋮ Private Puncturable PRFs from Standard Lattice Assumptions ⋮ Constraint-Hiding Constrained PRFs for NC $$^1$$ from LWE ⋮ On Dual Lattice Attacks Against Small-Secret LWE and Parameter Choices in HElib and SEAL ⋮ Watermarking cryptographic functionalities from standard lattice assumptions ⋮ Multi-theorem preprocessing NIZKs from lattices ⋮ Tighter security proofs for GPV-IBE in the quantum random oracle model ⋮ Adaptive oblivious transfer with access control from lattice assumptions ⋮ Integer Version of Ring-LWE and Its Applications ⋮ Classical Homomorphic Encryption for Quantum Circuits ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Quantum Hardness of Learning Shallow Classical Circuits ⋮ The Complexity of Public-Key Cryptography ⋮ Homomorphic Encryption ⋮ 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 ⋮ Compact ring signatures from learning with errors ⋮ A black-box approach to post-quantum zero-knowledge in constant rounds ⋮ On solving LPN using BKW and variants, Implementation and analysis ⋮ On the hardness of module-LWE with binary secret ⋮ How to meet ternary LWE keys ⋮ Smoothing out binary linear codes and worst-case sub-exponential hardness for LPN ⋮ SO-CCA secure PKE from pairing based all-but-many lossy trapdoor functions ⋮ Attribute-based signatures from lattices: unbounded attributes and semi-adaptive security ⋮ 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 ⋮ Error analysis of weak poly-LWE instances ⋮ Universal product learning with errors: a new variant of \textsf{LWE} for lattice-based cryptography ⋮ 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 ⋮ 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 ⋮ On the ring-LWE and polynomial-LWE problems ⋮ On the Efficacy of Solving LWE by Reduction to Unique-SVP ⋮ Secure Statistical Analysis Using RLWE-Based Homomorphic Encryption ⋮ 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 ⋮ FHEW with Efficient Multibit Bootstrapping ⋮ Efficient and fully secure lattice-based IBE with equality test ⋮ Augmented Learning with Errors: The Untapped Potential of the Error Term ⋮ On the hardness of module learning with errors with short distributions ⋮ Scalable zero knowledge via cycles of elliptic curves ⋮ Hardness of \(k\)-LWE and applications in traitor tracing ⋮ 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 ⋮ On the asymptotic complexity of solving LWE ⋮ Computational fuzzy extractor from LWE ⋮ Faster Fully Homomorphic Encryption: Bootstrapping in Less Than 0.1 Seconds ⋮ 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
This page was built for publication: Classical hardness of learning with errors
