A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem
From MaRDI portal
Publication:5700575
DOI10.1137/S0097539703436345zbMath1084.81019arXivquant-ph/0302112OpenAlexW2057065544WikidataQ56018876 ScholiaQ56018876MaRDI QIDQ5700575
Publication date: 28 October 2005
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/quant-ph/0302112
Related Items
SoK: how (not) to design and implement post-quantum cryptography, On the empirical scaling of run-time for finding optimal solutions to the travelling salesman problem, 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, Quantum computation vs. firewalls, On Solving Systems of Diagonal Polynomial Equations Over Finite Fields, Multi-query Quantum Sums, Post-quantum adaptor signature for privacy-preserving off-chain payments, Quantum Algorithms to Solve the Hidden Shift Problem for Quadratics and for Functions of Large Gowers Norm, Свойства регулярных представлений неабелевых $2$-групп с циклической подгруппой индекса $2$, Quantum mechanics on finite groups, Exhaustion 2-subsets in dihedral groups of order 2p, 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, On the Security of OSIDH, Sample complexity of hidden subgroup problem, Finding shortest lattice vectors faster using quantum search, Breaking symmetric cryptosystems using the offline distributed Grover-Meets-Simon algorithm, Quantum algorithms for typical hard problems: a perspective of cryptanalysis, 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, A subexponential-time, polynomial quantum space algorithm for inverting the CM group action, 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, Quantum algorithm based on the \(\varepsilon\)-random linear disequations for the continuous hidden shift problem, \( L_1\)-norm ball for CSIDH: optimal strategy for choosing the secret key space, DeCSIDH: delegating isogeny computations in the CSIDH setting, Three-state quantum walk on the Cayley graph of the dihedral group, Attack on SHealS and HealS: the second wave of GPST, Two remarks on the vectorization problem, Zero sum subsequences and hidden subgroups, Cryptographic group actions and applications, B-SIDH: supersingular isogeny Diffie-Hellman using twisted torsion, Oblivious pseudorandom functions from isogenies, Unnamed Item, Computational indistinguishability between quantum states and its cryptographic application, Algebraic Methods in Quantum Informatics, Towards practical key exchange from ordinary isogeny graphs, CSIDH: an efficient post-quantum commutative group action, The independence of reduced subgroup-state, Quantum algorithm design: techniques and applications, On the robustness of bucket brigade quantum RAM, On the power of non-adaptive learning graphs, A polynomial quantum algorithm for approximating the Jones polynomial, Solving systems of diagonal polynomial equations over finite fields, Permutation groups, minimal degrees and quantum computing., Quantum key-recovery on full AEZ, Quantum pattern matching fast on average, Quantum Lower Bounds for Tripartite Versions of the Hidden Shift and the Set Equality Problems, Computational problems in supersingular elliptic curve isogenies, Convergence rates of random walk on irreducible representations of finite groups, Group signatures and more from isogenies and lattices: generic, simple, and efficient, Complexity classes of equivalence problems revisited, Orienting supersingular isogeny graphs, A trade-off between classical and quantum circuit size for an attack against CSIDH, Quantum algorithms for algebraic problems, 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)\), Curves, Jacobians, and cryptography, Quantum binary search algorithm, Leveraging the hardness of dihedral coset problem for quantum cryptography, Deterministic algorithms for the hidden subgroup problem, The Complexity of Public-Key Cryptography, Constructing Carmichael numbers through improved subset-product algorithms, Простейшие надгруппы регулярных представлений неабелевых $2$-групп с циклической подгруппой индекса $2$, 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, He gives C-sieves on the CSIDH, Quantum security analysis of CSIDH
