ECC's vulnerability to quantum computing

[numa...@my-deja.com]

I've been reading as much as i could lately (and even understanding a
very small portion) regarding elliptic curve cryptography. However, I
have been unable to find any information regarding whether or not
advancements in quantum computing (which will necessarily debilitate
factoring based encryption ala RSA via Shor's algorithm), will have any
effect on ECC.

Bruce Schneier's Nov.1999 Crypto-Gram states that ECC's are based on
discrete logarithms, yet he mentions that most modern factoring
algorithms are nearly similar to discrete logarithms. Does this hold
true for reversible quantum algorithms?

Intuitively, I would assume that ECC does not hold up either, but it
seems that because of its relative strength at the same key size to RSA,
maybe if it doesn't, it would still last longer at least, although at
that point it might be like putting the milk back in the bottle. Or is
there some fundamental difference that prevents a quantum algorithm from
working in the group of elliptic curves?

I'm especially curious because I just turned in a paper to my Physical
Limits of Computing course regarding this, but had to end it with an "I
don't know..."

Slightly confused and grateful for help,
Jordan Wiens
http://jordan.wiens.com/

Sent via Deja.com http://www.deja.com/
Before you buy.

[Mike Rosing]

numa...@my-deja.com wrote:
>
> I've been reading as much as i could lately (and even understanding a
> very small portion) regarding elliptic curve cryptography. However, I
> have been unable to find any information regarding whether or not
> advancements in quantum computing (which will necessarily debilitate
> factoring based encryption ala RSA via Shor's algorithm), will have any
> effect on ECC.
>
> Bruce Schneier's Nov.1999 Crypto-Gram states that ECC's are based on
> discrete logarithms, yet he mentions that most modern factoring
> algorithms are nearly similar to discrete logarithms. Does this hold
> true for reversible quantum algorithms?

It's a discrete log problem, but the groups are different. The main
difference is that ECC requires a full exponential algorithm and IF
can gain a sub-exponential speed up. All that's for "regular"
computers.

>
> Intuitively, I would assume that ECC does not hold up either, but it
> seems that because of its relative strength at the same key size to RSA,
> maybe if it doesn't, it would still last longer at least, although at
> that point it might be like putting the milk back in the bottle. Or is
> there some fundamental difference that prevents a quantum algorithm from
> working in the group of elliptic curves?

Your intuition is correct. ECC's are polytime solvable on a quantum
computer. There was a talk at the ECC '99 conference about this, but I
don't see it posted on their web page (http://cacr.math.uwaterloo.ca/)

> I'm especially curious because I just turned in a paper to my Physical
> Limits of Computing course regarding this, but had to end it with an "I
> don't know..."

Best thing to do! The basic algorithm requires a whole bunch of
guesses,
so on a QC you get to do all the guessing at once. Odds are good after
a several guessing sessions the QC will give the correct answer.

I think it'd be fun to build a QC. But I need some mighty expensive
toys first :-)

Patience, persistence, truth,
Dr. mike

[Eric Hambuch]

Mike Rosing wrote:
>
>
> Best thing to do! The basic algorithm requires a whole bunch of
> guesses,
> so on a QC you get to do all the guessing at once. Odds are good after
> a several guessing sessions the QC will give the correct answer.
>
> I think it'd be fun to build a QC. But I need some mighty expensive
> toys first :-)

BTW: There is a good quantum computer simulator on
http://tph.tuwien.ac.at/~oemer/qc
It contains also Shors factoring algorithm!

Eric

[Diet NSA]

In article <8e6c94$fhq$1...@nnrp1.deja.com>, numa...@my-deja.com
wrote:

>
>Bruce Schneier's Nov.1999 Crypto-Gram states that ECC's are
based on
>discrete logarithms, yet he mentions that most modern factoring
>algorithms are nearly similar to discrete logarithms. Does this
hold
>true for reversible quantum algorithms?

I'm not sure what you mean specifically by stating that "most

modern factoring algorithms are nearly similar to discrete

logarithms". Along with his factorization result, Peter Shor
demonstrated that discrete logs can be solved in random quantum
polynomial time.

>
>Intuitively, I would assume that ECC does not hold up either,
but it
>seems that because of its relative strength at the same key size
to RSA,
>maybe if it doesn't, it would still last longer at least,
although at
>that point it might be like putting the milk back in the bottle.

Your intuition is correct. Also, IIRC, in the original Shor
paper solving discrete logs is not accomplished quite as
efficiently as factoring. You should read this abstract [which is
only one paragraph long] which mentions the authors' contention
that the discrete logarithm problem can be done efficiently over
any group including Galois field & elliptic curves :

http://theory.stanford.edu/~dabo/abstracts/quantum.html

" V hfdt afogx nfvw ufo axb (o)(o) " - Gtnjv
----------------------------------------------------
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!