Re: Multiplicative Homomorphic Mapping

In article <ILMEyK.Fo0@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
"Aldar C-F. Chan" <aldar@xxxxxxxxxxxxxxxx> wrote:

> "Gerry Myerson" <gerry@xxxxxxxxxxxxxxxxxxxxxxxxx> wrote in message
> news:gerry-E32158.14204822082005@xxxxxxxxxxxxxxxxxxxxx
> > g generates G, h generates H, a is in G, so a = g^x for some (very
> > hard to calculate) x, you want to know h^x; I don't see how you're
> > going to get it without getting x first, or anyway doing as much
> > work as it would take to get x. Do you have any reason to think
> > otherwise?
>
> I am not sure if I understand the difficulty of this problem well enough.
> Given g^x for unknown x, I don't see why finding h^x has to be as
> difficult as finding x. At the very least, given an algorithm doing so,
> it appears that the DL problem cannot be solved.

I agree that it is not clear that if you can find h^x from g^x
then you can find x from g^x. I would be very surprised if finding
h^x from g^x were any easier than finding x from g^x, but I have
often been surprised in the past & with any luck will be surprised
many times in the future.

Consdier the following setup: p a humungous given prime, g a given
primitive root mod p, a a given non-zero element of Z / pZ, so
a = g^x for some unknown x; H the group of solutions of t^(p-1) = 1
in the complex numbers, with generator z = e^(2 pi i / (p - 1)).
Now if you had a good way to implement the isomorphism f from (Z / pZ)*
to H, you could apply it to a to get f(a) = e^(2 pi i b / (p - 1)),
and bingo! - you've solved the discrete logarithm problem, x = b.

All this proves is that there is a setting in which implementing
the isomorphism is the same as solving the discrete logarithm.
It doesn't prove anything about any other setting, it just
reinforces my prejudices about the situation.

> I am not sure if the following could be possible counterexample:
>
> Suppose G is a supersingular elliptic over F_p with a non-degenerate
> pairing to F_p^l, let P in G be a subgroup of order q (call it S_1), then
> the pairing e(P,P) is a generator of a subgroup in F_p^l (call it S_2)
> of the same order.
>
> Given xP in S_1, we can find e(P,P)^x = e(xP,P).
>
> This is a very special instance and what I want to find is other more
> general instances.

I don't know enough about pairings on elliptic curves to appreciate
this example. It doesn't surprise me that if your groups come with
lots of extra structure then you can implement your isomorphism.

--
Gerry Myerson (gerry@xxxxxxxxxxxxxxx) (i -> u for email)
.