Quantum Computation and Lattice Problems

DOI10.1137/S0097539703440678zbMath1057.81012OpenAlexW2171692676MaRDI QIDQ4651491

Oded Regev

Publication date: 21 February 2005

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539703440678

zbMATH Keywords

quantum computationlatticesshortest vector problemhidden subgroup problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Quantum computation (81P68) Lattices and convex bodies (number-theoretic aspects) (11H06) Approximation algorithms (68W25)

Related Items (25)

An approach by representation of algebras for decoherence-free subspaces ⋮ On Solving Systems of Diagonal Polynomial Equations Over Finite Fields ⋮ Practical post-quantum signature schemes from isomorphism problems of trilinear forms ⋮ General linear group action on tensors: a candidate for post-quantum cryptography ⋮ Sample complexity of hidden subgroup problem ⋮ NTRU Fatigue: How Stretched is Overstretched? ⋮ Quantum algorithms for typical hard problems: a perspective of cryptanalysis ⋮ On the Complexity of the Hidden Subgroup Problem ⋮ Quantum algorithm based on the \(\varepsilon\)-random linear disequations for the continuous hidden shift problem ⋮ An efficient quantum algorithm for the hidden subgroup problem in nil-2 groups ⋮ Quantum cryptography beyond quantum key distribution ⋮ Computational indistinguishability between quantum states and its cryptographic application ⋮ The independence of reduced subgroup-state ⋮ Explicit Hard Instances of the Shortest Vector Problem ⋮ Using quantum key distribution for cryptographic purposes: a survey ⋮ Quantum algorithm design: techniques and applications ⋮ Solving systems of diagonal polynomial equations over finite fields ⋮ Complexity classes of equivalence problems revisited ⋮ Quantum algorithms for algebraic problems ⋮ Leveraging the hardness of dihedral coset problem for quantum cryptography ⋮ Deterministic algorithms for the hidden subgroup problem ⋮ The Complexity of Public-Key Cryptography ⋮ Quantum-Secure Symmetric-Key Cryptography Based on Hidden Shifts ⋮ A fusion algorithm for solving the hidden shift problem in finite abelian groups ⋮ On the quantum complexity of the continuous hidden subgroup problem

This page was built for publication: Quantum Computation and Lattice Problems