Worst‐Case to Average‐Case Reductions Based on Gaussian Measures
From MaRDI portal
Publication:5454252
DOI10.1137/S0097539705447360zbMath1142.68037OpenAlexW1994790157MaRDI QIDQ5454252
Daniele Micciancio, Oded Regev
Publication date: 28 March 2008
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0097539705447360
Analysis of algorithms and problem complexity (68Q25) Lattices and convex bodies (number-theoretic aspects) (11H06)
Related Items
PAKEs: New Framework, New Techniques and More Efficient Lattice-Based Constructions in the Standard Model ⋮ Improved Discrete Gaussian and Subgaussian Analysis for Lattice Cryptography ⋮ Isochronous Gaussian Sampling: From Inception to Implementation ⋮ No cutoff for circulants: an elementary proof ⋮ Provably Weak Instances of Ring-LWE ⋮ On ideal lattices, Gröbner bases and generalized hash functions ⋮ Sampling from Arbitrary Centered Discrete Gaussians for Lattice-Based Cryptography ⋮ Two-Round Oblivious Linear Evaluation from Learning with Errors ⋮ A Fast Phase-based Enumeration Algorithm for SVP Challenge Through $$y$$-Sparse Representations of Short Lattice Vectors ⋮ Ring Trapdoor Redactable Signatures from Lattice ⋮ Augmented Learning with Errors: The Untapped Potential of the Error Term ⋮ An Inequality for Gaussians on Lattices ⋮ Functional commitments for all functions, with transparent setup and from SIS ⋮ Towards Tightly Secure Lattice Short Signature and Id-Based Encryption ⋮ Multi-key Homomorphic Authenticators ⋮ Just how hard are rotations of \(\mathbb{Z}^n\)? Algorithms and cryptography with the simplest lattice ⋮ \texttt{POLKA}: towards leakage-resistant post-quantum CCA-secure public key encryption ⋮ Shorter hash-and-sign lattice-based signatures ⋮ On codes and learning with errors over function fields ⋮ Fiat-Shamir signatures based on module-NTRU ⋮ The gap is sensitive to size of preimages: collapsing property doesn't go beyond quantum collision-resistance for preimages bounded hash functions ⋮ Puncturable signature: a generic construction and instantiations ⋮ Zero-knowledge arguments for lattice-based accumulators: logarithmic-size ring signatures and group signatures without trapdoors ⋮ Lattice-based signatures with tight adaptive corruptions and more ⋮ Efficient lattice-based blind signatures via Gaussian one-time signatures ⋮ Revocable identity-based fully homomorphic signature scheme with signing key exposure resistance ⋮ \textsc{Hawk}: module LIP makes lattice signatures fast, compact and simple ⋮ Identity-based interactive aggregate signatures from lattices ⋮ Preimage sampling in the higher-bit approximate setting with a non-spherical Gaussian sampler ⋮ The state of the union: union-only signatures for data aggregation ⋮ Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\) ⋮ (Inner-product) functional encryption with updatable ciphertexts ⋮ Lattice signature with efficient protocols, application to anonymous credentials ⋮ A framework for practical anonymous credentials from lattices ⋮ Finding short integer solutions when the modulus is small ⋮ Generic constructions of master-key KDM secure attribute-based encryption ⋮ Multikey Fully Homomorphic Encryption and Applications ⋮ A fully secure lattice-based signcryption with designated equality test in standard model ⋮ On the hardness of the NTRU problem ⋮ Forward-secure revocable secret handshakes from lattices ⋮ Public-key encryption from homogeneous CLWE ⋮ Entropic hardness of Module-LWE from module-NTRU ⋮ Lattice-based programmable hash functions and applications ⋮ Concrete security from worst-case to average-case lattice reductions ⋮ Compact lattice gadget and its applications to hash-and-sign signatures ⋮ Toward practical lattice-based proof of knowledge from Hint-MLWE ⋮ Lattice-based authenticated key exchange with tight security ⋮ \textsf{DualMS}: efficient lattice-based two-round multi-signature with trapdoor-free simulation ⋮ \(\mathrm{mR}_{\mathrm{LWE}}\)-CP-ABE: a revocable CP-ABE for post-quantum cryptography ⋮ Some questions related to the reverse Minkowski theorem ⋮ Attacks on the Search RLWE Problem with Small Errors ⋮ Provably Secure Password Authenticated Key Exchange Based on RLWE for the Post-Quantum World ⋮ Collusion Resistant Traitor Tracing from Learning with Errors ⋮ Explicit Hard Instances of the Shortest Vector Problem ⋮ Analysis of Error Terms of Signatures Based on Learning with Errors ⋮ Drawing Bobbin Lace Graphs, or, Fundamental Cycles for a Subclass of Periodic Graphs ⋮ Two Efficient Tag-Based Encryption Schemes on Lattices ⋮ Simplified Revocable Hierarchical Identity-Based Encryption from Lattices ⋮ Lattice-Based Group Signatures with Verifier-Local Revocation: Achieving Shorter Key-Sizes and Explicit Traceability with Ease ⋮ Discrete Gaussian Distributions via Theta Functions ⋮ Identity-based blind signature from lattices ⋮ Improved Zero-Knowledge Proofs of Knowledge for the ISIS Problem, and Applications ⋮ On the Semantic Security of Functional Encryption Schemes ⋮ Provably Secure NTRU Instances over Prime Cyclotomic Rings ⋮ Revisiting Lattice Attacks on Overstretched NTRU Parameters ⋮ Constraint-Hiding Constrained PRFs for NC $$^1$$ from LWE ⋮ Improved Zero-Knowledge Identification with Lattices ⋮ Cryptographic Functions from Worst-Case Complexity Assumptions ⋮ Concurrently Secure Identification Schemes Based on the Worst-Case Hardness of Lattice Problems ⋮ Lattice-Based Identification Schemes Secure Under Active Attacks ⋮ 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 ⋮ Predicting Lattice Reduction ⋮ Integer Version of Ring-LWE and Its Applications ⋮ An Approximation of Theta Functions with Applications to Communications ⋮ The Geometry of Lattice Cryptography ⋮ A time-distance trade-off for GDD with preprocessing: instantiating the DLW heuristic ⋮ Kissing Numbers and Transference Theorems from Generalized Tail Bounds ⋮ Deterministic Construction of an Approximate M-Ellipsoid and its Application to Derandomizing Lattice Algorithms ⋮ Unnamed Item ⋮ Mixing time and eigenvalues of the abelian sandpile Markov chain ⋮ The Restricted Isometry Property of Subsampled Fourier Matrices ⋮ Measure inequalities and the transference theorem in the geometry of numbers ⋮ Lattice-based linearly homomorphic signature scheme over binary field ⋮ Homomorphic Encryption ⋮ SLIDE REDUCTION, SUCCESSIVE MINIMA AND SEVERAL APPLICATIONS ⋮ Separating Semantic and Circular Security for Symmetric-Key Bit Encryption from the Learning with Errors Assumption ⋮ Lattice-based key exchange on small integer solution problem ⋮ A tighter proof for CCA secure inner product functional encryption: genericity meets efficiency ⋮ On the hardness of module-LWE with binary secret ⋮ Efficient multi-party concurrent signature from lattices ⋮ Counterexamples to new circular security assumptions underlying iO ⋮ Lower bounds on lattice sieving and information set decoding ⋮ 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 ⋮ An improved exact sampling algorithm for the standard normal distribution ⋮ Two-message statistically sender-private OT from LWE ⋮ Adaptively secure distributed PRFs from LWE ⋮ Lattice-based certificateless encryption scheme ⋮ Homomorphic AES evaluation using the modified LTV scheme ⋮ On the higher-bit version of approximate inhomogeneous short integer solution problem ⋮ Gadget-based iNTRU lattice trapdoors ⋮ Lattice-based IBE with equality test supporting flexible authorization in the standard model ⋮ On the ring-LWE and polynomial-LWE problems ⋮ Faster Gaussian sampling for trapdoor lattices with arbitrary modulus ⋮ Non-commutative ring learning with errors from cyclic algebras ⋮ Post-quantum cryptography: lattice signatures ⋮ Lattice-based public-key encryption with equality test supporting flexible authorization in standard model ⋮ Asymptotically quasi-optimal cryptography ⋮ Batch-OT with optimal rate ⋮ Quantum algorithms for variants of average-case lattice problems via filtering ⋮ On the lattice isomorphism problem, quadratic forms, remarkable lattices, and cryptography ⋮ Quantum lightning never strikes the same state twice. Or: quantum money from cryptographic assumptions ⋮ Scalable revocable identity-based signature over lattices in the standard model ⋮ Lattice trapdoors and IBE from middle-product LWE ⋮ A pseudorandom number generator based on worst-case lattice problems ⋮ Discrete Gaussian measures and new bounds of the smoothing parameter for lattices ⋮ On the smoothing parameter and last minimum of random orthogonal lattices ⋮ Asymptotically efficient lattice-based digital signatures ⋮ Bonsai trees, or how to delegate a lattice basis ⋮ New transference theorems on lattices possessing \(n^\varepsilon\)-unique shortest vectors ⋮ More efficient construction of anonymous signatures ⋮ Secret computation of purchase history data using somewhat homomorphic encryption ⋮ On the number of lattice points in a small sphere and a recursive lattice decoding algorithm ⋮ On the hardness of module learning with errors with short distributions ⋮ Hardness of \(k\)-LWE and applications in traitor tracing ⋮ A polynomial time algorithm for GapCVPP in \(l_1\) norm ⋮ On the asymptotic complexity of solving LWE ⋮ The hunting of the SNARK ⋮ Security considerations for Galois non-dual RLWE families ⋮ Non-committing encryption with constant ciphertext expansion from standard assumptions ⋮ Towards classical hardness of module-LWE: the linear rank case ⋮ Computational indistinguishability between quantum states and its cryptographic application ⋮ Incremental symmetric puncturable encryption with support for unbounded number of punctures ⋮ Vector and functional commitments from lattices ⋮ On the probability of generating a lattice ⋮ Polar sampler: a novel Bernoulli sampler using polar codes with application to integer Gaussian sampling ⋮ Practical fully secure unrestricted inner product functional encryption modulo \(p\) ⋮ STP-LWE: A variant of learning with error for a flexible encryption ⋮ An efficient homomorphic aggregate signature scheme based on lattice ⋮ An efficient and batch verifiable conditional privacy-preserving authentication scheme for VANETs using lattice ⋮ Provably secure NTRUEncrypt over any cyclotomic field ⋮ Trapdoor delegation and HIBE from middle-product LWE in standard model ⋮ Strongly secure authenticated key exchange from factoring, codes, and lattices ⋮ Efficient public-key encryption with equality test from lattices ⋮ On a certain class of positive definite functions and measures on locally compact abelian groups and inner-product spaces ⋮ A simple provably secure AKE from the LWE problem ⋮ Improved security proofs in lattice-based cryptography: using the Rényi divergence rather than the statistical distance ⋮ Generating shorter bases for hard random lattices ⋮ Confined guessing: new signatures from standard assumptions ⋮ Towards a ring analogue of the leftover hash lemma ⋮ Identity-based proxy re-signatures from lattices ⋮ A lattice-based signcryption scheme without random oracles ⋮ Adaptively secure distributed PRFs from \(\mathsf{LWE}\) ⋮ Adaptively secure lattice-based revocable IBE in the QROM: compact parameters, tight security, and anonymity ⋮ Modular lattice signatures, revisited ⋮ An efficient anti-quantum lattice-based blind signature for blockchain-enabled systems ⋮ Key recovery from Gram-Schmidt norm leakage in hash-and-sign signatures over NTRU lattices ⋮ Tweaking the asymmetry of asymmetric-key cryptography on lattices: KEMs and signatures of smaller sizes ⋮ MPSign: a signature from small-secret middle-product learning with errors ⋮ Decentralized multi-authority \textbf{\textsf{ABE}} for \textbf{\textsf{DNF}}s from \textbf{\textsf{LWE}} ⋮ A \(2^{n/2}\)-time algorithm for \(\sqrt{n} \)-SVP and \(\sqrt{n} \)-Hermite SVP, and an improved time-approximation tradeoff for (H)SVP ⋮ New lattice two-stage sampling technique and its applications to functional encryption -- stronger security and smaller ciphertexts ⋮ Multiparty reusable non-interactive secure computation from LWE ⋮ Chosen ciphertext attacks secure inner-product functional encryption from learning with errors assumption ⋮ Non-interactive CCA2-secure threshold cryptosystems: achieving adaptive security in the standard model without pairings ⋮ How (Not) to Instantiate Ring-LWE ⋮ FHE Circuit Privacy Almost for Free ⋮ Circular Security Separations for Arbitrary Length Cycles from LWE ⋮ Programmable Hash Functions from Lattices: Short Signatures and IBEs with Small Key Sizes ⋮ Wildcarded identity-based encryption from lattices ⋮ Chosen-ciphertext lattice-based public key encryption with equality test in standard model ⋮ A new Gaussian sampling for trapdoor lattices with arbitrary modulus ⋮ Lattice-based revocable certificateless signature ⋮ Strongly unforgeable ring signature scheme from lattices in the standard model ⋮ On the rejection rate of exact sampling algorithm for discrete Gaussian distributions over the integers ⋮ Lattice reduction for modules, or how to reduce ModuleSVP to ModuleSVP ⋮ Random self-reducibility of ideal-SVP via Arakelov random walks ⋮ LWE with side information: attacks and concrete security estimation ⋮ Worst-case to average-case reductions for module lattices ⋮ Implementation of lattice trapdoors on modules and applications ⋮ Short identity-based signatures with tight security from lattices ⋮ Secure hybrid encryption in the standard model from hard learning problems ⋮ On the quantum complexity of the continuous hidden subgroup problem ⋮ Hardness of LWE on general entropic distributions ⋮ Integral matrix Gram root and lattice Gaussian sampling without floats
