Another Subexponential-time Quantum Algorithm for the Dihedral Hidden Subgroup Problem
From MaRDI portal
Abstract: We give an algorithm for the hidden subgroup problem for the dihedral group , or equivalently the cyclic hidden shift problem, that supersedes our first algorithm and is suggested by Regev's algorithm. It runs in quantum time and uses classical space, but only quantum space. The algorithm also runs faster with quantumly addressable classical space than with fully classical space. In the hidden shift form, which is more natural for this algorithm regardless, it can also make use of multiple hidden shifts. It can also be extended with two parameters that trade classical space and classical time for quantum time. At the extreme space-saving end, the algorithm becomes Regev's algorithm. At the other end, if the algorithm is allowed classical memory with quantum random access, then many trade-offs between classical and quantum time are possible.
Recommendations
- A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem
- An Efficient Quantum Algorithm for the Hidden Subgroup Problem in Extraspecial Groups
- Efficient quantum algorithms for the hidden subgroup problem over semi-direct product groups
- EFFICIENT QUANTUM ALGORITHMS FOR SOME INSTANCES OF THE NON-ABELIAN HIDDEN SUBGROUP PROBLEM
- An Efficient Quantum Algorithm for the Hidden Subgroup Problem over Weyl-Heisenberg Groups
- An Efficient Quantum Algorithm for the Hidden Subgroup Problem in Nil-2 Groups
- An efficient quantum algorithm for the hidden subgroup problem in nil-2 groups
- Quantum hidden subgroup algorithms: an algorithmic toolkit
- Hidden subgroup quantum algorithms for a class of semi-direct product groups
- Quantum algorithms for the hidden subgroup problem on some semi-direct product groups by reduction to abelian cases
Cited in
(57)- Quantum lattice enumeration and tweaking discrete pruning
- On the hardness of the computational ring-LWR problem and its applications
- Hidden shift quantum cryptanalysis and implications
- Towards practical key exchange from ordinary isogeny graphs
- CSIDH: an efficient post-quantum commutative group action
- A trade-off between classical and quantum circuit size for an attack against CSIDH
- Lossy CSI-fish: efficient signature scheme with tight reduction to decisional CSIDH-512
- Threshold schemes from isogeny assumptions
- Leveraging the hardness of dihedral coset problem for quantum cryptography
- A fusion algorithm for solving the hidden shift problem in finite abelian groups
- Optimal merging in quantum k-xor and k-sum algorithms
- He gives C-sieves on the CSIDH
- Quantum security analysis of CSIDH
- Post-quantum adaptor signature for privacy-preserving off-chain payments
- Practical post-quantum signature schemes from isomorphism problems of trilinear forms
- A subexponential-time, polynomial quantum space algorithm for inverting the CM group action
- Quantum algorithms for typical hard problems: a perspective of cryptanalysis
- Quantum algorithm based on the \(\varepsilon\)-random linear disequations for the continuous hidden shift problem
- Cryptographic group actions and applications
- Estimating quantum speedups for lattice sieves
- Improved classical and quantum algorithms for subset-sum
- A hidden shift quantum algorithm
- Quantum algorithm for a generalized hidden shift problem
- CSIDH on the surface
- Quantum pattern matching fast on average
- Quantum-Secure Symmetric-Key Cryptography Based on Hidden Shifts
- A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem
- New results on quantum boomerang attacks
- Group signatures and more from isogenies and lattices: generic, simple, and efficient
- A lower bound on the length of signatures based on group actions and generic isogenies
- Quantum impossible differential attacks: applications to AES and SKINNY
- Full quantum equivalence of group action DLog and CDH, and more
- Take your MEDS: digital signatures from matrix code equivalence
- \textsf{CSI-Otter}: isogeny-based (partially) blind signatures from the class group action with a twist
- Quantum time/memory/data tradeoff attacks
- Two remarks on the vectorization problem
- Quantum linear key-recovery attacks using the QFT
- Time and Query Complexity Tradeoffs for the Dihedral Coset Problem
- A review of mathematical and computational aspects of CSIDH algorithms
- Quantum attacks on hash constructions with low quantum random access memory
- Improved quantum algorithms for the k-XOR problem
- Cutting the GRASS: threshold group action signature schemes
- Isogeny problems with level structure
- Full quantum equivalence of group action DLog and CDH, and more
- Quantum complexity for discrete logarithms and related problems
- Deterministic algorithms for class group actions
- Quantum security of the Legendre PRF
- Higher-degree supersingular group actions
- Efficient post-quantum commutative group actions from orientations of large discriminant
- Another look at the quantum security of the vectorization problem with shifted inputs
- On the active security of the PEARL-SCALLOP group action
- Capybara and Tsubaki: verifiable random functions from group actions and isogenies
- Optimizing c-sum BKW and faster quantum variant for LWE
- Quantum procedures for nested search problems -- with applications in cryptanalysis
- Erebor and Durian: full anonymous ring signatures from quaternions and isogenies
- SoK: how (not) to design and implement post-quantum cryptography
- Low-gate quantum golden collision finding
This page was built for publication: Another Subexponential-time Quantum Algorithm for the Dihedral Hidden Subgroup Problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2958406)
