3
$\begingroup$

I have not found a specific answer to this question on here.

Shor's algorithm can be used to factorize a large (semi)prime $N$ by reducing the task to period-finding of a function $f(x)=x^a$ mod $N$.

This is done by creating an equal superposition over all pairs of $a_i$ and $f(x)=x^{a_i}$ for a random $x$, then measuring $f(x)$ causing the superposition to collapse into all $a_i$ for which $f(x)$ is our measures value. Using "Fourier sampling" (I have not fully understood this part) we can then obtain the period of $\ f$ and with .5 probability this yields a non-trivial square root of $N$ which leads to a prime factor.

(Plase correct me if my understanding of the above is flawed)

Now how can this algorithm be applied to Elliptic Curve schemes like ECDSA? I struggle to find an explanation for how the discrete log problem for groups over elliptic curves could be solved using Shor's.

EDIT: I would just as well appreciate a reference to other papers except Shor's, that explain the case of Shor's algorithm on DLPs.

$\endgroup$
  • 1
    $\begingroup$ Do you understand how the discrete logarithm problem is solved over $\mathbb Z^*_p$ using Shor's algorithm? $\endgroup$ – SEJPM Nov 2 '17 at 20:20
  • $\begingroup$ I read Shor's paper but did not understand the DLP part. From what I learned, if our $\mathbb{Z}_p^\ast$ DLP is find $r$ so that $g^r \equiv x$ mod $p$, we create superpositions over all $\ket{a}$ and $\ket{b}$ and calculate $g^ax^{-b}$ mod $p$. What is this good for to find the order of the group we are looking for? $\endgroup$ – indiscreteLogarithm Nov 2 '17 at 20:46
  • $\begingroup$ You may find this reference arxiv.org/abs/quant-ph/0301141 , interesting (found via the always useful quantum algorithm zoo math.nist.gov/quantum/zoo) $\endgroup$ – Frédéric Grosshans Nov 3 '17 at 10:02
  • $\begingroup$ @Frédéric Grosshans thanks for the reference, I read this paper but could you maybe give a few sentences describing what is done, like I did for integer factorization in the initial post? I can read the formulas in the paper, but I'm uncertain what they actually do. $\endgroup$ – indiscreteLogarithm Nov 4 '17 at 11:50
1
$\begingroup$

Section 2.2 of the following paper details how to apply Shor's algorithm to ECDLP: https://eprint.iacr.org/2017/598.pdf

Shor's algorithm circuit applied to ECDLP

The process is similar to DLP, except that we need different circuits to perform our our group operations in elliptic curves (additions and scalar multiplications).

$\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.