On Ideal Lattices and Learning with Errors over Rings

DOI10.1007/978-3-642-13190-5_1zbMath1279.94099WikidataQ57484385 ScholiaQ57484385MaRDI QIDQ3563827

Vadim Lyubashevsky, Chris Peikert, Oded Regev

Publication date: 1 June 2010

Published in: Advances in Cryptology – EUROCRYPT 2010 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-13190-5_1

Mathematics Subject Classification ID

94A60: Cryptography

68P25: Data encryption (aspects in computer science)

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

81P94: Quantum cryptography (quantum-theoretic aspects)

Related Items

A new lattice-based online/offline signatures framework for low-power devices, Polar coding for ring-LWE-based public key encryption, Dilithium for memory constrained devices, Lattice-Based Proof of a Shuffle, Lockable obfuscation from circularly insecure fully homomorphic encryption, Efficient lattice-based inner-product functional encryption, Quantum rewinding for many-round protocols, Entropic hardness of Module-LWE from module-NTRU, Lattice-based public key cryptosystems invoking linear mapping mask, Batched fully dynamic multi-key FHE from FHEW-like cryptosystems, Secure Implementation of Lattice-Based Encryption Schemes, Lattice-based programmable hash functions and applications, Lattice-based cryptography: a survey, Concrete security from worst-case to average-case lattice reductions, Finding and evaluating parameters for BGV, Fast blind rotation for bootstrapping FHEs, HERMES: efficient ring packing using MLWE ciphertexts and application to transciphering, Accelerating HE operations from key decomposition technique, Compact lattice gadget and its applications to hash-and-sign signatures, Lattice-based timed cryptography, Reductions from module lattices to free module lattices, and application to dequantizing module-LLL, Subfield algorithms for ideal- and module-SVP based on the decomposition group, Adelic Rogers integral formula, Hardness of (M)LWE with semi-uniform seeds, (Leveled) Fully Homomorphic Encryption without Bootstrapping, Structural cryptanalysis of McEliece schemes with compact keys, Polly cracker, revisited, Homomorphic AES evaluation using the modified LTV scheme, ETRU: NTRU over the Eisenstein integers, Strongly secure authenticated key exchange from factoring, codes, and lattices, Sampling from discrete Gaussians for lattice-based cryptography on a constrained device, A new scale-invariant homomorphic encryption scheme, SoK: how (not) to design and implement post-quantum cryptography, On the hardness of module-LWE with binary secret, Secret computation of purchase history data using somewhat homomorphic encryption, Cryptanalysis of a public key cryptosystem based on Diophantine equations via weighted LLL reduction, LWE without modular reduction and improved side-channel attacks against BLISS, Review of cryptographic schemes applied to remote electronic voting systems: remaining challenges and the upcoming post-quantum paradigm, Memory lower bounds of reductions revisited, Short, invertible elements in partially splitting cyclotomic rings and applications to lattice-based zero-knowledge proofs, The closest vector problem in tensored root lattices of type A and in their duals, Efficient authentication from hard learning problems, Post-quantum key exchange for the Internet and the open quantum safe project, An efficient quantum somewhat homomorphic symmetric searchable encryption, Assessing the feasibility of single trace power analysis of Frodo, Analysis of error-correcting codes for lattice-based key exchange, Provably secure NTRUEncrypt over any cyclotomic field, Efficient reductions in cyclotomic rings -- application to Ring LWE based FHE schemes, HILA5: on reliability, reconciliation, and error correction for Ring LWE encryption, Bonsai trees, or how to delegate a lattice basis, Functional encryption for cubic polynomials and implementation, A simple provably secure AKE from the LWE problem, CHIMERA: combining ring-LWE-based fully homomorphic encryption schemes, A framework for cryptographic problems from linear algebra, Towards isogeny-based password-authenticated key establishment, Discretisation and product distributions in ring-LWE, (In)security of ring-LWE under partial key exposure, On the condition number of the Vandermonde matrix of the \(n\)th cyclotomic polynomial, Limits on the efficiency of (ring) LWE-based non-interactive key exchange, (One) failure is not an option: bootstrapping the search for failures in lattice-based encryption schemes, Tweaking the asymmetry of asymmetric-key cryptography on lattices: KEMs and signatures of smaller sizes, On the ideal shortest vector problem over random rational primes, On the integer polynomial learning with errors problem, Round-optimal verifiable oblivious pseudorandom functions from ideal lattices, LWE from non-commutative group rings, Chosen-ciphertext lattice-based public key encryption with equality test in standard model, Fast reduction of algebraic lattices over cyclotomic fields, Lattice reduction for modules, or how to reduce ModuleSVP to ModuleSVP, Rounding in the rings, A non-PCP approach to succinct quantum-safe zero-knowledge, Practical product proofs for lattice commitments, Revocable hierarchical attribute-based signatures from lattices, Bootstrapping for approximate homomorphic encryption with negligible failure-probability by using sparse-secret encapsulation, Efficient and tight oblivious transfer from PKE with tight multi-user security, Distinguishing attack on the NTRUCipher encryption scheme, Revocable hierarchical identity-based authenticated key exchange, Efficient homomorphic conversion between (ring) LWE ciphertexts, Quantum key search for ternary LWE, Implementation of lattice trapdoors on modules and applications, How to meet ternary LWE keys, Lower bounds on lattice sieving and information set decoding, A trace map attack against special ring-LWE samples, FFT program generation for ring LWE-based cryptography, Succinct non-interactive arguments via linear interactive proofs, Universal product learning with errors: a new variant of \textsf{LWE} for lattice-based cryptography, Improved attacks against key reuse in learning with errors key exchange, An extension of Kannan's embedding for solving ring-based LWE problems, When HEAAN meets FV: a new somewhat homomorphic encryption with reduced memory overhead, The matrix reloaded: multiplication strategies in FrodoKEM, On the higher-bit version of approximate inhomogeneous short integer solution problem, Gadget-based iNTRU lattice trapdoors, Adaptively secure laconic function evaluation for \(\mathsf{NC}^1\), Application of automorphic forms to lattice problems, Non-commutative ring learning with errors from cyclic algebras, Vandermonde meets Regev: public key encryption schemes based on partial Vandermonde problems, Unified program generation and verification: a case study on number-theoretic transform, Lattice-based public-key encryption with equality test supporting flexible authorization in standard model, Tightly secure ring-LWE based key encapsulation with short ciphertexts, A Ring-LWE-based digital signature inspired by Lindner-Peikert scheme, The polynomial learning with errors problem and the smearing condition, Asymptotically quasi-optimal cryptography, Limits of polynomial packings for \(\mathbb{Z}_{p^k}\) and \(\mathbb{F}_{p^k}\), Anonymity of NIST PQC round 3 KEMs, Lattice trapdoors and IBE from middle-product LWE, Efficiently processing complex-valued data in homomorphic encryption, Flattening NTRU for evaluation key free homomorphic encryption, D-NTRU: more efficient and average-case IND-CPA secure NTRU variant, Security estimates of a ring-LWE symmetric cryptosystem against chosen plaintext attack, Trapdoor delegation and HIBE from middle-product LWE in standard model, The lattice-based digital signature scheme qTESLA, Extremal set theory and LWE based access structure hiding verifiable secret sharing with malicious-majority and free verification, TFHE: fast fully homomorphic encryption over the torus, Tightly secure signature schemes from the LWE and subset sum assumptions, Lattice-based revocable certificateless signature, Practical \(\mathsf{MP} \text{- }\mathsf{LWE}\)-based encryption balancing security-risk versus efficiency, Strongly leakage resilient authenticated key exchange, revisited, Hardness of learning problems over Burnside groups of exponent 3, Worst-case to average-case reductions for module lattices, Survey of information security, Asymptotically efficient lattice-based digital signatures, Comparison analysis of Ding's RLWE-based key exchange protocol and NewHope variants, Ideal forms of Coppersmith's theorem and Guruswami-Sudan list decoding, An efficient CCA-secure cryptosystem over ideal lattices from identity-based encryption, Error analysis of weak poly-LWE instances, Multikey Fully Homomorphic Encryption and Applications, Packed Ciphertexts in LWE-Based Homomorphic Encryption, Improved (Hierarchical) Inner-Product Encryption from Lattices, Unnamed Item, Private Conjunctive Query over Encrypted Data, Privacy-Friendly Forecasting for the Smart Grid Using Homomorphic Encryption and the Group Method of Data Handling, Algebraic Aspects of Solving Ring-LWE, Including Ring-Based Improvements in the Blum--Kalai--Wasserman Algorithm, Pseudorandom Functions: Three Decades Later, Computational quantum key distribution (CQKD) on decentralized ledger and blockchain, RLWE/PLWE equivalence for totally real cyclotomic subextensions via quasi-Vandermonde matrices, Efficient Password-Authenticated Key Exchange from RLWE Based on Asymmetric Key Consensus, Limits on the Efficiency of (Ring) LWE Based Non-interactive Key Exchange, Efficient Post-quantum SNARKs for RSIS and RLWE and Their Applications to Privacy, A Lattice-Based Approach to Privacy-Preserving Biometric Authentication Without Relying on Trusted Third Parties, Fast Discretized Gaussian Sampling and Post-quantum TLS Ciphersuite, Sampling from Arbitrary Centered Discrete Gaussians for Lattice-Based Cryptography, Multitarget Decryption Failure Attacks and Their Application to Saber and Kyber, A Novel Certificateless Multi-signature Scheme over NTRU Lattices, On the Scaled Inverse of $(x^i-x^j)$ modulo Cyclotomic Polynomial of the form $\Phi_{p^s}(x)$ or $\Phi_{p^s q^t}(x)$, Integer Version of Ring-LWE and Its Applications, Lattice-Based SNARGs and Their Application to More Efficient Obfuscation, LP Solutions of Vectorial Integer Subset Sums – Cryptanalysis of Galbraith’s Binary Matrix LWE, Provably Secure NTRU Instances over Prime Cyclotomic Rings, On Dual Lattice Attacks Against Small-Secret LWE and Parameter Choices in HElib and SEAL, Tighter security proofs for GPV-IBE in the quantum random oracle model, Minicrypt primitives with algebraic structure and applications, On ideal class group computation of imaginary multiquadratic fields, A Systematic Approach and Analysis of Key Mismatch Attacks on Lattice-Based NIST Candidate KEMs, Batch bootstrapping. I: A new framework for SIMD bootstrapping in polynomial modulus, Batch bootstrapping. II: Bootstrapping in polynomial modulus only requires \(\tilde{O}(1)\) FHE multiplications in amortization, On homomorphic secret sharing from polynomial-modulus LWE, Discretization error reduction for high precision torus fully homomorphic encryption, Optimisations and tradeoffs for HElib, Efficient FHEW bootstrapping with small evaluation keys, and applications to threshold homomorphic encryption, A thorough treatment of highly-efficient NTRU instantiations, \texttt{POLKA}: towards leakage-resistant post-quantum CCA-secure public key encryption, Lattice-based zero-knowledge proofs and applications: shorter, simpler, and more general, 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 Evaluation of Low Degree Multivariate Polynomials in Ring-LWE Homomorphic Encryption Schemes, Fiat-Shamir signatures based on module-NTRU, Verifiable Decryption for Fully Homomorphic Encryption, Parameter optimization and larger precision for (T)FHE, Lattice-based signatures with tight adaptive corruptions and more, Homomorphic encryption: a mathematical survey, Multi-key fully homomorphic encryption from NTRU and (R)LWE with faster bootstrapping, \textsc{Hawk}: module LIP makes lattice signatures fast, compact and simple, Subfield attacks on HSVP in ideal lattices, Identity-based interactive aggregate signatures from lattices, Towards case-optimized hybrid homomorphic encryption. Featuring the \textsf{Elisabeth} stream cipher, Log-\(\mathcal{S}\)-unit lattices using explicit Stickelberger generators to solve approx ideal-SVP, On module unique-SVP and NTRU, On the hardness of the NTRU problem, Fault-injection attacks against NIST's post-quantum cryptography round 3 KEM candidates, Transciphering framework for approximate homomorphic encryption, Improved programmable bootstrapping with larger precision and efficient arithmetic circuits for TFHE, Bootstrapping for helib, On the RLWE/PLWE equivalence for cyclotomic number fields, 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, A novel identity-based multi-signature scheme over NTRU lattices, On optimizing electricity markets performance, Improving speed and security in updatable encryption schemes, 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, Cryptographic group actions and applications, Ring-based identity based encryption -- asymptotically shorter MPK and tighter security, Recovery attack on Bob's reused randomness in CRYSTALS-KYBER and SABER, Polar sampler: a novel Bernoulli sampler using polar codes with application to integer Gaussian sampling, Post-Quantum Cryptography: State of the Art, The Whole is Less Than the Sum of Its Parts: Constructing More Efficient Lattice-Based AKEs, Three’s Compromised Too: Circular Insecurity for Any Cycle Length from (Ring-)LWE, Programmable Hash Functions from Lattices: Short Signatures and IBEs with Small Key Sizes, A Subfield Lattice Attack on Overstretched NTRU Assumptions, Cryptography from Learning Parity with Noise, High-Performance Ideal Lattice-Based Cryptography on 8-Bit ATxmega Microcontrollers, Efficient Integer Encoding for Homomorphic Encryption via Ring Isomorphisms, Augmented Learning with Errors: The Untapped Potential of the Error Term, Signature Schemes with Efficient Protocols and Dynamic Group Signatures from Lattice Assumptions, Partitioning via Non-linear Polynomial Functions: More Compact IBEs from Ideal Lattices and Bilinear Maps, Faster Fully Homomorphic Encryption: Bootstrapping in Less Than 0.1 Seconds, Provably Secure Password Authenticated Key Exchange Based on RLWE for the Post-Quantum World, Fully Homomorphic Encryption for Point Numbers, A Practical Post-Quantum Public-Key Cryptosystem Based on $$\textsf {spLWE}$$, Better Key Sizes (and Attacks) for LWE-Based Encryption, The Geometry of Lattice Cryptography, Generalized Learning Problems and Applications to Non-commutative Cryptography, Blending FHE-NTRU Keys – The Excalibur Property, Approximate-Deterministic Public Key Encryption from Hard Learning Problems, Secure Statistical Analysis Using RLWE-Based Homomorphic Encryption, BI-NTRU Encryption Schemes: Two New Secure Variants of NTRU, Bi-homomorphic Lattice-Based PRFs and Unidirectional Updatable Encryption, Practical Fully Homomorphic Encryption for Fully Masked Neural Networks, Improved Multiplication Triple Generation over Rings via RLWE-Based AHE, Integer Reconstruction Public-Key Encryption, Trapdoors for Ideal Lattices with Applications, Provably Weak Instances of Ring-LWE