Quantum algorithms for variants of average-case lattice problems via filtering

DOI10.1007/978-3-031-07082-2_14zbMath1502.81025arXiv2108.11015OpenAlexW3203077771MaRDI QIDQ2170094

Yilei Chen, Mark Zhandry, Qipeng Liu

Publication date: 30 August 2022

Full work available at URL: https://arxiv.org/abs/2108.11015

Mathematics Subject Classification ID

Quantum computation (81P68) Cryptography (94A60) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40) Quantum information, communication, networks (quantum-theoretic aspects) (81P45) Quantum state spaces, operational and probabilistic concepts (81P16) Quantum mechanics on special spaces: manifolds, fractals, graphs, lattices (81Q35) Quantum cryptography (quantum-theoretic aspects) (81P94)

Uses Software

• Saber

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Lattice basis reduction: Improved practical algorithms and solving subset sum problems
• Saber: module-LWR based key exchange, CPA-secure encryption and CCA-secure KEM
• Learning with errors and extrapolated dihedral cosets
• Hardness of SIS and LWE with Small Parameters
• New Algorithms for Learning in Presence of Errors
• Collision-Free Hashing from Lattice Problems
• Trapdoors for hard lattices and new cryptographic constructions
• Improved cryptographic hash functions with worst-case/average-case connection
• Hidden translation and orbit coset in quantum computing
• Efficient Public Key Encryption Based on Ideal Lattices
• Efficient quantum algorithms for computing class groups and solving the principal ideal problem in arbitrary degree number fields
• Lossy Codes and a New Variant of the Learning-With-Errors Problem
• Kissing Numbers and Transference Theorems from Generalized Tail Bounds
• A quantum algorithm for computing the unit group of an arbitrary degree number field
• Constrained Key-Homomorphic PRFs from Standard Lattice Assumptions
• Worst‐Case to Average‐Case Reductions Based on Gaussian Measures
• Efficient Fully Homomorphic Encryption from (Standard) LWE
• Attribute-based encryption for circuits
• A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem
• Short Stickelberger Class Relations and Application to Ideal-SVP
• Recovering Short Generators of Principal Ideals in Cyclotomic Rings
• On lattices, learning with errors, random linear codes, and cryptography

This page was built for publication: Quantum algorithms for variants of average-case lattice problems via filtering