Prev: Linear Equivalence and Involutions
Next: The Status Quo in Sci Crypt.
From: Rainer Urian on 12 Mar 2010 00:42
Hello,
I am searching for a solution for the following problem:
Let E(p) be a non-supersingular elliptic curve over GF(p)
Let l be a prime and assume E(p) contains an l-torsion element G. (One can
assume here that l is big. )
let G' be another l-torsion element in E(p^k), i.e. (G,G') generates the
l-torsion group.
Now I want an algorithm A to calculate two points P,P' such that
P= s*G
P'= s*G'
and such that s is provable unknown to A
Remark:
Calculating P=s*G alone, such that s is unknown is easy, e.g. by hashing
into E(p).
Also, for supersingular curves, one could use a endomorphism ("distortion
map") from G to G'.
But for non-supersingular curves there is no distortion map


Thank you,
Rainer

From: Kristian Gj�steen on 12 Mar 2010 04:53
Rainer Urian <rainer(a)urian.eu> wrote:
>I am searching for a solution for the following problem:
>Let E(p) be a non-supersingular elliptic curve over GF(p)
>Let l be a prime and assume E(p) contains an l-torsion element G. (One can
>assume here that l is big. )
>let G' be another l-torsion element in E(p^k), i.e. (G,G') generates the
>l-torsion group.
>Now I want an algorithm A to calculate two points P,P' such that
>P= s*G
>P'= s*G'
>and such that s is provable unknown to A
>Remark:
>Calculating P=s*G alone, such that s is unknown is easy, e.g. by hashing
>into E(p).
>Also, for supersingular curves, one could use a endomorphism ("distortion
>map") from G to G'.
>But for non-supersingular curves there is no distortion map

This looks similar to the "knowledge-of-exponent" assumption to me.

Given two cyclic subgroups G1=<g1> and G2=<g2>, g1,g2 - generators,
it is in general difficult to find a point (x,y) in G1 x G2 that is a
multiple of (g1,g2) without computing (x,y) as a linear combination of
known multiples of (g1,g2).

Sometimes, it is possible (e.g. when G1=G2 and you know the logarithm
of g2 to the base g1, or in your case when you have distortion maps),
but I think it should be possible to come up with a generic model proof
to show that there's no generic algorithm.

Obviously, this doesn't imply that your case is difficult, but it
might be.

--
Kristian Gj�steen
 | 
Pages: 1
Prev: Linear Equivalence and Involutions
Next: The Status Quo in Sci Crypt.