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

Improve this question
$\endgroup$
4
  • 3
    $\begingroup$ Do you understand how the discrete logarithm problem is solved over $\mathbb Z^*_p$ using Shor's algorithm? $\endgroup$
    – SEJPM
    Commented Nov 2, 2017 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$
    – indiscreteLog
    Commented Nov 2, 2017 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
    Commented Nov 3, 2017 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$
    – indiscreteLog
    Commented Nov 4, 2017 at 11:50

1 Answer 1

Reset to default
7
$\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).

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.