Quantum computers can break the RSA, El Gamal, and elliptic curve public-key cryptosystems, as they can efficiently factor integers and extract discrete logarithms. The power of such quantum attacks lies in \emph{quantum Fourier sampling}, an algorithmic paradigm based on generating and measuring coset states. %This motivates the investigation of the power or limitations of quantum Fourier sampling, especially in attacking candidates for ``post-quantum'' cryptosystems -- classical cryptosystems that can be implemented with today's computers but will remain secure even in the presence of quantum attacks. In this article we extend previous negative results of quantum Fourier sampling for Graph Isomorphism, which corresponds to hidden subgroups of order two (over S_n, to several cases corresponding to larger hidden subgroups. For one case, we strengthen some results of Kempe, Pyber, and Shalev on the Hidden Subgroup Problem over the symmetric group. In another case, we show the failure of quantum Fourier sampling on the Hidden Subgroup Problem over the general linear group GL_2(\FF_q). The most important case corresponds to Code Equivalence, the problem of determining whether two given linear codes are equivalent to each other up to a permutation of the coordinates. Our results suggest that for many codes of interest---including generalized Reed Solomon codes, alternant codes, and Reed-Muller codes---solving these instances of Code Equivalence via Fourier sampling appears to be out of reach of current families of quantum algorithms.
Quantum computers can break the RSA, El Gamal, and elliptic curve public-key cryptosystems, as they can efficiently factor integers and extract discrete logarithms. The power of such quantum attacks lies in \emph{quantum Fourier sampling}, an algorithmic paradigm based on generating and measuring coset states. %This motivates the investigation of the power or limitations of quantum Fourier sampling, especially in attacking candidates for ``post-quantum'' cryptosystems -- classical cryptosystems that can be implemented with today's computers but will remain secure even in the presence of quantum attacks. In this article we extend previous negative results of quantum Fourier sampling for Graph Isomorphism, which corresponds to hidden subgroups of order two (over S_n, to several cases corresponding to larger hidden subgroups. For one case, we strengthen some results of Kempe, Pyber, and Shalev on the Hidden Subgroup Problem over the symmetric group. In another case, we show the failure of quantum Fourier sampling on the Hidden Subgroup Problem over the general linear group GL_2(\FF_q). The most important case corresponds to Code Equivalence, the problem of determining whether two given linear codes are equivalent to each other up to a permutation of the coordinates. Our results suggest that for many codes of interest---including generalized Reed Solomon codes, alternant codes, and Reed-Muller codes---solving these instances of Code Equivalence via Fourier sampling appears to be out of reach of current families of quantum algorithms.
Abstract The hidden subgroup problem (HSP) is a cornerstone problem in quantum computing, which captures many problems of interest and provides a standard framework algorithm for their study based on Fourier sampling, one class of techniques known to provide quantum advantage, and which succeeds for some groups but not others. The quantum hardness of the HSP problem for the dihedral group is a critical question for post-quantum cryptosystems based on learning with errors and also appears in subexponential algorithms for constructing isogenies between elliptic curves over a finite field. In this article, we give an updated overview of the dihedral hidden subgroup problem as approached by the “standard” quantum algorithm for HSP on finite groups, detailing the obstructions for strong Fourier sampling to succeed and summarizing other known approaches and results. In our treatment, we “contrast and compare” as much as possible the cyclic and dihedral cases, with a view to determining bounds for the success probability of a quantum algorithm that uses m m coset samples to solve the HSP on these groups. In the last sections, we prove a number of no-go results for the dihedral coset problem (DCP), motivated by a connection between DCP and cloning of quantum states. The proofs of these no-go results are then adapted to give nontrivial upper bounds on the success probability of a quantum algorithm that uses m m coset samples to solve DCP.
The quantum hidden subgroup approach is an actively studied approach to solve combinatorial problems in quantum complexity theory. With the success of the Shor's algorithm, it was hoped that similar approach may be useful to solve the other combinatorial problems. One such problem is the graph isomorphism problem which has survived decades of efforts using the hidden subgroup approach. This paper provides a systematic approach to create arbitrarily large classes of classically efficiently solvable graph automorphism problems or easy graph automorphism problems for which hidden subgroup approach is guaranteed to always fail irrespective of the size of the graphs no matter how many copies of coset states are used. As the graph isomorphism problem is believed to be at least as hard as the graph automorphism problem, the result of this paper entails that the hidden subgroup approach is also guaranteed to always fail for the arbitrarily large classes of graph isomorphism problems. Combining these two results, it is argued that the hidden subgroup approach is essentially a dead end and alternative quantum algorithmic approach needs to be investigated for the graph isomorphism and automorphism problems.
Abstract In typical well-known cryptosystem, the hardness of classical problems plays a fundamental role in ensuring its security. While, with the booming of quantum computation, some classical hard problems tend to be vulnerable when confronted with the already-known quantum attacks, as a result, it is necessary to develop the post-quantum cryptosystem to resist the quantum attacks. With the purpose to bridge the two disciplines, it is significant to summarize known quantum algorithms and their threats toward these cryptographic intractable problems from a perspective of cryptanalysis. In this paper, we discussed the designing methodology, algorithm framework and latest progress of the mathematic hard problems on which the typical cryptosystems depend, including integer factorization problem, discrete logarithmic problem and its variants, lattice problem, dihedral hidden subgroup problems and extrapolated dihedral coset problem. It illustrated the reason why some cryptosystems such as RSA and ECC are not resistant to quantum attacks, yet some of them like lattice cryptosystems remain intact facing quantum attacks.
In the quest to identify further quantum algorithms exhibiting superpolynomial speed-ups, a recurring theme is that the complexity of a problem is largely shaped by the input access model. Here, we study this phenomenon for the state hidden subgroup problem (StateHSP), a quantum generalization of the hidden subgroup problem in which the goal is to identify the symmetries of an unknown quantum state. For finite abelian groups, existing Fourier-sampling algorithms use O(log(∣G∣)/ε) copies of the state, but whether this scaling is optimal has remained open. We settle the complexity of the abelian StateHSP in both the previously studied sample model and a new query model, which is a stronger and operationally natural generalization that provides access to the state-preparation unitary and its inverse. In the query model, we give a time-efficient quantum algorithm using O(log(∣G/H∣)/ε) forward and inverse queries, and prove a matching Ω(log(∣G/H∣)/ε) lower bound which holds even in the stronger conjugate-query and controlled-query settings. By contrast, we show that in the sample model, Θ(log(∣G/H∣)/ε) copies are both sufficient and information-theoretically necessary, even if one allows for arbitrary collective measurements. Thus, the quadratic improvement in ε genuinely arises from coherent access to the preparation circuit. As applications, we obtain faster algorithms for learning stabilizer groups, locating unentanglement, and identifying hidden translation symmetries.
I describe the role of symmetry in two quantum algorithms, with a focus on how that symmetry is made manifest by the Fourier transform. The Fourier transform can be considered in a wider context than the familiar one of functions on Rn or Z/nZ; instead it can be defined for an arbitrary group where it is known as representation theory. The first quantum algorithm solves an instance of the hidden subgroup problem--distinguishing conjugates of the Borel subgroup from each other in groups related to PSL(2; q). I use the symmetry of the subgroups under consideration to reduce the problem to a mild extension of a previously solved problem. This generalizes a result of Moore, Rockmore, Russel and Schulman[33] by switching to a more natural measurement that also applies to prime powers. In contrast to the first algorithm, the second quantum algorithm is an attempt to use naturally continuous spaces. Quantum walks have proved to be a useful tool for designing quantum algorithms. The natural equivalent to continuous time quantum walks is evolution with the Schrodinger equation, under the kinetic energy Hamiltonian for a massive particle. I take advantage of quantum interference to find the center of spherical shells in high dimensions. Any implementation would be likely to take place on a discrete grid, using the ability of a digital quantum computer to simulate the evolution of a quantum system. In addition, I use ideas from the second algorithm on a different set of starting states, and find that quantum evolution can be used to sample from the evolute of a plane curve. The method of stationary phase is used to determine scaling exponents characterizing the precision and probability of success for this procedure.
Contemporary cryptographic algorithms are resistant to the strongest threats to cybersecurity and high-profile cyber-attacks. In recent times, information security scientists and researchers had developed various cryptographic schemes that defeated attacks using the most sophisticated (in terms of processor speed) classical computer. However, this resistance will soon erode with the arrival of quantum computers. In this paper, we profiled quantum computers and quantum algorithms based on their widely believed threat against currently secure cryptographic primitives. We found that Grover’s and Shor’s quantum-based algorithms actually pose a threat to the continued security of symmetric cryptosystems (e.g. 128-bit AES) and asymmetric (public key) cryptosystems (e.g. RSA, Elgamal, elliptic curve Diffie Hellman (ECDH), etc.) respectively.We discovered that the source of the algorithms’ cryptanalytic power against the current systems, stems from the fact that they (Grover and Shor) both equipped their respective algorithms with a quantum circuit component that can execute the oracle in parallel by applying a single circuit to all possible states of an n-qubit input. With this exponential level of processing characteristic of quantum computers and quantum-based algorithms, it is easy for the current cryptosystems to be broken since the algorithms can existentially solve the underlying mathematical problems such as integer factorization, discrete logarithm problem and elliptic curve problem, which formed the basis of the security of the affected cryptosystems. Based on this realization and as part of our readiness for a post quantum era, we explored other mathematical structures (lattices, hashes, codes, isogenies, high entropy-based symmetric key resistance, and multivariate quadratic problems) whose hardness could surpass the cryptanalytic nightmare posed by quantum computers and quantum-based algorithms. Our contribution is that, based on the findings of this research work, we can confidently assert that all hope is not lost for organizations heavily relying on protocols and applications like HTTPS, TLS, PGP, Bitcoin, etc., which derived their security from the endangered cryptosystems.