Re: Multiplicative Homomorphic Mapping


"Gerry Myerson" <gerry@xxxxxxxxxxxxxxxxxxxxxxxxx> wrote in message
news:gerry-96BA5B.09182722082005@xxxxxxxxxxxxxxxxxxxxx
> In article <ILL7Dq.E4s@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
> "Aldar C-F. Chan" <aldar@xxxxxxxxxxxxxxxx> wrote:
>
> That depends on what "have" means, and on what "implement" means.

What I really meant "implement" is a poly-time algorithm to compute
the map.

>
> If you "have" a generator x for S_1 and a generator y for S_2
> then you can "implement" your isomorphism by mapping x^n to y^n
> for all n.

That's what I have in mind regarding the existence of such a mapping.

>
> To see how tricky this might be in practice, the following example,
> while not directly relevant, might be instructive. Let p be a whopping
> big prime. Then the multiplicative group of Z / pZ and the additive
> group of Z / (p - 1) Z are isomorphic, but implementing this isomorphism
> is thought to be computationally infeasible, owing to the difficulty
> of finding a generator for the 1st group.
>

I have thought of this case. This is not a good example because such
a mapping could be used to solve the the discrete logarithm problem.

What I am considering is the following:
- S_1 in K/F_p (p some large prime) is generated by the q-th root
of unity in K/F_p and
- S_2 is a multiplicative subgroup of order q in Z_n* (where n=p'q'
and q| (p'-1)(q'-1), p', q' are large primes).

Take a random generator \alpha from S_1 and \beta from S_2, map
S_1 to S_2 and vice-versa as what you said, i.e.
\alpha^x <---> \beta^x. In this case, it appears that the discrete
logarithm
problem is not touched and might be possible to have a poly-time
algorithm to implement.


.

Quantcast