A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem
From MaRDI portal
Publication:5700575
DOI10.1137/S0097539703436345zbMATH Open1084.81019DBLPjournals/siamcomp/Kuperberg05arXivquant-ph/0302112OpenAlexW2057065544WikidataQ56018876 ScholiaQ56018876MaRDI QIDQ5700575FDOQ5700575
Authors: Greg Kuperberg 
Publication date: 28 October 2005
Published in: SIAM Journal on Computing (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/quant-ph/0302112
Recommendations
Cited In (97)
- Hidden stabilizers, the isogeny to endomorphism ring problem and the cryptanalysis of pSIDH
- Multi-query Quantum Sums
- Applications of finite non-abelian simple groups to cryptography in the quantum era
- Breaking permutation-based pseudorandom cryptographic schemes using distributed exact quantum algorithms
- \textsf{CSI-Otter}: isogeny-based (partially) blind signatures from the class group action with a twist
- A review of mathematical and computational aspects of CSIDH algorithms
- Semidirect product key exchange: the state of play
- Свойства регулярных представлений неабелевых $2$-групп с циклической подгруппой индекса $2$
- DeCSIDH: delegating isogeny computations in the CSIDH setting
- Attack on SHealS and HealS: the second wave of GPST
- Простейшие надгруппы регулярных представлений неабелевых $2$-групп с циклической подгруппой индекса $2$
- Breaking symmetric cryptosystems using the offline distributed Grover-Meets-Simon algorithm
- Quantum Lower Bounds for Tripartite Versions of the Hidden Shift and the Set Equality Problems
- Zero sum subsequences and hidden subgroups
- Efficient quantum algorithms for some instances of the semidirect discrete logarithm problem
- Full quantum equivalence of group action DLog and CDH, and more
- Full quantum equivalence of group action DLog and CDH, and more
- 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
- Low memory attacks on small key CSIDH
- SCALLOP-HD: group action from 2-dimensional isogenies
- Isogeny problems with level structure
- Provable dual attacks on learning with errors
- 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
- Quantum algorithm based on the \(\varepsilon\)-random linear disequations for the continuous hidden shift problem
- Exhaustion 2-subsets in dihedral groups of order 2p
- Post-quantum \(\kappa\)-to-1 trapdoor claw-free functions from extrapolated dihedral cosets
- SCALLOP: scaling the CSI-FiSh
- Generic models for group actions
- SoK: how (not) to design and implement post-quantum cryptography
- Finding shortest lattice vectors faster using quantum search
- A fusion algorithm for solving the hidden shift problem in finite abelian groups
- Title not available (Why is that?)
- Leveraging the hardness of dihedral coset problem for quantum cryptography
- Deterministic algorithms for the hidden subgroup problem
- \( L_1\)-norm ball for CSIDH: optimal strategy for choosing the secret key space
- Orientations and the supersingular endomorphism ring problem
- Curves, Jacobians, and cryptography
- Quantum algorithm design: techniques and applications
- The quantum query complexity of the hidden subgroup problem is polynomial
- Quantum computation vs. firewalls
- Constructing Carmichael numbers through improved subset-product algorithms
- On the quantum complexity of the continuous hidden subgroup problem
- A polynomial quantum algorithm for approximating the Jones polynomial
- Hidden shift quantum cryptanalysis and implications
- Towards practical key exchange from ordinary isogeny graphs
- Quantum key-recovery on full AEZ
- Sample complexity of hidden subgroup problem
- Quantum algorithms for typical hard problems: a perspective of cryptanalysis
- Convergence rates of random walk on irreducible representations of finite groups
- Complexity classes of equivalence problems revisited
- Three-state quantum walk on the Cayley graph of the dihedral group
- B-SIDH: supersingular isogeny Diffie-Hellman using twisted torsion
- He gives C-sieves on the CSIDH
- Quantum security analysis of CSIDH
- Quantum binary search algorithm
- Quantum mechanics on finite groups
- Computational problems in supersingular elliptic curve isogenies
- On the empirical scaling of run-time for finding optimal solutions to the travelling salesman problem
- On the hardness of the computational ring-LWR problem and its applications
- Quantum lattice enumeration and tweaking discrete pruning
- Lossy CSI-fish: efficient signature scheme with tight reduction to decisional CSIDH-512
- Orienting supersingular isogeny graphs
- 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
- 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
- On Solving Systems of Diagonal Polynomial Equations Over Finite Fields
- Group signatures and more from isogenies and lattices: generic, simple, and efficient
- Algebraic Methods in Quantum Informatics
- Computational indistinguishability between quantum states and its cryptographic application
- On the Security of OSIDH
- Practical post-quantum signature schemes from isomorphism problems of trilinear forms
- 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)\)
- Quantum Algorithms for Abelian Difference Sets and Applications to Dihedral Hidden Subgroups
- On the power of non-adaptive learning graphs
- Optimal measurements for the dihedral hidden subgroup problem
- Query complexity of generalized Simon's 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-Secure Symmetric-Key Cryptography Based on Hidden Shifts
- Quantum Algorithms to Solve the Hidden Shift Problem for Quadratics and for Functions of Large Gowers Norm
- On the robustness of bucket brigade quantum RAM
- CSIDH: an efficient post-quantum commutative group action
- Two remarks on the vectorization problem
- Quantum algorithms for algebraic problems
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)
