Pseudorandom Knapsacks and the Sample Complexity of LWE Search-to-Decision Reductions
From MaRDI portal
Publication:5199207
DOI10.1007/978-3-642-22792-9_26zbMath1287.94085OpenAlexW2150624282MaRDI QIDQ5199207
Daniele Micciancio, Petros Mol
Publication date: 12 August 2011
Published in: Advances in Cryptology – CRYPTO 2011 (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-22792-9_26
Related Items
Almost Tight Security in Lattices with Polynomial Moduli – PRF, IBE, All-but-many LTF, and More ⋮ Tightly secure signatures from lossy identification schemes ⋮ Approximate-Deterministic Public Key Encryption from Hard Learning Problems ⋮ Deniable Attribute Based Encryption for Branching Programs from LWE ⋮ Targeted Homomorphic Attribute-Based Encryption ⋮ Vandermonde meets Regev: public key encryption schemes based on partial Vandermonde problems ⋮ Naor-Yung paradigm with shared randomness and applications ⋮ Obfuscated fuzzy Hamming distance and conjunctions from subset product problems ⋮ Lattice-based accumulator with constant time list update and constant time verification ⋮ On the hardness of module learning with errors with short distributions ⋮ Zero-knowledge arguments for lattice-based accumulators: logarithmic-size ring signatures and group signatures without trapdoors ⋮ Candidate witness encryption from lattice techniques ⋮ Quantum search-to-decision reduction for the LWE problem ⋮ A detailed analysis of Fiat-Shamir with aborts ⋮ Almost tight multi-user security under adaptive corruptions from LWE in the standard model ⋮ Indistinguishability obfuscation ⋮ Cryptographic group actions and applications ⋮ On the tightness of forward-secure signature reductions ⋮ Deterministic compression with uncertain priors ⋮ Lattice-based FHE as secure as PKE ⋮ Cryptogenography ⋮ Limits of random oracles in secure computation ⋮ Non-commutative arithmetic circuits with division ⋮ Decision trees, protocols and the entropy-influence conjecture ⋮ Locally testable codes and cayley graphs ⋮ Invitation games and the price of stability ⋮ Welfare maximization and truthfulness in mechanism design with ordinal preferences ⋮ Coordination mechanisms from (almost) all scheduling policies ⋮ Private interactive communication across an adversarial channel ⋮ Tree codes and a conjecture on exponential sums ⋮ Capacity of non-malleable codes ⋮ Linear-time encodable codes meeting the gilbert-varshamov bound and their cryptographic applications ⋮ Adversarial hypothesis testing and a quantum stein's lemma for restricted measurements ⋮ Sequential decision making with vector outcomes ⋮ Learning mixtures of arbitrary distributions over large discrete domains ⋮ Why do simple algorithms for triangle enumeration work in the real world? ⋮ Black-box obfuscation for d-CNFs ⋮ Candidate weak pseudorandom functions in AC 0 ○ MOD 2 ⋮ Iterated group products and leakage resilience against NC1 ⋮ Building one-time memories from isolated qubits ⋮ Attribute-efficient evolvability of linear functions ⋮ Energy-efficient circuit design ⋮ Rate-independent computation in continuous chemical reaction networks ⋮ Testers and their applications ⋮ On the automorphism groups of strongly regular graphs I ⋮ Faster private release of marginals on small databases ⋮ Mechanism design in large games ⋮ Redrawing the boundaries on purchasing data from privacy-sensitive individuals ⋮ Approximation schemes via Sherali-Adams hierarchy for dense constraint satisfaction problems and assignment problems ⋮ Complexity of approximating CSP with balance / hard constraints ⋮ Integer feasibility of random polytopes ⋮ Multireference alignment using semidefinite programming ⋮ Partial tests, universal tests and decomposability ⋮ High dimensional expanders and property testing ⋮ Parameterized testability ⋮ Direct sum fails for zero error average communication ⋮ Rational arguments ⋮ A lattice-based group signature scheme with verifier-local revocation ⋮ Improved security proofs in lattice-based cryptography: using the Rényi divergence rather than the statistical distance ⋮ Pseudo-free families of finite computational elementary abelian \(p\)-groups ⋮ Tighter Reductions for Forward-Secure Signature Schemes ⋮ Private Puncturable PRFs from Standard Lattice Assumptions ⋮ On the structure of Boolean functions with small spectral norm ⋮ The truth behind the myth of the folk theorem ⋮ Expanders with respect to Hadamard spaces and random graphs ⋮ Limits of local algorithms over sparse random graphs ⋮ Watermarking cryptographic functionalities from standard lattice assumptions ⋮ On the Hardness of Learning with Rounding over Small Modulus ⋮ Decompositions of Triangle-Dense Graphs ⋮ Multi-theorem preprocessing NIZKs from lattices ⋮ Verifiable single-server private information retrieval from LWE with binary errors ⋮ Multiparty reusable non-interactive secure computation from LWE ⋮ The Geometry of Lattice Cryptography ⋮ Shorter lattice-based zero-knowledge proofs via one-time commitments ⋮ How (Not) to Instantiate Ring-LWE ⋮ Fully Secure Functional Encryption for Inner Products, from Standard Assumptions ⋮ Circuit-ABE from LWE: Unbounded Attributes and Semi-adaptive Security ⋮ Lattice-based group signatures: achieving full dynamicity (and deniability) with ease ⋮ Lattice-Based Fully Dynamic Multi-key FHE with Short Ciphertexts ⋮ Cryptography with Auxiliary Input and Trapdoor from Constant-Noise LPN ⋮ Unnamed Item ⋮ Tightly secure signature schemes from the LWE and subset sum assumptions ⋮ Rounding in the rings ⋮ Hardness of LWE on general entropic distributions ⋮ Key-homomorphic pseudorandom functions from LWE with small modulus
