# Are there post-quantum cryptosystems with a gap between classical and quantum security?

Is there a gap between classical attacks and quantum attacks against some post-quantum security assumptions? (I'm particularly interested in asymmetric cryptography.)

I understand that there is no polynomial-time algorithm against these problems (otherwise it will no longer be considered as a PQ security assumption). But is it sometimes the case that we know more efficient quantum attacks than classical attacks (even if it's still exponential)?

• You can run standard algorithms on a quantum computer. So even if there is a gap, it would not be a gap for somebody owning a big quantum computer, I suppose. Sep 11, 2019 at 10:13
• @MaartenBodewes But those standard algorithms might require more memory than the quantum computer has. In that way, it's just as capable of running all standard algorithms as a classical computer is of running quantum algorithms (it can, but the amount of memory it would require would be inconceivable).
– forest
Sep 12, 2019 at 7:22

Here's an example where the best known quantum attack is, in a sense, just "halfway" between the best known classical attack on one side, and a complete break on the other: Inverting a cryptographic group action such as CSIDH.

Let $$G$$ be a (finite) commutative group $$G$$ acting on a set $$X$$, i.e., we consider a map $$\ast\colon\; G\times X\to X$$ that is compatible with the group structure of $$G$$ in the sense that $$1\ast x=x$$ and $$(g\cdot h)\ast x=g\ast(h\ast x)$$.

The problem to be solved is analogous to the discrete-logarithm problem:

Given two elements $$x,y\in X$$, find $$g\in G$$ with $$g\ast x=y$$, assuming it exists.

Classically, the best known attack is a meet-in-the-middle approach à la baby-step giant-step, where the group $$G$$ is split into two subsets $$U,V\subseteq G$$ such that $$G=U\cdot V$$, and one looks for a collision between the two sets $$U\ast x$$ and $$V^{-1}\ast y$$. Indeed, when $$u\ast x=v^{-1}\ast y$$, then $$(u\cdot v)\ast x=y$$. This takes time and space $$O(\!\sqrt{\lvert G\rvert})$$, which is exponential in $$\log{\lvert G\rvert}$$.
(In reality, there are better time-space tradeoffs than this simplistic approach.)

Quantumly however, this problem can be attacked using Kuperberg's algorithm [1,2] for the abelian hidden shift problem, and this takes subexponential (but superpolynomial) time in the group size. More concretely, the asymptotic cost is $${\exp}\Big(\!\sqrt{\log{\lvert G\rvert}}+o(1)\Big) \text,$$ which can be roughly summarized as "taking a square root in the exponent".
(For comparison, the number field sieve for integer factorization is also subexponential, but with a cube root.)

• Thanks for the answer, and do you know if there is a similar phenomena with some lattice problem? Sep 12, 2019 at 7:49