On lattices, learning with errors, random linear codes, and cryptography
From MaRDI portal
Publication:5899512
DOI10.1145/1568318.1568324zbMath1325.68101OpenAlexW2007466965MaRDI QIDQ5899512
Publication date: 11 November 2015
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1568318.1568324
Linear codes (general theory) (94B05) Quantum computation (81P68) Cryptography (94A60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Relations with coding theory (11H71) Quantum algorithms and complexity in the theory of computing (68Q12)
Related Items
Adaptive Simulation Security for Inner Product Functional Encryption ⋮ 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 ⋮ The Power of Few Qubits and Collisions – Subset Sum Below Grover’s Bound ⋮ A Lattice-Based Approach to Privacy-Preserving Biometric Authentication Without Relying on Trusted Third Parties ⋮ Fast Discretized Gaussian Sampling and Post-quantum TLS Ciphersuite ⋮ Efficient Verifiable Partially-Decryptable Commitments from Lattices and Applications ⋮ Efficient Construction of Public-Key Matrices in Lattice-Based Cryptography: Chaos Strikes Again ⋮ Message-Restriction-Free Commitment Scheme Based on Lattice Assumption ⋮ A Systematic Approach and Analysis of Key Mismatch Attacks on Lattice-Based NIST Candidate KEMs ⋮ Shorter Lattice-Based Group Signatures via “Almost Free” Encryption and Other Optimizations ⋮ LMCLAEKS: LWE-assisted multi-recipient certificateless authenticated encryption with keyword search ⋮ Multiparty noninteractive key exchange from ring key-homomorphic weak PRFs ⋮ Functional commitments for all functions, with transparent setup and from SIS ⋮ Discretization error reduction for high precision torus fully homomorphic encryption ⋮ Efficient FHEW bootstrapping with small evaluation keys, and applications to threshold homomorphic encryption ⋮ On the feasibility of single-trace attacks on the Gaussian sampler using a CDT ⋮ A thorough treatment of highly-efficient NTRU instantiations ⋮ Semi-quantum tokenized signatures ⋮ Oblivious message retrieval ⋮ Graphic lattices made by graph felicitous-type labelings and colorings of topological coding ⋮ Lattice-based zero-knowledge proofs and applications: shorter, simpler, and more general ⋮ Solving LWR via BDD Strategy: Modulus Switching Approach ⋮ Revisiting the Sparsification Technique in Kannan’s Embedding Attack on LWE ⋮ Hybrid dual and meet-LWE attack ⋮ Classical reduction of gap SVP to LWE: a concrete security analysis ⋮ mrNISC from LWE with polynomial modulus ⋮ Homomorphic encryption: a mathematical survey ⋮ Revocable identity-based fully homomorphic signature scheme with signing key exposure resistance ⋮ Revisiting group oriented secret sharing schemes ⋮ mrNISC from LWE with polynomial modulus ⋮ Large-precision homomorphic sign evaluation using FHEW/TFHE bootstrapping ⋮ Classically verifiable NIZK for QMA with preprocessing ⋮ Subfield attacks on HSVP in ideal lattices ⋮ On the measurement and simulation of the BKZ behavior for \(q\)-ary lattices ⋮ Identity-based interactive aggregate signatures from lattices ⋮ Cumulatively all-lossy-but-one trapdoor functions from standard assumptions ⋮ Cryptographic primitives with hinting property ⋮ Towards practical topology-hiding computation ⋮ From the hardness of detecting superpositions to cryptography: quantum public key encryption and commitments ⋮ Semantic embedding for quantum algorithms ⋮ Quantum mutual implicit authentication key agreement protocol without entanglement with key recycling ⋮ A framework for practical anonymous credentials from lattices ⋮ A fully secure lattice-based signcryption with designated equality test in standard model ⋮ An Efficient Algorithm for Integer Lattice Reduction ⋮ Public-coin 3-round zero-knowledge from learning with errors and keyless multi-collision-resistant hash ⋮ Securing approximate homomorphic encryption using differential privacy ⋮ Maliciously secure massively parallel computation for all-but-one corruptions ⋮ On the hardness of the NTRU problem ⋮ Balanced non-adjacent forms ⋮ Transciphering framework for approximate homomorphic encryption ⋮ A new lattice-based online/offline signatures framework for low-power devices ⋮ Lattice-based inner product argument ⋮ Leveled Hierarchical Identity-Based Fully Homomorphic Encryption from Learning with Rounding ⋮ A New Insight—Proxy Re-encryption Under LWE with Strong Anti-collusion ⋮ A survey on functional encryption ⋮ The direction of updatable encryption does matter ⋮ Public-key encryption from homogeneous CLWE ⋮ Public key authenticated encryption with keyword search from LWE ⋮ No-directional and backward-leak uni-directional updatable encryption are equivalent ⋮ Concrete security from worst-case to average-case lattice reductions ⋮ Fast blind rotation for bootstrapping FHEs ⋮ HERMES: efficient ring packing using MLWE ciphertexts and application to transciphering ⋮ Accelerating HE operations from key decomposition technique ⋮ Simple tests of quantumness also certify qubits ⋮ A detailed analysis of Fiat-Shamir with aborts ⋮ Toward practical lattice-based proof of knowledge from Hint-MLWE ⋮ HRA-secure attribute-based threshold proxy re-encryption from lattices ⋮ \(\mathrm{mR}_{\mathrm{LWE}}\)-CP-ABE: a revocable CP-ABE for post-quantum cryptography ⋮ Subfield algorithms for ideal- and module-SVP based on the decomposition group ⋮ Mathematics of computation through the lens of linear equations and lattices ⋮ A lattice-based forward secure IBE scheme for Internet of things ⋮ Just Take the Average! An Embarrassingly Simple $2^n$-Time Algorithm for SVP (and CVP) ⋮ Deterministic compression with uncertain priors ⋮ Constructing concrete hard instances of the maximum independent set problem ⋮ The Average-Case Complexity of Counting Cliques in Erdös--Rényi Hypergraphs ⋮ One-Shot Verifiable Encryption from Lattices ⋮ Short Stickelberger Class Relations and Application to Ideal-SVP ⋮ Private Puncturable PRFs from Standard Lattice Assumptions ⋮ Constraint-Hiding Constrained PRFs for NC $$^1$$ from LWE ⋮ On Dual Lattice Attacks Against Small-Secret LWE and Parameter Choices in HElib and SEAL ⋮ Magic Adversaries Versus Individual Reduction: Science Wins Either Way ⋮ The truth behind the myth of the folk theorem ⋮ Expanders with respect to Hadamard spaces and random graphs ⋮ Unnamed Item ⋮ Limits of local algorithms over sparse random graphs ⋮ Round-optimal secure multi-party computation ⋮ Improved learning of \(k\)-parities ⋮ Verifying quantum computations at scale: A cryptographic leash on quantum devices ⋮ Novel Identity-Based Hash Proof System with Compact Master Public Key from Lattices in the Standard Model ⋮ Sumcheck-based delegation of quantum computing to rational server ⋮ Integer Version of Ring-LWE and Its Applications ⋮ On Quantum Chosen-Ciphertext Attacks and Learning with Errors ⋮ Hardness of bounded distance decoding on lattices in lp norms ⋮ Kissing Numbers and Transference Theorems from Generalized Tail Bounds ⋮ Survey of Lattice-Based Group Signature ⋮ Towards Round-Optimal Secure Multiparty Computations: Multikey FHE Without a CRS ⋮ Meta-heuristic approaches to solve shortest lattice vector problem ⋮ RLWE/PLWE equivalence for totally real cyclotomic subextensions via quasi-Vandermonde matrices ⋮ A Lattice-Based Certificateless Public Key Encryption with Equality Test in Standard Model ⋮ Attribute-Based Keyword Search from Lattices ⋮ On CCA-Secure Somewhat Homomorphic Encryption ⋮ Improved Information Set Decoding for Code-Based Cryptosystems with Constrained Memory ⋮ Trapdoors for Ideal Lattices with Applications ⋮ 3-Message Zero Knowledge Against Human Ignorance ⋮ Predicate Encryption for Circuits from LWE ⋮ Quantum Homomorphic Encryption for Circuits of Low T-gate Complexity ⋮ Coded-BKW: Solving LWE Using Lattice Codes ⋮ An Improved BKW Algorithm for LWE with Applications to Cryptography and Lattices ⋮ Provably Weak Instances of Ring-LWE ⋮ Multi-key FHE from LWE, Revisited ⋮ On the Efficacy of Solving LWE by Reduction to Unique-SVP ⋮ When NTT meets Karatsuba: preprocess-then-NTT technique revisited ⋮ Lattice Point Enumeration on Block Reduced Bases ⋮ Quantum learning Boolean linear functions w.r.t. product distributions ⋮ Quantum algorithms for typical hard problems: a perspective of cryptanalysis ⋮ On the hardness of module learning with errors with short distributions ⋮ On optimizing electricity markets performance ⋮ Multikey Fully Homomorphic Encryption and Applications ⋮ Adaptively secure inner product encryption from LWE ⋮ Towards classical hardness of module-LWE: the linear rank case ⋮ Security limitations of classical-client delegated quantum computing ⋮ Unnamed Item ⋮ Unclonable encryption, revisited ⋮ On error distributions in ring-based LWE ⋮ Simulatable verifiable random function from the LWE assumption ⋮ A Practical Post-Quantum Public-Key Cryptosystem Based on $$\textsf {spLWE}$$ ⋮ Analysis of Error Terms of Signatures Based on Learning with Errors ⋮ Aligned Drawings of Planar Graphs ⋮ Grid-Obstacle Representations with Connections to Staircase Guarding ⋮ 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 ⋮ BI-NTRU Encryption Schemes: Two New Secure Variants of NTRU ⋮ Unnamed Item ⋮ Tighter Security Proofs for Post-quantum Key Encapsulation Mechanism in the Multi-challenge Setting ⋮ Generic Construction of Bounded-Collusion IBE via Table-Based ID-to-Key Map ⋮ Agnostic Learning from Tolerant Natural Proofs ⋮ Identity-based blind signature from lattices ⋮ 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 ⋮ Finding Shortest Lattice Vectors in the Presence of Gaps ⋮ 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 ⋮ Better Key Sizes (and Attacks) for LWE-Based Encryption ⋮ An LWE-based verifiable threshold secret sharing scheme ⋮ A Noiseless Key-Homomorphic PRF: Application on Distributed Storage Systems ⋮ The Geometry of Lattice Cryptography ⋮ A novel fully homomorphic encryption scheme bsed on LWE ⋮ Naor-Yung Paradigm with Shared Randomness and Applications ⋮ How (Not) to Instantiate Ring-LWE ⋮ Sampling Exactly from the Normal Distribution ⋮ Three’s Compromised Too: Circular Insecurity for Any Cycle Length from (Ring-)LWE ⋮ Spooky Encryption and Its Applications ⋮ Fully Secure Functional Encryption for Inner Products, from Standard Assumptions ⋮ Unnamed Item ⋮ Quantum Hardness of Learning Shallow Classical Circuits ⋮ Pseudorandom Functions: Three Decades Later ⋮ Homomorphic Encryption ⋮ Weak Zero-Knowledge beyond the Black-Box Barrier ⋮ Compact ring signatures from learning with errors ⋮ A black-box approach to post-quantum zero-knowledge in constant rounds ⋮ Multi-theorem designated-verifier NIZK for QMA ⋮ On the hardness of module-LWE with binary secret ⋮ Shortest vectors in lattices of Bai-Galbraith's embedding attack on the LWR problem ⋮ Polly cracker, revisited ⋮ On basing search SIVP on \(\mathbf{NP}\)-hardness ⋮ Topology-hiding computation beyond semi-honest adversaries ⋮ Traitor-tracing from LWE made simple and attribute-based ⋮ Two-message statistically sender-private OT from LWE ⋮ Lattice-based certificateless encryption scheme ⋮ Puncturable pseudorandom sets and private information retrieval with near-optimal online bandwidth and time ⋮ Error analysis of weak poly-LWE instances ⋮ Tightly secure signatures from lossy identification schemes ⋮ Attribute-based conditional proxy re-encryption in the standard model under LWE ⋮ Cross-domain attribute-based access control encryption ⋮ On the higher-bit version of approximate inhomogeneous short integer solution problem ⋮ On the ring-LWE and polynomial-LWE problems ⋮ Fast near collision attack on the Grain v1 stream cipher ⋮ Non-commutative ring learning with errors from cyclic algebras ⋮ Efficient cryptosystems from \(2^k\)-th power residue symbols ⋮ Approximate CVP in time \(2^{0.802 n}\) -- now in any norm! ⋮ Lattice-based public-key encryption with equality test supporting flexible authorization in standard model ⋮ A note on the concrete hardness of the shortest independent vector in lattices ⋮ Naor-Yung paradigm with shared randomness and applications ⋮ Practical non-interactive publicly verifiable secret sharing with thousands of parties ⋮ \(\mathsf{Rubato}\): noisy ciphers for approximate homomorphic encryption ⋮ Single-server private information retrieval with sublinear amortized time ⋮ Watermarking PRFs against quantum adversaries ⋮ On the lattice isomorphism problem, quadratic forms, remarkable lattices, and cryptography ⋮ Constant-round blind classical verification of quantum sampling ⋮ A unified framework of identity-based sequential aggregate signatures from 2-level HIBE schemes ⋮ Toward non-interactive zero-knowledge proofs for NP from LWE ⋮ Bootstrapping for helib ⋮ Scalable revocable identity-based signature over lattices in the standard model ⋮ From cryptomania to obfustopia through secret-key functional encryption ⋮ Algebraically structured LWE. Revisited ⋮ Matrix PRFs: constructions, attacks, and applications to obfuscation ⋮ Compressible FHE with applications to PIR ⋮ On the RLWE/PLWE equivalence for cyclotomic number fields ⋮ Cryptographic algorithms for privacy-preserving online applications ⋮ Bonsai trees, or how to delegate a lattice basis ⋮ Comparison analysis of Ding's RLWE-based key exchange protocol and NewHope variants ⋮ Improved analysis of the reduction from BDD to uSVP ⋮ Hardness of \(k\)-LWE and applications in traitor tracing ⋮ Security considerations for Galois non-dual RLWE families ⋮ Computational indistinguishability between quantum states and its cryptographic application ⋮ Group signature from lattices preserving forward security in dynamic setting ⋮ Lattice-based proxy-oriented identity-based encryption with keyword search for cloud storage ⋮ Solving the learning parity with noise's open question ⋮ Computational fuzzy extractors ⋮ STP-LWE: A variant of learning with error for a flexible encryption ⋮ Strongly secure authenticated key exchange from factoring, codes, and lattices ⋮ The projection games conjecture and the hardness of approximation of Super-SAT and related problems ⋮ HILA5: on reliability, reconciliation, and error correction for Ring LWE encryption ⋮ A public-key encryption scheme based on non-linear indeterminate equations ⋮ A simple provably secure AKE from the LWE problem ⋮ Everlasting multi-party computation ⋮ 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 ⋮ Enhancing Goldreich, Goldwasser and Halevi's scheme with intersecting lattices ⋮ On the structure of Boolean functions with small spectral norm ⋮ Verifying solutions to LWE with implications for concrete security ⋮ Towards a ring analogue of the leftover hash lemma ⋮ Collusion-resistant identity-based proxy re-encryption: lattice-based constructions in standard model ⋮ Parallel Cholesky-based reduction for the weighted integer least squares problem ⋮ On the condition number of the Vandermonde matrix of the \(n\)th cyclotomic polynomial ⋮ A lattice-based signcryption scheme without random oracles ⋮ Sampling from discrete Gaussians for lattice-based cryptography on a constrained device ⋮ Compact designated verifier NIZKs from the CDH assumption without pairings ⋮ Verifiable single-server private information retrieval from LWE with binary errors ⋮ Round-optimal blind signatures in the plain model from classical and quantum standard assumptions ⋮ A \(2^{n/2}\)-time algorithm for \(\sqrt{n} \)-SVP and \(\sqrt{n} \)-Hermite SVP, and an improved time-approximation tradeoff for (H)SVP ⋮ On the ideal shortest vector problem over random rational primes ⋮ On the security of homomorphic encryption on approximate numbers ⋮ Classical vs quantum random oracles ⋮ On the success probability of solving unique SVP via BKZ ⋮ On the integer polynomial learning with errors problem ⋮ Exact lattice sampling from non-Gaussian distributions ⋮ Group encryption: full dynamicity, message filtering and code-based instantiation ⋮ Wildcarded identity-based encryption from lattices ⋮ LWE from non-commutative group rings ⋮ Chosen-ciphertext lattice-based public key encryption with equality test in standard model ⋮ A new Gaussian sampling for trapdoor lattices with arbitrary modulus ⋮ Practical \(\mathsf{MP} \text{- }\mathsf{LWE}\)-based encryption balancing security-risk versus efficiency ⋮ Sharing privacy protected and statistically sound clinical research data using outsourced data storage ⋮ 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 ⋮ Slide reduction, revisited -- filling the gaps in SVP approximation ⋮ An optimized GHV-type HE scheme: simpler, faster, and more versatile ⋮ A new post-quantum multivariate polynomial public key encapsulation algorithm ⋮ Fiat-Shamir for repeated squaring with applications to PPAD-hardness and VDFs ⋮ Improved lattice enumeration algorithms by primal and dual reordering methods ⋮ Worst-case to average-case reductions for module lattices ⋮ Leveraging the hardness of dihedral coset problem for quantum cryptography ⋮ An improved quantum algorithm for the quantum learning with errors problem ⋮ Password protected secret sharing from lattices ⋮ On removing rejection conditions in practical lattice-based signatures ⋮ Key-homomorphic pseudorandom functions from LWE with small modulus
