Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller
From MaRDI portal
Publication:2894439
DOI10.1007/978-3-642-29011-4_41zbMath1297.94090OpenAlexW74973629MaRDI QIDQ2894439
Chris Peikert, Daniele Micciancio
Publication date: 29 June 2012
Published in: Advances in Cryptology – EUROCRYPT 2012 (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-29011-4_41
Related Items
Fully Homomorphic Encryption with Auxiliary Inputs ⋮ Trapdoors for Ideal Lattices with Applications ⋮ Approximate-Deterministic Public Key Encryption from Hard Learning Problems ⋮ Predicate Encryption for Circuits from LWE ⋮ Multi-key FHE from LWE, Revisited ⋮ Deniable Attribute Based Encryption for Branching Programs from LWE ⋮ Targeted Homomorphic Attribute-Based Encryption ⋮ Zero-Knowledge Interactive Proof Systems for New Lattice Problems ⋮ Sponge Based CCA2 Secure Asymmetric Encryption for Arbitrary Length Message ⋮ A survey of lattice based expressive attribute based encryption ⋮ Post-quantum online voting scheme ⋮ On Key Recovery Attacks Against Existing Somewhat Homomorphic Encryption Schemes ⋮ Lattice-based secret handshakes with reusable credentials ⋮ Efficient and fully secure lattice-based IBE with equality test ⋮ More efficient construction of anonymous signatures ⋮ Augmented Learning with Errors: The Untapped Potential of the Error Term ⋮ Cryptanalysis of Boyen's attribute-based encryption scheme in TCC 2013 ⋮ On the hardness of module learning with errors with short distributions ⋮ 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 ⋮ From Identification to Signatures, Tightly: A Framework and Generic Transforms ⋮ Multi-key Homomorphic Authenticators ⋮ Partitioning via Non-linear Polynomial Functions: More Compact IBEs from Ideal Lattices and Bilinear Maps ⋮ A Homomorphic Proxy Re-encryption from Lattices ⋮ Adaptively secure inner product encryption from LWE ⋮ Non-committing encryption with constant ciphertext expansion from standard assumptions ⋮ Towards classical hardness of module-LWE: the linear rank case ⋮ Succinct LWE sampling, random polynomials, and obfuscation ⋮ ABE for DFA from LWE against bounded collusions, revisited ⋮ Ring-based identity based encryption -- asymptotically shorter MPK and tighter security ⋮ Towards tight adaptive security of non-interactive key exchange ⋮ Vector and functional commitments from lattices ⋮ Direct computation of branching programs and its applications to more efficient lattice-based cryptography ⋮ Simulatable verifiable random function from the LWE assumption ⋮ Identity-Based Blind Signature from Lattices in Standard Model ⋮ Multi-bit Leveled Homomorphic Encryption via $$\mathsf {Dual.LWE}$$ -Based ⋮ A Practical Post-Quantum Public-Key Cryptosystem Based on $$\textsf {spLWE}$$ ⋮ 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 ⋮ Compact Inner Product Encryption from LWE ⋮ Compact Hierarchical IBE from Lattices in the Standard Model ⋮ 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 ⋮ Generic Construction of UC-Secure Oblivious Transfer ⋮ Adaptive Security with Quasi-Optimal Rate ⋮ Decompositions of Triangle-Dense Graphs ⋮ Lattice-based identity-based resplittable threshold public key encryption scheme ⋮ An LWE-based verifiable threshold secret sharing scheme ⋮ Classical Homomorphic Encryption for Quantum Circuits ⋮ The Geometry of Lattice Cryptography ⋮ Turing Machines with Shortcuts: Efficient Attribute-Based Encryption for Bounded Functions ⋮ The Whole is Less Than the Sum of Its Parts: Constructing More Efficient Lattice-Based AKEs ⋮ How (Not) to Instantiate Ring-LWE ⋮ FHE Circuit Privacy Almost for Free ⋮ Cryptanalysis of GGH15 Multilinear Maps ⋮ Three’s Compromised Too: Circular Insecurity for Any Cycle Length from (Ring-)LWE ⋮ Circular Security Separations for Arbitrary Length Cycles from LWE ⋮ Programmable Hash Functions from Lattices: Short Signatures and IBEs with Small Key Sizes ⋮ Fully Secure Functional Encryption for Inner Products, from Standard Assumptions ⋮ Circuit-ABE from LWE: Unbounded Attributes and Semi-adaptive Security ⋮ Lattice-Based Fully Dynamic Multi-key FHE with Short Ciphertexts ⋮ Cryptography with Auxiliary Input and Trapdoor from Constant-Noise LPN ⋮ Attribute-Based Keyword Search from Lattices ⋮ PAKEs: New Framework, New Techniques and More Efficient Lattice-Based Constructions in the Standard Model ⋮ Constraining and Watermarking PRFs from Milder Assumptions ⋮ Improved Discrete Gaussian and Subgaussian Analysis for Lattice Cryptography ⋮ Almost Tight Security in Lattices with Polynomial Moduli – PRF, IBE, All-but-many LTF, and More ⋮ Isochronous Gaussian Sampling: From Inception to Implementation ⋮ Efficient Post-quantum SNARKs for RSIS and RLWE and Their Applications to Privacy ⋮ Short Zero-Knowledge Proof of Knowledge for Lattice-Based Commitment ⋮ COSAC: COmpact and Scalable Arbitrary-Centered Discrete Gaussian Sampling over Integers ⋮ Efficient Verifiable Partially-Decryptable Commitments from Lattices and Applications ⋮ Two-Round Oblivious Linear Evaluation from Learning with Errors ⋮ Towards a Simpler Lattice Gadget Toolkit ⋮ Ring Trapdoor Redactable Signatures from Lattice ⋮ Classical Verification of Quantum Computations ⋮ Gladius: LWR Based Efficient Hybrid Public Key Encryption with Distributed Decryption ⋮ Shorter Lattice-Based Group Signatures via “Almost Free” Encryption and Other Optimizations ⋮ Lattice-based accumulator with constant time list update and constant time verification ⋮ Functional commitments for all functions, with transparent setup and from SIS ⋮ 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 ⋮ Succinct vector, polynomial, and functional commitments from lattices ⋮ Efficient laconic cryptography from learning with errors ⋮ Sender-binding key encapsulation ⋮ Privately puncturing PRFs from lattices: adaptive security and collusion resistant pseudorandomness ⋮ Quantum commitments and signatures without one-way functions ⋮ Lattice-based zero-knowledge proofs and applications: shorter, simpler, and more general ⋮ Lattice-based SNARKs: publicly verifiable, preprocessing, and recursively composable (extended abstract) ⋮ Shorter hash-and-sign lattice-based signatures ⋮ MuSig-L: lattice-based multi-signature with single-round online phase ⋮ A new framework for more efficient round-optimal lattice-based (partially) blind signature via trapdoor sampling ⋮ Achieving Almost-Full Security for Lattice-Based Fully Dynamic Group Signatures with Verifier-Local Revocation ⋮ Fiat-Shamir signatures based on module-NTRU ⋮ Relaxed Lattice-Based Signatures with Short Zero-Knowledge Proofs ⋮ Verifiable Decryption for Fully Homomorphic Encryption ⋮ Lattice-based signatures with tight adaptive corruptions and more ⋮ Efficient lattice-based blind signatures via Gaussian one-time signatures ⋮ Multi-authority ABE from lattices without random oracles ⋮ ABE for circuits with constant-size secret keys and adaptive security ⋮ Revocable identity-based fully homomorphic signature scheme with signing key exposure resistance ⋮ Fully collusion resistant trace-and-revoke functional encryption for arbitrary identities ⋮ Triply adaptive UC NIZK ⋮ Multi-key fully homomorphic encryption from NTRU and (R)LWE with faster bootstrapping ⋮ Identity-based interactive aggregate signatures from lattices ⋮ Preimage sampling in the higher-bit approximate setting with a non-spherical Gaussian sampler ⋮ New and improved constructions for partially equivocable public key encryption ⋮ Cumulatively all-lossy-but-one trapdoor functions from standard assumptions ⋮ (Inner-product) functional encryption with updatable ciphertexts ⋮ Lattice signature with efficient protocols, application to anonymous credentials ⋮ A framework for practical anonymous credentials from lattices ⋮ A fully secure lattice-based signcryption with designated equality test in standard model ⋮ Candidate witness encryption from lattice techniques ⋮ Balanced non-adjacent forms ⋮ Public-key watermarking schemes for pseudorandom functions ⋮ Leveled Hierarchical Identity-Based Fully Homomorphic Encryption from Learning with Rounding ⋮ A New Design of Online/Offline Signatures Based on Lattice ⋮ A New Insight—Proxy Re-encryption Under LWE with Strong Anti-collusion ⋮ Entropic hardness of Module-LWE from module-NTRU ⋮ Simplified server-aided revocable identity-based encryption from lattices ⋮ Spatial encryption revisited: from delegatable multiple inner product encryption and more ⋮ Public key authenticated encryption with keyword search from LWE ⋮ Lattice-based programmable hash functions and applications ⋮ Quantum search-to-decision reduction for the LWE problem ⋮ Lattice-based succinct arguments from vanishing polynomials (extended abstract) ⋮ \textsf{Orbweaver}: succinct linear functional commitments from lattices ⋮ Compact lattice gadget and its applications to hash-and-sign signatures ⋮ Error correction and ciphertext quantization in lattice cryptography ⋮ Almost tight multi-user security under adaptive corruptions from LWE in the standard model ⋮ \textsf{DualMS}: efficient lattice-based two-round multi-signature with trapdoor-free simulation ⋮ A lower bound for proving hardness of learning with rounding with polynomial modulus ⋮ Traceable policy-based signatures and instantiation from lattices ⋮ Lattice-Based Identity-Based Homomorphic Conditional Proxy Re-Encryption for Secure Big Data Computing in Cloud Environment ⋮ Collusion Resistant Traitor Tracing from Learning with Errors ⋮ Deterministic compression with uncertain priors ⋮ Drawing Bobbin Lace Graphs, or, Fundamental Cycles for a Subclass of Periodic Graphs ⋮ Discrete Gaussian Distributions via Theta Functions ⋮ 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 ⋮ 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 ⋮ Generic constructions of integrated PKE and PEKS ⋮ Tighter security proofs for GPV-IBE in the quantum random oracle model ⋮ Verifying quantum computations at scale: A cryptographic leash on quantum devices ⋮ Two-round \(n\)-out-of-\(n\) and multi-signatures and trapdoor commitment from lattices ⋮ Two-round \(n\)-out-of-\(n\) and multi-signatures and trapdoor commitment from lattices ⋮ A Novel Lattice-Based Ciphertext-Policy Attribute-Based Proxy Re-encryption for Cloud Sharing ⋮ Adaptively secure MPC with sublinear communication complexity ⋮ Classical Homomorphic Encryption for Quantum Circuits ⋮ A time-distance trade-off for GDD with preprocessing: instantiating the DLW heuristic ⋮ Multi-use Deterministic Public Key Proxy Re-Encryption from Lattices in the Auxiliary-Input Setting ⋮ Towards Round-Optimal Secure Multiparty Computations: Multikey FHE Without a CRS ⋮ Lattice-based revocable (hierarchical) IBE with decryption key exposure resistance ⋮ Homomorphic Encryption ⋮ Separating Semantic and Circular Security for Symmetric-Key Bit Encryption from the Learning with Errors Assumption ⋮ Cryptanalyses of Candidate Branching Program Obfuscators ⋮ Hardness of (M)LWE with semi-uniform seeds ⋮ Lattice-based key exchange on small integer solution problem ⋮ A constant-time sampling algorithm for binary Gaussian distribution over the integers ⋮ SoK: how (not) to design and implement post-quantum cryptography ⋮ On the hardness of module-LWE with binary secret ⋮ Counterexamples to new circular security assumptions underlying iO ⋮ SO-CCA secure PKE from pairing based all-but-many lossy trapdoor functions ⋮ (In)security of concrete instantiation of Lin17's functional encryption scheme from noisy multilinear maps ⋮ Obfuscating finite automata ⋮ Attribute-based signatures from lattices: unbounded attributes and semi-adaptive security ⋮ Two-message statistically sender-private OT from LWE ⋮ Adaptively secure distributed PRFs from LWE ⋮ Does Fiat-Shamir require a cryptographic hash function? ⋮ Policy-based signature scheme from lattices ⋮ Universal product learning with errors: a new variant of \textsf{LWE} for lattice-based cryptography ⋮ Tightly secure signatures from lossy identification schemes ⋮ Attribute-based access control for inner product functional encryption from LWE ⋮ Review of cryptographic schemes applied to remote electronic voting systems: remaining challenges and the upcoming post-quantum paradigm ⋮ Attribute-based conditional proxy re-encryption in the standard model under LWE ⋮ Lattice-based HRA-secure attribute-based proxy re-encryption in standard model ⋮ On the higher-bit version of approximate inhomogeneous short integer solution problem ⋮ Survey of information security ⋮ Gadget-based iNTRU lattice trapdoors ⋮ Memory lower bounds of reductions revisited ⋮ Faster Gaussian sampling for trapdoor lattices with arbitrary modulus ⋮ Puncturable identity-based and attribute-based encryption from lattices ⋮ Lattice-based public-key encryption with equality test supporting flexible authorization in standard model ⋮ A Ring-LWE-based digital signature inspired by Lindner-Peikert scheme ⋮ Attribute-based proxy re-encryption from standard lattices ⋮ Scalable revocable identity-based signature over lattices in the standard model ⋮ Duplication free public keys based on SIS-type problems ⋮ Lattice trapdoors and IBE from middle-product LWE ⋮ Matrix PRFs: constructions, attacks, and applications to obfuscation ⋮ Compressible FHE with applications to PIR ⋮ Finding shortest lattice vectors faster using quantum search ⋮ A generic construction of tightly secure signatures in the multi-user setting ⋮ Hardness of \(k\)-LWE and applications in traitor tracing ⋮ On the asymptotic complexity of solving LWE ⋮ Loop-abort faults on lattice-based Fiat-Shamir and hash-and-sign signatures ⋮ Zero-knowledge arguments for matrix-vector relations and lattice-based group encryption ⋮ Revocable identity-based encryption with bounded decryption key exposure resistance: lattice-based construction and more ⋮ Lattice-based completely non-malleable public-key encryption in the standard model ⋮ Public key compression for constrained linear signature schemes ⋮ Trapdoor delegation and HIBE from middle-product LWE in standard model ⋮ 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 ⋮ Efficient public-key encryption with equality test from lattices ⋮ CPA/CCA2-secure PKE with squared-exponential DFR from low-noise LPN ⋮ A lattice-based group signature scheme with verifier-local revocation ⋮ A multi-key SMC protocol and multi-key FHE based on some-are-errorless LWE ⋮ A more efficient leveled strongly-unforgeable fully homomorphic signature scheme ⋮ On the structure of Boolean functions with small spectral norm ⋮ Discretisation and product distributions in ring-LWE ⋮ Collusion-resistant identity-based proxy re-encryption: lattice-based constructions in standard model ⋮ Lattice-based unidirectional infinite-use proxy re-signatures with private re-signature key ⋮ 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 ⋮ Sampling from discrete Gaussians for lattice-based cryptography on a constrained device ⋮ Revocable attribute-based proxy re-encryption ⋮ CCA-security from adaptive all-but-one lossy trapdoor functions ⋮ TFHE: fast fully homomorphic encryption over the torus ⋮ Optimal broadcast encryption from pairings and LWE ⋮ Indistinguishability obfuscation without maps: attacks and fixes for noisy linear FE ⋮ Key recovery from Gram-Schmidt norm leakage in hash-and-sign signatures over NTRU lattices ⋮ 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 ⋮ Unbounded multi-party computation from learning with errors ⋮ Candidate obfuscation via oblivious LWE sampling ⋮ Worst case short lattice vector enumeration on block reduced bases of arbitrary blocksizes ⋮ Cryptanalysis of a rank-based signature with short public keys ⋮ Exact lattice sampling from non-Gaussian distributions ⋮ Efficient adaptively-secure IB-KEMs and VRFs via near-collision resistance ⋮ Non-interactive CCA2-secure threshold cryptosystems: achieving adaptive security in the standard model without pairings ⋮ Round-optimal verifiable oblivious pseudorandom functions from ideal lattices ⋮ Identity-based encryption with security against the KGC: a formal model and its instantiations ⋮ Quantum-resistant identity-based signature with message recovery and proxy delegation ⋮ LWE from non-commutative group rings ⋮ Chosen-ciphertext lattice-based public key encryption with equality test in standard model ⋮ Why you cannot even hope to use Gröbner bases in cryptography: an eternal golden braid of failures ⋮ A new Gaussian sampling for trapdoor lattices with arbitrary modulus ⋮ Tightly secure signature schemes from the LWE and subset sum assumptions ⋮ Lattice-based revocable certificateless signature ⋮ Strongly unforgeable ring signature scheme from lattices in the standard model ⋮ Incompressible encodings ⋮ Adaptively secure constrained pseudorandom functions in the standard model ⋮ Rounding in the rings ⋮ An optimized GHV-type HE scheme: simpler, faster, and more versatile ⋮ Progressive and efficient verification for digital signatures ⋮ Revocable hierarchical attribute-based signatures from lattices ⋮ Worst-case to average-case reductions for module lattices ⋮ Password protected secret sharing from lattices ⋮ Efficient homomorphic conversion between (ring) LWE ciphertexts ⋮ Implementation of lattice trapdoors on modules and applications ⋮ Generating cryptographically-strong random lattice bases and recognizing rotations of \(\mathbb{Z}^n\) ⋮ Short identity-based signatures with tight security from lattices ⋮ Secure hybrid encryption in the standard model from hard learning problems ⋮ Hardness of LWE on general entropic distributions ⋮ Key-homomorphic pseudorandom functions from LWE with small modulus ⋮ Integral matrix Gram root and lattice Gaussian sampling without floats
Uses Software
This page was built for publication: Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller
