Re: Multiplicative Homomorphic Mapping

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

> "Gerry Myerson" <gerry@xxxxxxxxxxxxxxxxxxxxxxxxx> wrote in message
> news:gerry-96BA5B.09182722082005@xxxxxxxxxxxxxxxxxxxxx
> >
> > 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.

I think you're obscuring the essentials by talking about extension
fields. Suppose p and q are biggish primes and d divides both p - 1
and q - 1 so that both Z / pZ and Z / qZ have subgroups of order d.
These subgroups are both cyclic, hence isomorphic: you want to find
an isomorphism.

To carry out the procedure above, first you have to find a generator
for each of the subgroups. This is just as hard as finding primitive
roots mod p and mod q to begin with.

But then you want to know which element in the subgroup of Z / qZ
corresponds to some given element of the subgroup of Z / pZ. Well,
isn't this exactly the discrete logarithm problem?

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?

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

Relevant Pages

  • Re: Beginers Abstract Algebra - Three Questions
    ... > Deduce that at least one prime factor of k must be of the form ... to work for primes of the form 4k + 3. ... >>then exactly half of H is odd permutations and half of H is even. ... If you don't know that much about groups & subgroups, ...
    (sci.math)
  • Group of order 4
    ... Let G be a group and denote with Lthe set of his subgroups. ...
    (sci.math)