An ECC game
in [Cryptography]
|
Prev: Call for Papers: ICOMP'10 (The 2010 International Conference on Internet Computing), USA, July 2010
Next: A 3D pattern found in Prime Number sums - using the golden ratio log!
From: Rainer Urian on 20 Feb 2010 15:11 Hi, assume we are playing the following ECC-k game: A chooses a random number s from the range 0..2^k as secret key B can choose n k-bit elliptic curves and corresponding public points (ECC_i, P_i, i=1..n). The chossen elliptic curves can be arbitrary but must be cryptographically strong. (e.g. must be primary, not supersingular ,...) Then A calculates Q_i = P_i*s in ECC_i for i=1..n and sends the results Q_i to B. Now, is it possible for B to guess A's secret key with significant probability ? -- Rainer
From: Kristian Gj�steen on 20 Feb 2010 17:43
Rainer Urian <rainer(a)urian.eu> wrote: >assume we are playing the following ECC-k game: >A chooses a random number s from the range 0..2^k as secret key >B can choose n k-bit elliptic curves and corresponding public points >(ECC_i, P_i, i=1..n). The chossen elliptic curves can be arbitrary but must >be cryptographically strong. (e.g. must be primary, not supersingular ,...) >Then A calculates Q_i = P_i*s in ECC_i for i=1..n and sends the results Q_i >to B. > >Now, is it possible for B to guess A's secret key with significant >probability ? Who knows? I don't think you can reduce this to something well-studied like EC-DDH or EC-DLOG. If you place a few restrictions on the choice of the curves, it's not known how to embed a trapdoor in an elliptic curve (it seems possible to embed a practical trapdoor in some very special elliptic curves that on their own remain cryptographically strong). One might try techniques similar to the attack on textbook RSA where someone encrypts the same message to multiple recipients. The idea would be to choose a number of curves that all lift to the same curve over the rationals, then use the chinese remainder theorem to lift the points below to the rational curve, then send them down to curves where the discrete logarithm is easy, to recover the logarithm of the entire point. The problem is that the lifted point will have too many digits to be calculatable. So it wouldn't work. That's one minute of thinking. Someone else might come up with something better in 30s. -- Kristian Gj�steen |