4
$\begingroup$

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)?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Maarten Bodewes Sep 11 at 10:13
  • $\begingroup$ @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). $\endgroup$ – forest Sep 12 at 7:22
5
$\begingroup$

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.)

$\endgroup$
  • $\begingroup$ Thanks for the answer, and do you know if there is a similar phenomena with some lattice problem? $\endgroup$ – Ievgeni Sep 12 at 7:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.