A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem
From MaRDI portal
Abstract: We present a quantum algorithm for the dihedral hidden subgroup problem with time and query complexity . In this problem an oracle computes a function on the dihedral group which is invariant under a hidden reflection in . By contrast the classical query complexity of DHSP is . The algorithm also applies to the hidden shift problem for an arbitrary finitely generated abelian group. The algorithm begins with the quantum character transform on the group, just as for other hidden subgroup problems. Then it tensors irreducible representations of and extracts summands to obtain target representations. Finally, state tomography on the target representations reveals the hidden subgroup.
Recommendations
Cited in
(only showing first 100 items - show all)- 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
- Quantum algorithm design: techniques and applications
- Quantum key-recovery on full AEZ
- Computational problems in supersingular elliptic curve isogenies
- Orienting supersingular isogeny graphs
- A trade-off between classical and quantum circuit size for an attack against CSIDH
- Query complexity of generalized Simon's problem
- Lossy CSI-fish: efficient signature scheme with tight reduction to decisional CSIDH-512
- Threshold schemes from isogeny assumptions
- One-way functions and malleability oracles: hidden shift attacks on isogeny-based protocols
- CSURF-TWO: CSIDH for the ratio \((2:1)\)
- Leveraging the hardness of dihedral coset problem for quantum cryptography
- Deterministic algorithms for the hidden subgroup problem
- A fusion algorithm for solving the hidden shift problem in finite abelian groups
- On the quantum complexity of the continuous hidden subgroup problem
- He gives C-sieves on the CSIDH
- Quantum security analysis of CSIDH
- Post-quantum adaptor signature for privacy-preserving off-chain payments
- Orientations and the supersingular endomorphism ring problem
- Quantum algorithms for variants of average-case lattice problems via filtering
- 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 binary search algorithm
- Quantum dual adversary for hidden subgroups and beyond
- The quantum query complexity of the hidden subgroup problem is polynomial
- Permutation groups, minimal degrees and quantum computing.
- Convergence rates of random walk on irreducible representations of finite groups
- Sample complexity of hidden subgroup problem
- 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
- L₁-norm ball for CSIDH: optimal strategy for choosing the secret key space
- Three-state quantum walk on the Cayley graph of the dihedral group
- Cryptographic group actions and applications
- B-SIDH: supersingular isogeny Diffie-Hellman using twisted torsion
- Oblivious pseudorandom functions from isogenies
- A hidden shift quantum algorithm
- Constructing Carmichael numbers through improved subset-product algorithms
- Quantum algorithm for a generalized hidden shift problem
- Another Subexponential-time Quantum Algorithm for the Dihedral Hidden Subgroup Problem
- On the empirical scaling of run-time for finding optimal solutions to the travelling salesman problem
- Quantum computation vs. firewalls
- Quantum algorithms for algebraic problems
- Quantum Algorithms to Solve the Hidden Shift Problem for Quadratics and for Functions of Large Gowers Norm
- On solving systems of diagonal polynomial equations over finite fields
- Multi-query quantum sums
- Algebraic Methods in Quantum Informatics
- Optimal measurements for the dihedral hidden subgroup problem
- Computational indistinguishability between quantum states and its cryptographic application
- Exhaustion 2-subsets in dihedral groups of order 2 p
- The independence of reduced subgroup-state
- On the power of non-adaptive learning graphs
- On learning linear functions from subset and its applications in quantum computing
- The Complexity of Public-Key Cryptography
- Properties of permutation representations of nonabelian 2-groups with a cyclic subgroup of index 2
- Solving systems of diagonal polynomial equations over finite fields
- On the security of OSIDH
- Quantum pattern matching fast on average
- On the robustness of bucket brigade quantum RAM
- Curves, Jacobians, and cryptography
- Quantum-Secure Symmetric-Key Cryptography Based on Hidden Shifts
- Quantum Algorithms for Abelian Difference Sets and Applications to Dihedral Hidden Subgroups
- Простейшие надгруппы регулярных представлений неабелевых 2-групп с циклической подгруппой индекса 2
- Quantum Lower Bounds for Tripartite Versions of the Hidden Shift and the Set Equality Problems
- A polynomial quantum algorithm for approximating the Jones polynomial
- Group signatures and more from isogenies and lattices: generic, simple, and efficient
- Breaking symmetric cryptosystems using the offline distributed Grover-Meets-Simon algorithm
- SCALLOP: scaling the CSI-FiSh
- Generic models for group actions
- A lower bound on the length of signatures based on group actions and generic isogenies
- Full quantum equivalence of group action DLog and CDH, and more
- \textsf{CSI-Otter}: isogeny-based (partially) blind signatures from the class group action with a twist
- DeCSIDH: delegating isogeny computations in the CSIDH setting
- Attack on SHealS and HealS: the second wave of GPST
- Two remarks on the vectorization problem
- Zero sum subsequences and hidden subgroups
- SPDH-Sign: Towards Efficient, Post-quantum Group-Based Signatures
- Time and Query Complexity Tradeoffs for the Dihedral Coset Problem
- The dihedral hidden subgroup problem
- Low memory attacks on small key CSIDH
- Post-quantum \(\kappa\)-to-1 trapdoor claw-free functions from extrapolated dihedral cosets
- Applications of finite non-abelian simple groups to cryptography in the quantum era
- Breaking permutation-based pseudorandom cryptographic schemes using distributed exact quantum algorithms
- A review of mathematical and computational aspects of CSIDH algorithms
- Semidirect product key exchange: the state of play
- Hidden stabilizers, the isogeny to endomorphism ring problem and the cryptanalysis of pSIDH
- Efficient quantum algorithms for some instances of the semidirect discrete logarithm problem
- CSI-Otter: isogeny-based (partially) blind signatures from the class group action with a twist
- SCALLOP-HD: group action from 2-dimensional isogenies
- Isogeny problems with level structure
- Provable dual attacks on learning with errors
- Full quantum equivalence of group action DLog and CDH, and more
- Quantum complexity for discrete logarithms and related problems
- LWE with quantum amplitudes: Algorithm, hardness, and oblivious sampling
- Quantum state group actions
- A quasi-polynomial time algorithm for the extrapolated dihedral coset problem over power-of-two moduli
- Deterministic algorithms for class group actions
This page was built for publication: A 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 Q5700575)
