A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem
From MaRDI portal
Publication:5700575
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
(99)- Quantum algorithms for algebraic problems
- SoK: how (not) to design and implement post-quantum cryptography
- Finding shortest lattice vectors faster using quantum search
- On the security of OSIDH
- A fusion algorithm for solving the hidden shift problem in finite abelian groups
- Leveraging the hardness of dihedral coset problem for quantum cryptography
- Deterministic algorithms for the hidden subgroup problem
- Orientations and the supersingular endomorphism ring problem
- \( L_1\)-norm ball for CSIDH: optimal strategy for choosing the secret key space
- scientific article; zbMATH DE number 7378736 (Why is no real title available?)
- Quantum algorithm design: techniques and applications
- Hidden stabilizers, the isogeny to endomorphism ring problem and the cryptanalysis of pSIDH
- Curves, Jacobians, and cryptography
- The quantum query complexity of the hidden subgroup problem is polynomial
- Applications of finite non-abelian simple groups to cryptography in the quantum era
- Breaking permutation-based pseudorandom cryptographic schemes using distributed exact quantum algorithms
- Quantum computation vs. firewalls
- \textsf{CSI-Otter}: isogeny-based (partially) blind signatures from the class group action with a twist
- Quantum algorithm for a generalized hidden shift problem
- On solving systems of diagonal polynomial equations over finite fields
- Constructing Carmichael numbers through improved subset-product algorithms
- On the quantum complexity of the continuous hidden subgroup problem
- Hidden shift quantum cryptanalysis and implications
- Towards practical key exchange from ordinary isogeny graphs
- A polynomial quantum algorithm for approximating the Jones polynomial
- Quantum key-recovery on full AEZ
- Sample complexity of hidden subgroup problem
- Quantum algorithms for typical hard problems: a perspective of cryptanalysis
- A review of mathematical and computational aspects of CSIDH algorithms
- Semidirect product key exchange: the state of play
- Complexity classes of equivalence problems revisited
- Convergence rates of random walk on irreducible representations of finite groups
- Three-state quantum walk on the Cayley graph of the dihedral group
- DeCSIDH: delegating isogeny computations in the CSIDH setting
- Exhaustion 2-subsets in dihedral groups of order \(2 p\)
- B-SIDH: supersingular isogeny Diffie-Hellman using twisted torsion
- He gives C-sieves on the CSIDH
- Quantum security analysis of CSIDH
- Quantum mechanics on finite groups
- On the empirical scaling of run-time for finding optimal solutions to the travelling salesman problem
- Quantum binary search algorithm
- Attack on SHealS and HealS: the second wave of GPST
- Computational problems in supersingular elliptic curve isogenies
- On the hardness of the computational ring-LWR problem and its applications
- Quantum lattice enumeration and tweaking discrete pruning
- Простейшие надгруппы регулярных представлений неабелевых $2$-групп с циклической подгруппой индекса $2$
- Lossy CSI-fish: efficient signature scheme with tight reduction to decisional CSIDH-512
- Orienting supersingular isogeny graphs
- Breaking symmetric cryptosystems using the offline distributed Grover-Meets-Simon algorithm
- A hidden shift quantum algorithm
- Permutation groups, minimal degrees and quantum computing.
- A trade-off between classical and quantum circuit size for an attack against CSIDH
- Another Subexponential-time Quantum Algorithm for the Dihedral Hidden Subgroup Problem
- Quantum Lower Bounds for Tripartite Versions of the Hidden Shift and the Set Equality Problems
- Post-quantum adaptor signature for privacy-preserving off-chain payments
- Quantum algorithms for variants of average-case lattice problems via filtering
- A subexponential-time, polynomial quantum space algorithm for inverting the CM group action
- The independence of reduced subgroup-state
- Zero sum subsequences and hidden subgroups
- Efficient quantum algorithms for some instances of the semidirect discrete logarithm problem
- Group signatures and more from isogenies and lattices: generic, simple, and efficient
- Full quantum equivalence of group action DLog and CDH, and more
- Algebraic Methods in Quantum Informatics
- Full quantum equivalence of group action DLog and CDH, and more
- Computational indistinguishability between quantum states and its cryptographic application
- A lower bound on the length of signatures based on group actions and generic isogenies
- CSI-Otter: isogeny-based (partially) blind signatures from the class group action with a twist
- Practical post-quantum signature schemes from isomorphism problems of trilinear forms
- Low memory attacks on small key CSIDH
- 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)\)
- Properties of permutation representations of nonabelian 2-groups with a cyclic subgroup of index 2
- SCALLOP-HD: group action from 2-dimensional isogenies
- Isogeny problems with level structure
- Provable dual attacks on learning with errors
- On the power of non-adaptive learning graphs
- Quantum Algorithms for Abelian Difference Sets and Applications to Dihedral Hidden Subgroups
- Optimal measurements for the dihedral hidden subgroup problem
- Query complexity of generalized Simon's problem
- Multi-query quantum sums
- Quantum complexity for discrete logarithms and related problems
- SPDH-Sign: Towards Efficient, Post-quantum Group-Based Signatures
- Time and Query Complexity Tradeoffs for the Dihedral Coset Problem
- The dihedral hidden subgroup problem
- Quantum algorithm based on the \(\varepsilon\)-random linear disequations for the continuous hidden shift problem
- Cryptographic group actions and applications
- The Complexity of Public-Key Cryptography
- Oblivious pseudorandom functions from isogenies
- Solving systems of diagonal polynomial equations over finite fields
- Quantum pattern matching fast on average
- Quantum Algorithms to Solve the Hidden Shift Problem for Quadratics and for Functions of Large Gowers Norm
- Quantum-Secure Symmetric-Key Cryptography Based on Hidden Shifts
- CSIDH: an efficient post-quantum commutative group action
- On the robustness of bucket brigade quantum RAM
- Post-quantum \(\kappa\)-to-1 trapdoor claw-free functions from extrapolated dihedral cosets
- Two remarks on the vectorization problem
- SCALLOP: scaling the CSI-FiSh
- Generic models for 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)
