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 (only showing first 100 items - show all)

Pseudorandomness of decoding, revisited: adapting OHCP to code-based cryptography ⋮ Too many hints -- when LLL breaks LWE ⋮ Efficient updatable public-key encryption from lattices ⋮ Traceable ring signatures from group actions: logarithmic, flexible, and quantum resistant ⋮ Ring/module learning with errors under linear leakage -- hardness and applications ⋮ Lattice-based threshold, accountable, and private signature ⋮ Lower bounds for lattice-based compact functional encryption ⋮ Evaluating the security of CRYSTALS-Dilithium in the quantum random oracle model ⋮ Crypto dark matter on the torus. Oblivious PRFs from shallow PRFs and TFHE ⋮ SLAP: succinct lattice-based polynomial commitments from standard assumptions ⋮ MODRED: a code-based non-interactive key exchange protocol ⋮ Aggregating Falcon signatures with LaBRADOR ⋮ Plaintext-ciphertext matrix multiplication and FHE bootstrapping: fast and fused ⋮ Greyhound: fast polynomial commitments from lattices ⋮ 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 ⋮ Hardness of entropic module-LWE ⋮ Doubly efficient private information retrieval and fully homomorphic RAM computation from ring LWE ⋮ GeT a CAKE: \underline{Ge}neric \underline{T}ransformations from \underline{K}ey encaspulation mechanisms to password \underline{A}uthenticated \underline{K}ey \underline{E}xchanges ⋮ Identity-based encryption from lattices using approximate trapdoors ⋮ Fractional non-norm elements for division algebras, and an application to cyclic learning with errors ⋮ Sequential half-aggregation of lattice-based signatures ⋮ Covercrypt: an efficient early-abort KEM for hidden access policies with traceability from the DDH and LWE ⋮ Multilinear Schwartz-Zippel \(\operatorname{mod} \mathrm{N}\) and lattice-based succinct arguments ⋮ Concrete analysis of approximate ideal-SIVP to decision ring-LWE reduction ⋮ On the multi-user security of LWE-based NIKE ⋮ Simple threshold (fully homomorphic) encryption from LWE with polynomial modulus ⋮ Algebraically structured LWE, revisited ⋮ Lattice-based polynomial commitments: towards asymptotic and concrete efficiency ⋮ G+G: a Fiat-Shamir lattice signature based on convolved Gaussians ⋮ 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

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

This page was built for publication: Worst-case to average-case reductions for module lattices