3
$\begingroup$

I was wondering what the "accepted" way is to describe an adversary who:

  • is in possession of a quantum computer with which they can efficiently run quantum algorithms such as Grover's or Shor's algorithm.
  • Is polynomially bounded with regard to solving problems for which no quantum algorithms exist (e.g. finding hash collisions).

I was thinking of something like: quantum capable polynomial time bounded adversary. But I'm not sure whether being able to run quantum algorithms while being polynomial bounded is some kind of paradox?

$\endgroup$
  • $\begingroup$ An Oracle that can find a collision to any (polynomial-time) function in polynomial time is extremely powerful; you can solve any problem in NP in polynomial time with it (!). It's not clear how much adding a 'quantum computer' on the side really adds to it. $\endgroup$ – poncho Jul 10 '17 at 13:15
  • $\begingroup$ I personally understand "quantum capable polynomial time bounded adversary" as being "someone who's got a quantum computer able to run Shor's and Grover's algo on problems of practical size, while not having any other advantages beside having such a big quantum computer". I wouldn't understand it as being someone whose got such an oracle as @poncho described. Note that more and more, such adversaries are simply qualified as "post-quantum adversaries" $\endgroup$ – Lery Jul 10 '17 at 15:37
  • $\begingroup$ @Lery: note that Grover's algorithm takes exponential time, and so a 'polynomial bounded adversary' might not be able to run it... $\endgroup$ – poncho Jul 10 '17 at 15:50
  • $\begingroup$ @poncho Only if you run it on exponential functions. :) $\endgroup$ – Lery Jul 10 '17 at 16:08
  • 1
    $\begingroup$ Can you just make a reference to the BQP class of decision problems? That class has a very specific meaning which looks like its aligned with yours. $\endgroup$ – Cort Ammon Jul 10 '17 at 20:19
5
$\begingroup$

I think what you are looking for is an adversary that

  • has access to a quantum computer, and
  • is efficient (i.e., runs in polynomial time -> independent of the property it tries to attack).

In this case, the common way to model the adversary is just as a polynomial time quantum algorithm. Note, it depends on the security model for the property that the adversary tries to attack (e.g., collision resistance, or EU-CMA) if it gets quantum access to a primitive or not, not on the adversary model. Schemes which achieve security in terms of traditional security definitions (i.e., with no quantum access to secretly keyed resources) against any polynomial time quantum algorithm are what we call post-quantum cryptography.

As in the traditional / classical setting, the question if a certain problem like the MQ-problem still is hard when considering such polynomial time quantum algorithms boils down to an assumption again: We do not have a proof that there exists no polynomial time quantum algorithm that solves MQ / SVP / [choose your favourite PQ problem] with noticeable success probability. However, we got reason to believe that no such algorithm exists.

$\endgroup$

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.