Worst-case to average-case reductions for module lattices

DOI10.1007/s10623-014-9938-4zbMath1361.94043OpenAlexW1985439922MaRDI QIDQ2345928

Adeline Roux-Langlois, Damien Stehlé

Publication date: 21 May 2015

Published in: Designs, Codes and Cryptography (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10623-014-9938-4

zbMATH Keywords

ideal latticeslattice-based cryptographyworst-case to average-case reductionsmodule lattices

Mathematics Subject Classification ID

Cryptography (94A60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

SoK: how (not) to design and implement post-quantum cryptography ⋮ On the hardness of module-LWE with binary secret ⋮ Efficient Post-quantum SNARKs for RSIS and RLWE and Their Applications to Privacy ⋮ A compressed \(\varSigma \)-protocol theory for lattices ⋮ A trace map attack against special ring-LWE samples ⋮ Efficient lattice-based polynomial evaluation and batch ZK arguments ⋮ LWE without modular reduction and improved side-channel attacks against BLISS ⋮ An efficient lattice reduction using reuse technique blockwisely on NTRU ⋮ A monolithic hardware implementation of Kyber: comparing apples to apples in PQC candidates ⋮ Practical post-quantum few-time verifiable random function with applications to Algorand ⋮ An extension of Kannan's embedding for solving ring-based LWE problems ⋮ The matrix reloaded: multiplication strategies in FrodoKEM ⋮ Memory lower bounds of reductions revisited ⋮ On the ring-LWE and polynomial-LWE problems ⋮ Short, invertible elements in partially splitting cyclotomic rings and applications to lattice-based zero-knowledge proofs ⋮ Application of automorphic forms to lattice problems ⋮ Non-commutative ring learning with errors from cyclic algebras ⋮ \textsc{Mitaka}: a simpler, parallelizable, maskable variant of \textsc{Falcon} ⋮ Multitarget Decryption Failure Attacks and Their Application to Saber and Kyber ⋮ Algebraically structured LWE. Revisited ⋮ When NTT meets Karatsuba: preprocess-then-NTT technique revisited ⋮ Small leaks sink a great ship: an evaluation of key reuse resilience of PQC third round finalist NTRU-HRSS ⋮ Shorter Lattice-Based Group Signatures via “Almost Free” Encryption and Other Optimizations ⋮ Efficient lattice-based traceable ring signature scheme with its application in blockchain ⋮ On the hardness of module learning with errors with short distributions ⋮ On homomorphic secret sharing from polynomial-modulus LWE ⋮ Partitioning via Non-linear Polynomial Functions: More Compact IBEs from Ideal Lattices and Bilinear Maps ⋮ Systematic study of decryption and re-encryption leakage: the case of Kyber ⋮ Post-quantum anonymity of Kyber ⋮ A thorough treatment of highly-efficient NTRU instantiations ⋮ Lattice-based zero-knowledge proofs and applications: shorter, simpler, and more general ⋮ Lattice-based SNARKs: publicly verifiable, preprocessing, and recursively composable (extended abstract) ⋮ Practical sublinear proofs for R1CS from lattices ⋮ Some easy instances of ideal-SVP and implications on the partial Vandermonde knapsack problem ⋮ On codes and learning with errors over function fields ⋮ Efficient lattice-based blind signatures via Gaussian one-time signatures ⋮ BLOOM: bimodal lattice one-out-of-many proofs and applications ⋮ Identity-based interactive aggregate signatures from lattices ⋮ Towards case-optimized hybrid homomorphic encryption. Featuring the \textsf{Elisabeth} stream cipher ⋮ On module unique-SVP and NTRU ⋮ Lattice signature with efficient protocols, application to anonymous credentials ⋮ A framework for practical anonymous credentials from lattices ⋮ On the hardness of the NTRU problem ⋮ Balanced non-adjacent forms ⋮ Fault-enabled chosen-ciphertext attacks on Kyber ⋮ Dilithium for memory constrained devices ⋮ Entropic hardness of Module-LWE from module-NTRU ⋮ Lattice-based cryptography: a survey ⋮ Concrete security from worst-case to average-case lattice reductions ⋮ HERMES: efficient ring packing using MLWE ciphertexts and application to transciphering ⋮ Reductions from module lattices to free module lattices, and application to dequantizing module-LLL ⋮ Attacks on the Search RLWE Problem with Small Errors ⋮ Hardness of (M)LWE with semi-uniform seeds ⋮ Practical exact proofs from lattices: new techniques to exploit fully-splitting rings ⋮ Towards classical hardness of module-LWE: the linear rank case ⋮ Twisted-PHS: using the product formula to solve approx-SVP in ideal lattices ⋮ Calamari and Falafl: logarithmic (linkable) ring signatures from isogenies and lattices ⋮ On the (M)iNTRU assumption in the integer case ⋮ Assessing the feasibility of single trace power analysis of Frodo ⋮ Provably secure NTRUEncrypt over any cyclotomic field ⋮ Extremal set theory and LWE based access structure hiding verifiable secret sharing with malicious-majority and free verification ⋮ NTRU prime: reducing attack surface at low cost ⋮ Short Stickelberger Class Relations and Application to Ideal-SVP ⋮ Constraint-Hiding Constrained PRFs for NC $$^1$$ from LWE ⋮ Group signatures and more from isogenies and lattices: generic, simple, and efficient ⋮ A framework for cryptographic problems from linear algebra ⋮ Integer Version of Ring-LWE and Its Applications ⋮ Limits on the efficiency of (ring) LWE-based non-interactive key exchange ⋮ TFHE: fast fully homomorphic encryption over the torus ⋮ Homomorphic Evaluation of Lattice-Based Symmetric Encryption Schemes ⋮ (One) failure is not an option: bootstrapping the search for failures in lattice-based encryption schemes ⋮ MPSign: a signature from small-secret middle-product learning with errors ⋮ On the integer polynomial learning with errors problem ⋮ Shorter lattice-based zero-knowledge proofs via one-time commitments ⋮ LWE from non-commutative group rings ⋮ Quantum Hardness of Learning Shallow Classical Circuits ⋮ Practical \(\mathsf{MP} \text{- }\mathsf{LWE}\)-based encryption balancing security-risk versus efficiency ⋮ Fast reduction of algebraic lattices over cyclotomic fields ⋮ Lattice reduction for modules, or how to reduce ModuleSVP to ModuleSVP ⋮ Practical product proofs for lattice commitments ⋮ Lattice-based blind signatures, revisited ⋮ Covert authentication from lattices ⋮ Efficient and tight oblivious transfer from PKE with tight multi-user security ⋮ Efficient homomorphic conversion between (ring) LWE ciphertexts ⋮ Implementation of lattice trapdoors on modules and applications

Uses Software

• NTRU
• ring-LWE

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A generalization of the LLL-algorithm over Euclidean rings or orders
• Limits on the hardness of lattice problems in \(\ell_{p}\) norms
• Generalized compact knapsacks, cyclic lattices, and efficient one-way functions
• On the complexity of computing short linearly independent vectors and short bases in a lattice
• (Leveled) fully homomorphic encryption without bootstrapping
• Hardness of SIS and LWE with Small Parameters
• Subspace LWE
• Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller
• Circular and KDM Security for Identity-Based Encryption
• Efficient Authentication from Hard Learning Problems
• Making NTRU as Secure as Worst-Case Problems over Ideal Lattices
• A Group Signature Scheme from Lattice Assumptions
• Linearly Homomorphic Signatures over Binary Fields and New Tools for Lattice-Based Signatures
• Fast Cryptographic Primitives and Circular-Secure Encryption Based on Hard Learning Problems
• Trapdoors for hard lattices and new cryptographic constructions
• On Ideal Lattices and Learning with Errors over Rings
• An Efficient and Parallel Gaussian Sampler for Lattices
• Generalized Compact Knapsacks Are Collision Resistant
• Lattice-based Cryptography
• Efficient Public Key Encryption Based on Ideal Lattices
• Complex Lattice Reduction Algorithm for Low-Complexity Full-Diversity MIMO Detection
• Almost Perfect Lattices, the Covering Radius Problem, and Applications to Ajtai's Connection Factor
• A Toolkit for Ring-LWE Cryptography
• Short Bases of Lattices over Number Fields
• Advanced Topics in Computional Number Theory
• Public-key cryptosystems from the worst-case shortest vector problem
• Bi-Deniable Public-Key Encryption
• On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption
• Worst‐Case to Average‐Case Reductions Based on Gaussian Measures
• Classical hardness of learning with errors
• Theory of Cryptography
• On lattices, learning with errors, random linear codes, and cryptography
• On lattices, learning with errors, random linear codes, and cryptography