Usenet.com

www.Usenet.com

Group Index

Sci Thread Archive from Usenet.com

<-- __Chronological__ --> <-- __Thread__ -->

Proving the hardness of a problem similar to the representation problem




I'm trying to prove that it is not possible to generate two pairs
(x,y) and (x',y') so that g1 ^ x + g2 ^ y = g1 ^ x' + g2 ^ y' (mod q).
Gq is a group of known prime order q.  g1 and g2 are elements of Gq
not equal to 1 (i.e. g1 and g2 are generators). How can I prove that
it is a difficult problem (e.g. equivalent to DL)?

Did you already see a proof of this problem, which is similar to the
representation problem? Unfortunately, it is not possible to simplify
sums of exponential expressions as it is done with products of
exponential expressions.

Do you have any idea on how to prove the hardness of this problem or
the equivalence with a well known difficult problem?

Is there a book or a report that describes a generic method to prove
that two difficult problems are equivalent?

We can define the problem as:
I) g1,g2, A1( ) --> x,y,x',y' so that  g1 ^ x + g2 ^ y = g1 ^ x' + g2
^ y' (mod q)

II) A2(g1,g2) --> x,y so that g1 ^ x + g2 ^ y = 0
It is easy to prove that:  II => DL

III) A3(g1,g2,h) --> x,y so that g1 ^ x + g2 ^ y = h
IV) A4(g) --> x,y so that g^x + g^y = 1
V)  A5(g) --> x,y,z so that y=log_g(z) and x=log_g(z+1)
III => IV => V

V) Finding the discrete log in base "g" of a random number "z" and the
discrete log in base "g" of "z+1" seems to be a difficult problem, but
I do not see how to prove it.

Thanks,

      Laurent



<-- __Chronological__ --> <-- __Thread__ -->


Usenet.com



Please check out one of the premium Usenet Newsgroup Service Providers below for access to Usenet.