Collisions in Discrete Logarithms

[Amitabh Saxena]

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

[David Wagner]

Post by Amitabh Saxena
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.

Start by assuming that 1+1 = 3, then you'll have no problem proving
it.

Seriously, I don't think you're going to find a proof of this claim,
because I don't think the claim is true. If g,h are generated at random
(so that the d.log of h to base g is unknown, and vice versa), then
finding collisions is as hard as solving the discrete log problem.
Suppose h = g^a. If you can find x,y,x',y' such that g^x h^y = g^x' h^y',
then a = (x - x')/(y' - y) (mod |G|), and you've found the d.log of h.

[Kristian GjXsteen]

Post by Amitabh Saxena
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).

It will have many solutions, since both g and h are generators.

Post by Amitabh Saxena
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).

If the group order has known, small factors, then it is easy. (Do
it in the small subgroups, then combine the results using Chinese
remainder theorem.)

Otherwise, I don't think you can find such a proof, since it looks
as if finding two such numbers for an arbitrary m is equivalent to
finding discrete logarithms. (Find x and y for m=g^z, and solve the
resulting linear equation to find log_g h.)

A search for the Chaum-van Heijst-Pfitzmann hash function may turn
up more information.

--
Kristian Gj<F8>steen

[Scott "Poncho" Fluhrer]

Post by Amitabh Saxena
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).

Actually, if the group order is known, it is exactly as hard. Here is the
reduction:

- Suppose you have an Oracle that, given a triplet (g, h, m) with random
generators g, h, and a group element m, produces with nontrivial probability
a pair (x, y) s.t. g^x h^h = m.
- Then, given a pair (a, b) with 'a' a generator, and b a group element, you
select a random r, s relatively prime to the group order L, and then submit
to the Oracle the triplet (a^r, a^s, b). a^r and a^s can be seen to be
random generators, and so the Oracle outputs with nontrivial probability a
pair (x, y). Then, we know that a^(rx+sy) = m, solving the DLP.

Post by Amitabh Saxena
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?

Nope (same argument)

Post by Amitabh Saxena
Thanks in advance
Amitabh