On the hardness of learning with errors with binary secrets

DOI10.4086/TOC.2018.V014A013MaRDI QIDQ4612477zbMATH OpenOpenAlexFDO

Authors Daniele Micciancio

Publication date 31 January 2019

Published in Theory of Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4086/toc.2018.v014a013

zbMATH Keywords

latticelearningcomplexity theorycryptographypseudorandomnessLWE

Mathematics Subject Classification ID

Cryptography (94A60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Lattices and convex bodies in (n) dimensions (aspects of discrete geometry) (52C07) Lattices and convex bodies (number-theoretic aspects) (11H06)

Recommendations

• Classical hardness of learning with errors
• Revisiting the hardness of binary error LWE
• On the hardness of module-LWE with binary secret
• On the concrete hardness of learning with errors
• Lattice decoding attacks on binary LWE

Cites work

• A Pseudorandom Generator from any One-way Function
• An improved BKW algorithm for LWE with applications to cryptography and lattices
• Classical hardness of learning with errors
• Fast Cryptographic Primitives and Circular-Secure Encryption Based on Hard Learning Problems
• Faster fully homomorphic encryption: bootstrapping in less than 0.1 seconds
• Generalized compact knapsacks, cyclic lattices, and efficient one-way functions
• Lattice decoding attacks on binary LWE
• New Algorithms for Learning in Presence of Errors
• On dual lattice attacks against small-secret LWE and parameter choices in HElib and SEAL
• On ideal lattices and learning with errors over rings
• On lattices, learning with errors, random linear codes, and cryptography
• On the hardness of LWE with binary error: revisiting the hybrid lattice-reduction and meet-in-the-middle attack
• 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
• Trapdoors for hard lattices and new cryptographic constructions
• Worst‐Case to Average‐Case Reductions Based on Gaussian Measures

Cited in

(22)

• On the hardness of module-LWE with binary secret
• TFHE: fast fully homomorphic encryption over the torus
• A framework for cryptographic problems from linear algebra
• On the hardness of LWE with binary error: revisiting the hybrid lattice-reduction and meet-in-the-middle attack
• Classical hardness of learning with errors
• Lattice decoding attacks on binary LWE
• On the multi-user security of LWE-based NIKE
• Hardness of LWE on general entropic distributions
• Entropic hardness of Module-LWE from module-NTRU
• Efficient FHEW bootstrapping with small evaluation keys, and applications to threshold homomorphic encryption
• Towards classical hardness of module-LWE: the linear rank case
• Lattice-Based Secure Biometric Authentication for Hamming Distance
• Tweaking the asymmetry of asymmetric-key cryptography on lattices: KEMs and signatures of smaller sizes
• Hardness of (M)LWE with semi-uniform seeds
• SoK: learning with errors, circular security, and fully homomorphic encryption
• The complexity of algebraic algorithms for LWE
• On the hardness of module learning with errors with short distributions
• A systematic study of sparse LWE
• Revocable policy-based chameleon hash using lattices
• Pseudorandom knapsacks and the sample complexity of LWE search-to-decision reductions
• Revisiting the hardness of binary error LWE
• Sequential half-aggregation of lattice-based signatures

Describes a project that uses

Uses Software

• FHEW

This page was built for publication: On the hardness of learning with errors with binary secrets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4612477)