Amitabh Saxena

2005-10-01 15:26:36 UTC

Can anyone give me some references for this problem?

Given a group G where computing Discrete Logarithms is hard. Let g and

h be two generators and m be any given element of G. Our goal is to try

to find two numbers (x, y) such that g^x.h^y=m. It is very likely that

this will have more than one solution for (x, y).

I want a proof that finding this type of collisions is considerably

easier than computing discrete logarithms.. (I need some sort of

metrics for the hardness of this problem in relation to the DLP).

As an extension of this question, what if we consider different

properties for G, say suppose DLP is hard but the DDHP is easy, in this

case is finding collisions any easier?

Thanks in advance

Amitabh

Given a group G where computing Discrete Logarithms is hard. Let g and

h be two generators and m be any given element of G. Our goal is to try

to find two numbers (x, y) such that g^x.h^y=m. It is very likely that

this will have more than one solution for (x, y).

I want a proof that finding this type of collisions is considerably

easier than computing discrete logarithms.. (I need some sort of

metrics for the hardness of this problem in relation to the DLP).

As an extension of this question, what if we consider different

properties for G, say suppose DLP is hard but the DDHP is easy, in this

case is finding collisions any easier?

Thanks in advance

Amitabh