I don't understand why discrete logarithm is not quantum proof. I understand that quantum computer can quickly compute the exponent, but there is a modulo in the equation. Doesn't it mean, that there are infinite possibilities? Doesn't modulo make it basically one way function? So quantum computer will give array with millions and billions of possible keys?
4
-
$\begingroup$ The DLP can be formulated in ways such that it has a single solution. And the question's reasoning would apply unchanged to classical computers, which can solve the DLP for small enough parameters. Thus I do not understand the argument made. $\endgroup$– fgrieu ♦Commented Jun 22 at 8:46
-
$\begingroup$ I mean that for example simple problem: 6 = 12^x mod 7, the equation will be true when x = 3 and when x=9, that's what I mean with infinite possibilities, that's not one solution $\endgroup$– pepa z depaCommented Jun 22 at 8:56
-
1$\begingroup$ The DLP problem is considered solved (for cryptographic purposes) as soon as you find any solution x (here 3 or 9). $\endgroup$– fgrieu ♦Commented Jun 22 at 9:34
-
$\begingroup$ Dupe of this How effective is quantum computing against elliptic curve cryptography? and maybe this How can Shor's Algorithm be applied to ECC? and maybe this Shor's algorithm for elliptic curve discrete logarithm problem, too $\endgroup$– kelalakaCommented Jun 22 at 17:32
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
0
The problem is by definition modular, and the equation is $$g^x\equiv h \pmod p$$ for the integer case. This equation a single solution since the map $x \mapsto g^x \pmod p$ is one to one. Thus there are $p-1$ possible values of $x$ to test assuming $h\neq 0.$ By making $p$ large enough, you obtain enough security in terms of the search for the solution. The best known generic classical algorithms (baby step giant step, pollard's rho) are exponential complexity (exponential in $\log p$) while the quantum attack using Shor's algorithm is polynomial in $\log p.$
$\begingroup$
$\endgroup$
The input and output are all over a finite field. There is no need to find a specific value. We find the value mod p, which as you say can be viewed as an infinite collection of natural numbers all equivalent modules p.
But that is the task, finding the solution over the finite field(e.g $Z_p$). We can't even with infinite compute find which larger natural number we started with, we don't need to.
One way function is not a function which loses information. A one way function is one whixh it's hard to find any preimage, that is given y find x such that $y = f(x)$.
Hypothetical quantom computers could run Shore's algorithm and efficiently solve the discrete logarithm problem.
