On lattices, learning with errors, random linear codes, and cryptography

DOI10.1145/1060590.1060603zbMath1192.94106OpenAlexW2061949491WikidataQ54066002 ScholiaQ54066002MaRDI QIDQ5901106

Oded Regev

Publication date: 16 August 2010

Published in: Proceedings of the thirty-seventh annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1060590.1060603

Mathematics Subject Classification ID

Quantum computation (81P68) Cryptography (94A60) Data encryption (aspects in computer science) (68P25)

Related Items

Lattice-based SNARKs: publicly verifiable, preprocessing, and recursively composable (extended abstract) ⋮ Shorter hash-and-sign lattice-based signatures ⋮ Some easy instances of ideal-SVP and implications on the partial Vandermonde knapsack problem ⋮ On codes and learning with errors over function fields ⋮ Breaking the Hardness Assumption and IND-CPA Security of HQC Submitted to NIST PQC Project ⋮ Achieving Almost-Full Security for Lattice-Based Fully Dynamic Group Signatures with Verifier-Local Revocation ⋮ Fiat-Shamir signatures based on module-NTRU ⋮ Multi-key Homomorphic Proxy Re-Encryption ⋮ Parameter optimization and larger precision for (T)FHE ⋮ Zero-knowledge arguments for lattice-based accumulators: logarithmic-size ring signatures and group signatures without trapdoors ⋮ Batched fully homomorphic encryption from TFHE ⋮ Lattice-based signatures with tight adaptive corruptions and more ⋮ Multi-authority ABE from lattices without random oracles ⋮ Rate-1 incompressible encryption from standard assumptions ⋮ Achievable \textsf{CCA2} relaxation for homomorphic encryption ⋮ Homomorphic encryption: a mathematical survey ⋮ Fully collusion resistant trace-and-revoke functional encryption for arbitrary identities ⋮ Zero-knowledge protocols for the subset sum problem from MPC-in-the-head with rejection ⋮ Multi-key fully homomorphic encryption from NTRU and (R)LWE with faster bootstrapping ⋮ Subfield attacks on HSVP in ideal 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 ⋮ Towards case-optimized hybrid homomorphic encryption. Featuring the \textsf{Elisabeth} stream cipher ⋮ A non-heuristic approach to time-space tradeoffs and optimizations for BKW ⋮ Another round of breaking and making quantum money: how to not build it from lattices, and more ⋮ (Inner-product) functional encryption with updatable ciphertexts ⋮ Take your MEDS: digital signatures from matrix code equivalence ⋮ Lattice signature with efficient protocols, application to anonymous credentials ⋮ Generic constructions of master-key KDM secure attribute-based encryption ⋮ Computing primitive idempotents in finite commutative rings and applications ⋮ Candidate witness encryption from lattice techniques ⋮ How to build a trapdoor function from an encryption scheme ⋮ Improved programmable bootstrapping with larger precision and efficient arithmetic circuits for TFHE ⋮ Time-release cryptography from minimal circuit assumptions ⋮ Modeling and simulating the sample complexity of solving LWE using BKW-style algorithms ⋮ Polar coding for ring-LWE-based public key encryption ⋮ Dilithium for memory constrained devices ⋮ New constructions of collapsing hashes ⋮ Statistically sender-private OT from LPN and derandomization ⋮ Constructive post-quantum reductions ⋮ Lattice-Based Proof of a Shuffle ⋮ Post-quantum plaintext-awareness ⋮ Forward-secure revocable secret handshakes from lattices ⋮ Post-quantum asynchronous deniable key exchange and the signal handshake ⋮ Lockable obfuscation from circularly insecure fully homomorphic encryption ⋮ Efficient lattice-based inner-product functional encryption ⋮ Post-quantum insecurity from LWE ⋮ Quantum rewinding for many-round protocols ⋮ Public-key encryption from homogeneous CLWE ⋮ Entropic hardness of Module-LWE from module-NTRU ⋮ Simplified server-aided revocable identity-based encryption from lattices ⋮ Lattice-based public key cryptosystems invoking linear mapping mask ⋮ Batched fully dynamic multi-key FHE from FHEW-like cryptosystems ⋮ Generic construction of trace-and-revoke inner product functional encryption ⋮ Spatial encryption revisited: from delegatable multiple inner product encryption and more ⋮ 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 ⋮ Quantum search-to-decision reduction for the LWE problem ⋮ Learning with physical rounding for linear and quadratic leakage functions ⋮ Black-hole radiation decoding is quantum cryptography ⋮ 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 ⋮ Lattice-based timed cryptography ⋮ A lower bound for proving hardness of learning with rounding with polynomial modulus ⋮ \(\mathrm{mR}_{\mathrm{LWE}}\)-CP-ABE: a revocable CP-ABE for post-quantum cryptography ⋮ Traceable policy-based signatures and instantiation from lattices ⋮ Elliptic genera from classical error-correcting codes ⋮ Indistinguishability obfuscation ⋮ Hardness of (M)LWE with semi-uniform seeds ⋮ Candidate iO from homomorphic encryption schemes ⋮ Classical Homomorphic Encryption for Quantum Circuits ⋮ On CCA-Secure Somewhat Homomorphic Encryption ⋮ The Cryptographic Power of Random Selection ⋮ Cryptography from Learning Parity with Noise ⋮ Secure Multiparty RAM Computation in Constant Rounds ⋮ Approximate-Deterministic Public Key Encryption from Hard Learning Problems ⋮ Deniable Attribute Based Encryption for Branching Programs from LWE ⋮ Targeted Homomorphic Attribute-Based Encryption ⋮ Semi-adaptive Security and Bundling Functionalities Made Generic and Easy ⋮ From Cryptomania to Obfustopia Through Secret-Key Functional Encryption ⋮ On the Efficacy of Solving LWE by Reduction to Unique-SVP ⋮ Oblivious Transfer from Weakly Random Self-Reducible Public-Key Cryptosystem ⋮ Faster Sieving for Shortest Lattice Vectors Using Spherical Locality-Sensitive Hashing ⋮ FHEW with Efficient Multibit Bootstrapping ⋮ Augmented Learning with Errors: The Untapped Potential of the Error Term ⋮ Leakage Resilience of the Blom’s Key Distribution Scheme ⋮ Zero-Knowledge Arguments for Matrix-Vector Relations and Lattice-Based Group Encryption ⋮ Efficient KDM-CCA Secure Public-Key Encryption for Polynomial Functions ⋮ Signature Schemes with Efficient Protocols and Dynamic Group Signatures from Lattice Assumptions ⋮ Towards Tightly Secure Lattice Short Signature and Id-Based Encryption ⋮ Partitioning via Non-linear Polynomial Functions: More Compact IBEs from Ideal Lattices and Bilinear Maps ⋮ A Homomorphic Proxy Re-encryption from Lattices ⋮ 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 ⋮ Faster Fully Homomorphic Encryption: Bootstrapping in Less Than 0.1 Seconds ⋮ Optimization of $$\mathsf {LPN}$$ Solving Algorithms ⋮ Direct computation of branching programs and its applications to more efficient lattice-based cryptography ⋮ Secret handshakes: full dynamicity, deniability and lattice-based design ⋮ Maliciously circuit-private multi-key FHE and MPC based on LWE ⋮ Polar sampler: a novel Bernoulli sampler using polar codes with application to integer Gaussian sampling ⋮ 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 ⁰ ○ MOD ₂ ⋮ 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 ⋮ Algorithms for the Shortest and Closest Lattice Vector Problems ⋮ Gate Elimination for Linear Functions and New Feebly Secure Constructions ⋮ Fully Simulatable Quantum-Secure Coin-Flipping and Applications ⋮ Post-Quantum Forward-Secure Onion Routing ⋮ Lower Bounds on Assumptions Behind Indistinguishability Obfuscation ⋮ On the Hardness of Learning with Rounding over Small Modulus ⋮ Two-Round Man-in-the-Middle Security from LPN ⋮ Reconfigurable Cryptography: A Flexible Approach to Long-Term Security ⋮ Cryptographic Assumptions: A Position Paper ⋮ Decompositions of Triangle-Dense Graphs ⋮ CCA-Secure Keyed-Fully Homomorphic Encryption ⋮ Post-Quantum Cryptography: State of the Art ⋮ Lattice-based identity-based resplittable threshold public key encryption scheme ⋮ Algebraic cryptography: new constructions and their security against provable break ⋮ Homomorphic Evaluation of Lattice-Based Symmetric Encryption Schemes ⋮ A Lattice-Based Group Signature Scheme with Message-Dependent Opening ⋮ Turing Machines with Shortcuts: Efficient Attribute-Based Encryption for Bounded Functions ⋮ Parallel Implementation of BDD Enumeration for LWE ⋮ Generalized Learning Problems and Applications to Non-commutative Cryptography ⋮ Naor-Yung Paradigm with Shared Randomness and Applications ⋮ Adversary-Dependent Lossy Trapdoor Function from Hardness of Factoring Semi-smooth RSA Subgroup Moduli ⋮ FHE Circuit Privacy Almost for Free ⋮ Towards Sound Fresh Re-keying with Hard (Physical) Learning Problems ⋮ 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 ⋮ Efficient Threshold Encryption from Lossy Trapdoor Functions ⋮ Lattice-Based Fully Dynamic Multi-key FHE with Short Ciphertexts ⋮ Cryptography with Auxiliary Input and Trapdoor from Constant-Noise LPN ⋮ Measure inequalities and the transference theorem in the geometry of numbers ⋮ On random nonsingular Hermite normal form ⋮ Lattice-based key exchange on small integer solution problem ⋮ On solving LPN using BKW and variants, Implementation and analysis ⋮ Noisy Simon period finding ⋮ SoK: how (not) to design and implement post-quantum cryptography ⋮ Dual lattice attacks for closest vector problems (with preprocessing) ⋮ On the hardness of module-LWE with binary secret ⋮ Balancing access control and privacy for data deduplication via functional encryption ⋮ SO-CCA secure PKE from pairing based all-but-many lossy trapdoor functions ⋮ Signature schemes secure against hard-to-invert leakage ⋮ Two-round MPC: information-theoretic and black-box ⋮ Two-message statistically sender-private OT from LWE ⋮ Adaptively secure distributed PRFs from LWE ⋮ Return of GGH15: provable security against zeroizing attacks ⋮ LWE without modular reduction and improved side-channel attacks against BLISS ⋮ Quantum algorithms for the \(k\)-XOR problem ⋮ Policy-based signature scheme from lattices ⋮ Regular lossy functions and their applications in leakage-resilient cryptography ⋮ Review of cryptographic schemes applied to remote electronic voting systems: remaining challenges and the upcoming post-quantum paradigm ⋮ Memory lower bounds of reductions revisited ⋮ Fiat-Shamir and correlation intractability from strong KDM-secure encryption ⋮ Shortest vector from lattice sieving: a few dimensions for free ⋮ Another step towards realizing random oracles: non-malleable point obfuscation ⋮ A novel model for lattice-based authorized searchable encryption with special keyword ⋮ A pseudorandom number generator based on worst-case lattice problems ⋮ Finding shortest lattice vectors faster using quantum search ⋮ New transference theorems on lattices possessing \(n^\varepsilon\)-unique shortest vectors ⋮ Hardness of \(k\)-LWE and applications in traitor tracing ⋮ On the asymptotic complexity of solving LWE ⋮ The hunting of the SNARK ⋮ Efficient authentication from hard learning problems ⋮ Post-quantum key exchange for the Internet and the open quantum safe project ⋮ Circuit complexity of linear functions: gate elimination and feeble security ⋮ Leakage-resilient cryptography from puncturable primitives and obfuscation ⋮ Decentralized multi-client functional encryption for inner product ⋮ Simple and more efficient PRFs with tight security from LWE and matrix-DDH ⋮ Zero-knowledge arguments for matrix-vector relations and lattice-based group encryption ⋮ Assessing the feasibility of single trace power analysis of Frodo ⋮ Minimal condition for shortest vectors in lattices of low dimension ⋮ Quantum private comparison over noisy channels ⋮ Functional encryption for cubic polynomials and implementation ⋮ Efficient reductions in cyclotomic rings -- application to Ring LWE based FHE schemes ⋮ HILA5: on reliability, reconciliation, and error correction for Ring LWE encryption ⋮ A lattice-based group signature scheme with verifier-local revocation ⋮ The polynomial approximate common divisor problem and its application to the fully homomorphic encryption ⋮ 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 multivariate cryptosystem inspired by random linear codes ⋮ Finite interval-time transition system for real-time actors ⋮ Generating shorter bases for hard random lattices ⋮ On the structure of Boolean functions with small spectral norm ⋮ Functional encryption for cascade automata ⋮ (Leveled) Fully Homomorphic Encryption without Bootstrapping ⋮ A framework for cryptographic problems from linear algebra ⋮ Approximate Voronoi cells for lattices, revisited ⋮ Collusion-resistant identity-based proxy re-encryption: lattice-based constructions in standard model ⋮ Traceable ring signatures: general framework and post-quantum security ⋮ Lattice-based weak-key analysis on single-server outsourcing protocols of modular exponentiations and basic countermeasures ⋮ 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 ⋮ CCA-security from adaptive all-but-one lossy trapdoor functions ⋮ Limits on the efficiency of (ring) LWE-based non-interactive key exchange ⋮ Separating models of learning with faulty teachers ⋮ Optimal broadcast encryption from pairings and LWE ⋮ Candidate iO from homomorphic encryption schemes ⋮ Impossibility results for lattice-based functional encryption schemes ⋮ (One) failure is not an option: bootstrapping the search for failures in lattice-based encryption schemes ⋮ Low weight discrete logarithm and subset sum in \(2^{0.65n}\) with polynomial memory ⋮ Measure-rewind-measure: tighter quantum random oracle model proofs for one-way to hiding and CCA security ⋮ Tweaking the asymmetry of asymmetric-key cryptography on lattices: KEMs and signatures of smaller sizes ⋮ Decentralized multi-authority \textbf{\textsf{ABE}} for \textbf{\textsf{DNF}}s from \textbf{\textsf{LWE}} ⋮ Round-optimal blind signatures in the plain model from classical and quantum standard assumptions ⋮ New lattice two-stage sampling technique and its applications to functional encryption -- stronger security and smaller ciphertexts ⋮ On bounded distance decoding with predicate: breaking the ``lattice barrier for the hidden number problem ⋮ Multiparty reusable non-interactive secure computation from LWE ⋮ Indistinguishability obfuscation from simple-to-state hard problems: new assumptions, new techniques, and simplification ⋮ Candidate obfuscation via oblivious LWE sampling ⋮ Bifurcated signatures: folding the accountability vs. anonymity dilemma into a single private signing scheme ⋮ An efficient CCA-secure access control encryption for any policy ⋮ Chosen ciphertext attacks secure inner-product functional encryption from learning with errors assumption ⋮ Exact lattice sampling from non-Gaussian distributions ⋮ Non-interactive CCA2-secure threshold cryptosystems: achieving adaptive security in the standard model without pairings ⋮ Single-to-multi-theorem transformations for non-interactive statistical zero-knowledge ⋮ Round-optimal verifiable oblivious pseudorandom functions from ideal lattices ⋮ Identity-based encryption with security against the KGC: a formal model and its instantiations ⋮ LWE from non-commutative group rings ⋮ Cryptography with constant input locality ⋮ A new scale-invariant homomorphic encryption scheme ⋮ Incompressible encodings ⋮ Fast reduction of algebraic lattices over cyclotomic fields ⋮ Rounding in the rings ⋮ Efficient pseudorandom correlation generators from ring-LPN ⋮ Covert authentication from lattices ⋮ Efficient and tight oblivious transfer from PKE with tight multi-user security ⋮ Generic transformation from broadcast encryption to round-optimal deniable ring authentication ⋮ Access control encryption from group encryption ⋮ Short identity-based signatures with tight security from lattices ⋮ Secure hybrid encryption in the standard model from hard learning problems ⋮ Quantum indistinguishability for public key encryption ⋮ Impossibility of quantum virtual black-box obfuscation of classical circuits ⋮ Three-round secure multiparty computation from black-box two-round oblivious transfer ⋮ A new simple technique to bootstrap various lattice zero-knowledge proofs to QROM secure NIZKs ⋮ Counterexamples to new circular security assumptions underlying iO ⋮ Lattice reduction with approximate enumeration oracles. Practical algorithms and concrete performance ⋮ Lower bounds on lattice sieving and information set decoding ⋮ A trace map attack against special ring-LWE samples ⋮ Shortest vectors in lattices of Bai-Galbraith's embedding attack on the LWR problem ⋮ Smoothing out binary linear codes and worst-case sub-exponential hardness for LPN ⋮ Succinct non-interactive arguments via linear interactive proofs ⋮ An efficient CCA-secure cryptosystem over ideal lattices from identity-based encryption ⋮ Error analysis of weak poly-LWE instances ⋮ Universal product learning with errors: a new variant of \textsf{LWE} for lattice-based cryptography ⋮ Attribute-based access control for inner product functional encryption from LWE ⋮ Improved attacks against key reuse in learning with errors key exchange ⋮ A note on perfect correctness by derandomization ⋮ Lattice-based HRA-secure attribute-based proxy re-encryption in standard model ⋮ Black-box accumulation based on lattices ⋮ The matrix reloaded: multiplication strategies in FrodoKEM ⋮ Survey of information security ⋮ Making the BKW algorithm practical for LWE ⋮ On a dual/hybrid approach to small secret LWE. A dual/enumeration technique for learning with errors and application to security estimates of FHE schemes ⋮ Security of public key encryption against resetting attacks ⋮ Gadget-based iNTRU lattice trapdoors ⋮ Lattice-based IBE with equality test supporting flexible authorization in the standard model ⋮ Adaptively secure laconic function evaluation for \(\mathsf{NC}^1\) ⋮ Application of automorphic forms to lattice problems ⋮ Vandermonde meets Regev: public key encryption schemes based on partial Vandermonde problems ⋮ Ciphertext-only attacks against compact-LWE submitted to NIST PQC project ⋮ Puncturable identity-based and attribute-based encryption from lattices ⋮ 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 ⋮ Naor-Yung paradigm with shared randomness and applications ⋮ Asymptotically quasi-optimal cryptography ⋮ Secure multiparty computation with sublinear preprocessing ⋮ Indistinguishability obfuscation from LPN over \(\mathbb{F}_p\), DLIN, and PRGs in \(NC^0\) ⋮ Anamorphic encryption: private communication against a dictator ⋮ Batch-OT with optimal rate ⋮ One-shot Fiat-Shamir-based NIZK arguments of composite residuosity and logarithmic-size ring signatures in the standard model ⋮ Quantum algorithms for variants of average-case lattice problems via filtering ⋮ Quantum lightning never strikes the same state twice. Or: quantum money from cryptographic assumptions ⋮ Attribute-based proxy re-encryption from standard lattices ⋮ Lattice trapdoors and IBE from middle-product LWE ⋮ A black-box construction of fully-simulatable, round-optimal oblivious transfer from strongly uniform key agreement ⋮ Leveraging linear decryption: rate-1 fully-homomorphic encryption and time-lock puzzles ⋮ Permuted puzzles and cryptographic hardness ⋮ Revisiting approximate polynomial common divisor problem and noisy multipolynomial reconstruction ⋮ Generalized approach for analysing quantum key distribution experiments ⋮ Algebraic generalization of Diffie-Hellman key exchange ⋮ Post-quantum online voting scheme ⋮ Key-recovery attacks on \(\mathsf{ASASA}\) ⋮ Lattice-based secret handshakes with reusable credentials ⋮ Predicting the concrete security of LWE against the dual attack using binary search ⋮ Efficient and fully secure lattice-based IBE with equality test ⋮ A detailed analysis of the hybrid lattice-reduction and meet-in-the-middle attack ⋮ Estimation of the hardness of the learning with errors problem with a restricted number of samples ⋮ Quantum algorithms for typical hard problems: a perspective of cryptanalysis ⋮ On the hardness of module learning with errors with short distributions ⋮ Sample-size-reduction of quantum states for the noisy linear problem ⋮ Computational fuzzy extractor from LWE ⋮ Improved broadcast attacks against subset sum problems via lattice oracle ⋮ Improving convergence and practicality of slide-type reductions ⋮ Finding collisions in a quantum world: quantum black-box separation of collision-resistance and one-wayness ⋮ Non-committing encryption with constant ciphertext expansion from standard assumptions ⋮ Collusion resistant trace-and-revoke for arbitrary identities from standard assumptions ⋮ Towards classical hardness of module-LWE: the linear rank case ⋮ Twisted-PHS: using the product formula to solve approx-SVP in ideal lattices ⋮ Simpler statistically sender private oblivious transfer from ideals of cyclotomic integers ⋮ Cryptographic group actions and applications ⋮ A combinatorial approach to quantum random functions ⋮ Complexity theory. Abstracts from the workshop held November 14--20, 2021 (hybrid meeting) ⋮ Post-quantum resettably-sound zero knowledge ⋮ The round complexity of quantum zero-knowledge ⋮ Rate-1 quantum fully homomorphic encryption ⋮ Decentralized multi-authority ABE for \(\mathsf{NC}^1\) from BDH ⋮ Succinct LWE sampling, random polynomials, and obfuscation ⋮ Ring-based identity based encryption -- asymptotically shorter MPK and tighter security ⋮ Updatable public key encryption in the standard model ⋮ On the (M)iNTRU assumption in the integer case ⋮ Revocable identity-based encryption with bounded decryption key exposure resistance: lattice-based construction and more ⋮ Computational fuzzy extractors ⋮ Lattice-based completely non-malleable public-key encryption in the standard model ⋮ Efficient, actively secure MPC with a dishonest majority: a survey ⋮ Extremal set theory and LWE based access structure hiding verifiable secret sharing with malicious-majority and free verification ⋮ Almost fully anonymous attribute-based group signatures with verifier-local revocation and member registration from lattice assumptions ⋮ Efficient public-key encryption with equality test from lattices ⋮ Pseudorandom functions in NC class from the standard LWE assumption ⋮ On the complexity of the BKW algorithm on LWE ⋮ Novel updatable identity-based hash proof system and its applications ⋮ Cryptographic hardness for learning intersections of halfspaces ⋮ TFHE: fast fully homomorphic encryption over the torus ⋮ Worst case short lattice vector enumeration on block reduced bases of arbitrary blocksizes ⋮ Lattice-based group signatures: achieving full dynamicity (and deniability) with ease ⋮ 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 ⋮ Succinct non-interactive secure computation ⋮ Hardness of LWE on general entropic distributions ⋮ Limits on the Efficiency of (Ring) LWE Based Non-interactive Key Exchange ⋮ Almost Tight Security in Lattices with Polynomial Moduli – PRF, IBE, All-but-many LTF, and More ⋮ Decryption Failure Is More Likely After Success ⋮ Compact Lossy and All-but-One Trapdoor Functions from Lattice ⋮ Fully Homomorphic Encryption with Auxiliary Inputs ⋮ Zero-Knowledge Interactive Proof Systems for New Lattice Problems ⋮ Sampling from Arbitrary Centered Discrete Gaussians for Lattice-Based Cryptography ⋮ Multitarget Decryption Failure Attacks and Their Application to Saber and Kyber ⋮ Reusable Two-Round MPC from LPN ⋮ On the Bottleneck Complexity of MPC with Correlated Randomness ⋮ Two-Round Oblivious Linear Evaluation from Learning with Errors ⋮ Rational Modular Encoding in the DCR Setting: Non-interactive Range Proofs and Paillier-Based Naor-Yung in the Standard Model ⋮ Classical Verification of Quantum Computations ⋮ Lattice-Based Group Encryption with Full Dynamicity and Message Filtering Policy ⋮ A New Variant of Unbalanced Oil and Vinegar Using Quotient Ring: QR-UOV ⋮ NTRU Fatigue: How Stretched is Overstretched? ⋮ Faster Dual Lattice Attacks for Solving LWE with Applications to CRYSTALS ⋮ Sublinear-communication secure multiparty computation does not require FHE ⋮ 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 ⋮ Efficient laconic cryptography from learning with errors ⋮ On homomorphic secret sharing from polynomial-modulus LWE ⋮ Rinocchio: SNARKs for ring arithmetic ⋮ Breaking the \(O(\sqrt{n})\)-bit barrier: Byzantine agreement with polylog bits per party ⋮ Round-optimal oblivious transfer and MPC from computational CSIDH ⋮ Sender-binding key encapsulation ⋮ An upper bound on the covering radius of the logarithmic lattice for cyclotomic number fields ⋮ Optimisations and tradeoffs for HElib ⋮ Privately puncturing PRFs from lattices: adaptive security and collusion resistant pseudorandomness ⋮ Backward-leak uni-directional updatable encryption from (homomorphic) public key encryption ⋮ \texttt{POLKA}: towards leakage-resistant post-quantum CCA-secure public key encryption ⋮ Multikey Fully Homomorphic Encryption and Applications ⋮ Lattice-Based Identity-Based Homomorphic Conditional Proxy Re-Encryption for Secure Big Data Computing in Cloud Environment ⋮ How to Encrypt with the LPN Problem ⋮ Separating Models of Learning with Faulty Teachers ⋮ Unnamed Item ⋮ Collusion Resistant Traitor Tracing from Learning with Errors ⋮ Efficient and effective quantum compiling for entanglement-based machine learning on IBM Q devices ⋮ Explicit Hard Instances of the Shortest Vector Problem ⋮ Deterministic compression with uncertain priors ⋮ Boolean Functions for Homomorphic-Friendly Stream Ciphers ⋮ Two Efficient Tag-Based Encryption Schemes on Lattices ⋮ Compact Inner Product Encryption from LWE ⋮ Compact Hierarchical IBE from Lattices in the Standard Model ⋮ An Experimental Study of Kannan’s Embedding Technique for the Search LWE Problem ⋮ Bi-homomorphic Lattice-Based PRFs and Unidirectional Updatable Encryption ⋮ 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 ⋮ Fractional LWE: A Nonlinear Variant of LWE ⋮ Generic Construction of Bounded-Collusion IBE via Table-Based ID-to-Key Map ⋮ Discrete Gaussian Distributions via Theta Functions ⋮ Parameterized Intractability of Even Set and Shortest Vector Problem from Gap-ETH ⋮ Ring Packing and Amortized FHEW Bootstrapping ⋮ Improved Zero-Knowledge Proofs of Knowledge for the ISIS Problem, and Applications ⋮ Improved (Hierarchical) Inner-Product Encryption from Lattices ⋮ CCA-Secure Inner-Product Functional Encryption from Projective Hash Functions ⋮ LP Solutions of Vectorial Integer Subset Sums – Cryptanalysis of Galbraith’s Binary Matrix LWE ⋮ Separating IND-CPA and Circular Security for Unbounded Length Key Cycles ⋮ Provably Secure NTRU Instances over Prime Cyclotomic Rings ⋮ Efficient Compression of SIDH Public Keys ⋮ On Dual Lattice Attacks Against Small-Secret LWE and Parameter Choices in HElib and SEAL ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Parallel and Concurrent Security of the HB and HB +  Protocols ⋮ Cryptographic Functions from Worst-Case Complexity Assumptions ⋮ The truth behind the myth of the folk theorem ⋮ Algorithmic problems in Engel groups and cryptographic applications ⋮ Concurrently Secure Identification Schemes Based on the Worst-Case Hardness of Lattice Problems ⋮ Expanders with respect to Hadamard spaces and random graphs ⋮ Limits of local algorithms over sparse random graphs ⋮ Lattice-Based Identification Schemes Secure Under Active Attacks ⋮ Watermarking cryptographic functionalities from standard lattice assumptions ⋮ Topology-hiding computation on all graphs ⋮ 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 ⋮ Improvements in the analysis of Kannan's CVP algorithm ⋮ Functional Encryption for Cascade Automata (Extended Abstract) ⋮ Giophantus distinguishing attack is a low dimensional learning with errors problem ⋮ Predicting Lattice Reduction ⋮ A CCA2 Secure Public Key Encryption Scheme Based on the McEliece Assumptions in the Standard Model ⋮ Adaptive oblivious transfer with access control from lattice assumptions ⋮ A Novel Lattice-Based Ciphertext-Policy Attribute-Based Proxy Re-encryption for Cloud Sharing ⋮ Minicrypt primitives with algebraic structure and applications ⋮ Adaptively secure MPC with sublinear communication complexity ⋮ Classical Homomorphic Encryption for Quantum Circuits ⋮ 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 ⋮ Unnamed Item ⋮ Oblivious Transfer Based on the McEliece Assumptions ⋮ Algebraic Aspects of Solving Ring-LWE, Including Ring-Based Improvements in the Blum--Kalai--Wasserman Algorithm ⋮ Multi-use Deterministic Public Key Proxy Re-Encryption from Lattices in the Auxiliary-Input Setting ⋮ Lattice-based revocable (hierarchical) IBE with decryption key exposure resistance ⋮ The Complexity of Public-Key Cryptography ⋮ Separating Semantic and Circular Security for Symmetric-Key Bit Encryption from the Learning with Errors Assumption ⋮ A Note on Perfect Correctness by Derandomization ⋮ Quantum-Secure Symmetric-Key Cryptography Based on Hidden Shifts ⋮ Lattice-Based SNARGs and Their Application to More Efficient Obfuscation