Public-key cryptosystems from the worst-case shortest vector problem
From MaRDI portal
Publication:5172727
DOI10.1145/1536414.1536461zbMath1304.94079OpenAlexW2058785578WikidataQ57484381 ScholiaQ57484381MaRDI QIDQ5172727
Publication date: 4 February 2015
Published in: Proceedings of the forty-first annual ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1536414.1536461
Related Items
Limits on the Efficiency of (Ring) LWE Based Non-interactive Key Exchange ⋮ Constraining and Watermarking PRFs from Milder Assumptions ⋮ Almost Tight Security in Lattices with Polynomial Moduli – PRF, IBE, All-but-many LTF, and More ⋮ Compact Lossy and All-but-One Trapdoor Functions from Lattice ⋮ Fast Discretized Gaussian Sampling and Post-quantum TLS Ciphersuite ⋮ Fully Homomorphic Encryption with Auxiliary Inputs ⋮ Approximate-Deterministic Public Key Encryption from Hard Learning Problems ⋮ Multi-key FHE from LWE, Revisited ⋮ Targeted Homomorphic Attribute-Based Encryption ⋮ Lattice-Based Group Encryption with Full Dynamicity and Message Filtering Policy ⋮ Faster Dual Lattice Attacks for Solving LWE with Applications to CRYSTALS ⋮ Rinocchio: SNARKs for ring arithmetic ⋮ Breaking the \(O(\sqrt{n})\)-bit barrier: Byzantine agreement with polylog bits per party ⋮ Privately puncturing PRFs from lattices: adaptive security and collusion resistant pseudorandomness ⋮ Zero-knowledge arguments for lattice-based accumulators: logarithmic-size ring signatures and group signatures without trapdoors ⋮ Classical reduction of gap SVP to LWE: a concrete security analysis ⋮ Lattice-based signatures with tight adaptive corruptions and more ⋮ mrNISC from LWE with polynomial modulus ⋮ Fully collusion resistant trace-and-revoke functional encryption for arbitrary identities ⋮ mrNISC from LWE with polynomial modulus ⋮ Subfield attacks on HSVP in ideal lattices ⋮ Unnamed Item ⋮ On error distributions in ring-based LWE ⋮ Multi-bit Leveled Homomorphic Encryption via $$\mathsf {Dual.LWE}$$ -Based ⋮ Collusion Resistant Traitor Tracing from Learning with Errors ⋮ 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 ⋮ Two Efficient Tag-Based Encryption Schemes on Lattices ⋮ Bi-homomorphic Lattice-Based PRFs and Unidirectional Updatable Encryption ⋮ New Algorithms for Learning in Presence of Errors ⋮ Packed Ciphertexts in LWE-Based Homomorphic Encryption ⋮ Improved Zero-Knowledge Proofs of Knowledge for the ISIS Problem, and Applications ⋮ Improved (Hierarchical) Inner-Product Encryption from Lattices ⋮ Private Puncturable PRFs from Standard Lattice Assumptions ⋮ Constraint-Hiding Constrained PRFs for NC $$^1$$ from LWE ⋮ Unnamed Item ⋮ 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 ⋮ Multi-theorem preprocessing NIZKs from lattices ⋮ Parallel and concurrent security of the HB and \(HB^{+}\) protocols ⋮ Tighter security proofs for GPV-IBE in the quantum random oracle model ⋮ Better Key Sizes (and Attacks) for LWE-Based Encryption ⋮ Integer Version of Ring-LWE and Its Applications ⋮ Approximating the Closest Vector Problem Using an Approximate Shortest Vector Oracle ⋮ Classical Homomorphic Encryption for Quantum Circuits ⋮ Classical Homomorphic Encryption for Quantum Circuits ⋮ The Geometry of Lattice Cryptography ⋮ Generalized Learning Problems and Applications to Non-commutative Cryptography ⋮ Hardness of bounded distance decoding on lattices in lp norms ⋮ Kissing Numbers and Transference Theorems from Generalized Tail Bounds ⋮ Efficient Threshold Encryption from Lossy Trapdoor Functions ⋮ Unnamed Item ⋮ Threshold Decryption and Zero-Knowledge Proofs for Lattice-Based Cryptosystems ⋮ Public-Key Encryption Schemes with Auxiliary Inputs ⋮ Public-Key Cryptographic Primitives Provably as Secure as Subset Sum ⋮ Quantum Hardness of Learning Shallow Classical Circuits ⋮ The Complexity of Public-Key Cryptography ⋮ Pseudorandom Functions: Three Decades Later ⋮ Homomorphic Encryption ⋮ Separating Semantic and Circular Security for Symmetric-Key Bit Encryption from the Learning with Errors Assumption ⋮ Generic constructions of master-key KDM secure attribute-based encryption ⋮ Candidate witness encryption from lattice techniques ⋮ Securing approximate homomorphic encryption using differential privacy ⋮ Leveled Hierarchical Identity-Based Fully Homomorphic Encryption from Learning with Rounding ⋮ Statistically sender-private OT from LPN and derandomization ⋮ Forward-secure revocable secret handshakes from lattices ⋮ Quantum search-to-decision reduction for the LWE problem ⋮ Lattice-based authenticated key exchange with tight security ⋮ Error correction and ciphertext quantization in lattice cryptography ⋮ Almost tight multi-user security under adaptive corruptions from LWE in the standard model ⋮ A lower bound for proving hardness of learning with rounding with polynomial modulus ⋮ HRA-secure attribute-based threshold proxy re-encryption from lattices ⋮ Hardness of (M)LWE with semi-uniform seeds ⋮ Compact ring signatures from learning with errors ⋮ A black-box approach to post-quantum zero-knowledge in constant rounds ⋮ Lattice-based key exchange on small integer solution problem ⋮ On solving LPN using BKW and variants, Implementation and analysis ⋮ On the hardness of module-LWE with binary secret ⋮ Lattice reduction with approximate enumeration oracles. Practical algorithms and concrete performance ⋮ Smoothing out binary linear codes and worst-case sub-exponential hardness for LPN ⋮ Cryptography from Learning Parity with Noise ⋮ Traitor-tracing from LWE made simple and attribute-based ⋮ Two-message statistically sender-private OT from LWE ⋮ Lattice-based certificateless encryption scheme ⋮ An efficient CCA-secure cryptosystem over ideal lattices from identity-based encryption ⋮ Universal product learning with errors: a new variant of \textsf{LWE} for lattice-based cryptography ⋮ Attribute-based conditional proxy re-encryption in the standard model under LWE ⋮ Lattice-based HRA-secure attribute-based proxy re-encryption in standard model ⋮ Survey of information security ⋮ Puncturable identity-based and attribute-based encryption from lattices ⋮ Toward non-interactive zero-knowledge proofs for NP from LWE ⋮ Attribute-based proxy re-encryption from standard lattices ⋮ Algebraically structured LWE. Revisited ⋮ Matrix PRFs: constructions, attacks, and applications to obfuscation ⋮ A pseudorandom number generator based on worst-case lattice problems ⋮ Generalized approach for analysing quantum key distribution experiments ⋮ Bonsai trees, or how to delegate a lattice basis ⋮ Efficient and fully secure lattice-based IBE with equality test ⋮ Comparison analysis of Ding's RLWE-based key exchange protocol and NewHope variants ⋮ Estimation of the hardness of the learning with errors problem with a restricted number of samples ⋮ Augmented Learning with Errors: The Untapped Potential of the Error Term ⋮ On the hardness of module learning with errors with short distributions ⋮ Hardness of \(k\)-LWE and applications in traitor tracing ⋮ Zero-Knowledge Arguments for Matrix-Vector Relations and Lattice-Based Group Encryption ⋮ Signature Schemes with Efficient Protocols and Dynamic Group Signatures from Lattice Assumptions ⋮ Towards Tightly Secure Lattice Short Signature and Id-Based Encryption ⋮ Preventing Adaptive Key Recovery Attacks on the GSW Levelled Homomorphic Encryption Scheme ⋮ Encoding Functions with Constant Online Rate, or How to Compress Garbled Circuit Keys ⋮ On optimizing electricity markets performance ⋮ On the asymptotic complexity of solving LWE ⋮ Computational fuzzy extractor from LWE ⋮ Improved broadcast attacks against subset sum problems via lattice oracle ⋮ Improving convergence and practicality of slide-type reductions ⋮ Efficient authentication from hard learning problems ⋮ Adaptively secure inner product encryption from LWE ⋮ More constructions of lossy and correlation-secure trapdoor functions ⋮ Finding collisions in a quantum world: quantum black-box separation of collision-resistance and one-wayness ⋮ Towards classical hardness of module-LWE: the linear rank case ⋮ Succinct LWE sampling, random polynomials, and obfuscation ⋮ Direct computation of branching programs and its applications to more efficient lattice-based cryptography ⋮ Zero-knowledge arguments for matrix-vector relations and lattice-based group encryption ⋮ Lattice-based proxy-oriented identity-based encryption with keyword search for cloud storage ⋮ Revocable identity-based encryption with bounded decryption key exposure resistance: lattice-based construction and more ⋮ Computational fuzzy extractors ⋮ Extremal set theory and LWE based access structure hiding verifiable secret sharing with malicious-majority and free verification ⋮ Strongly secure authenticated key exchange from factoring, codes, and lattices ⋮ Minimal condition for shortest vectors in lattices of low dimension ⋮ NTRU prime: reducing attack surface at low cost ⋮ A lattice-based group signature scheme with verifier-local revocation ⋮ 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 ⋮ A multi-key SMC protocol and multi-key FHE based on some-are-errorless LWE ⋮ Generating shorter bases for hard random lattices ⋮ On the structure of Boolean functions with small spectral norm ⋮ (Leveled) Fully Homomorphic Encryption without Bootstrapping ⋮ Verifying solutions to LWE with implications for concrete security ⋮ Finding Shortest Lattice Vectors in the Presence of Gaps ⋮ Post-Quantum Forward-Secure Onion Routing ⋮ Collusion-resistant identity-based proxy re-encryption: lattice-based constructions in standard model ⋮ On the Hardness of Learning with Rounding over Small Modulus ⋮ Cryptographic Assumptions: A Position Paper ⋮ Adaptive Security with Quasi-Optimal Rate ⋮ Decompositions of Triangle-Dense Graphs ⋮ Finding Correlations in Subquadratic Time, with Applications to Learning Parities and the Closest Pair Problem ⋮ A lattice-based signcryption scheme without random oracles ⋮ Revocable attribute-based proxy re-encryption ⋮ Verifiable single-server private information retrieval from LWE with binary errors ⋮ Decentralized multi-authority \textbf{\textsf{ABE}} for \textbf{\textsf{DNF}}s from \textbf{\textsf{LWE}} ⋮ 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 ⋮ A Lattice-Based Group Signature Scheme with Message-Dependent Opening ⋮ Turing Machines with Shortcuts: Efficient Attribute-Based Encryption for Bounded Functions ⋮ A novel fully homomorphic encryption scheme bsed on LWE ⋮ Identity-based encryption with security against the KGC: a formal model and its instantiations ⋮ How (Not) to Instantiate Ring-LWE ⋮ Three’s Compromised Too: Circular Insecurity for Any Cycle Length from (Ring-)LWE ⋮ Circular Security Separations for Arbitrary Length Cycles from LWE ⋮ Spooky Encryption and Its Applications ⋮ Circuit-ABE from LWE: Unbounded Attributes and Semi-adaptive Security ⋮ LWE from non-commutative group rings ⋮ Lattice-Based Fully Dynamic Multi-key FHE with Short Ciphertexts ⋮ On the rejection rate of exact sampling algorithm for discrete Gaussian distributions over the integers ⋮ Hardness of learning problems over Burnside groups of exponent 3 ⋮ Incompressible encodings ⋮ Lattice reduction for modules, or how to reduce ModuleSVP to ModuleSVP ⋮ Slide reduction, revisited -- filling the gaps in SVP approximation ⋮ Rounding in the rings ⋮ An optimized GHV-type HE scheme: simpler, faster, and more versatile ⋮ A new post-quantum multivariate polynomial public key encapsulation algorithm ⋮ Worst-case to average-case reductions for module lattices ⋮ Hardness of LWE on general entropic distributions ⋮ Key-homomorphic pseudorandom functions from LWE with small modulus
