Removing 1 modular exponentiation

Mike Perry mikepery at
Mon Feb 19 23:07:47 UTC 2007

Thus spake James Muir (jamuir at

> Mike Perry wrote:
> >Thus spake Watson Ladd (watsonbladd at
> >Well, one immediate problem is that b/k has to be an integer.. So b=rk
> >for some random r and b is thus not completely random.. To clarify the
> >effects of this, you should rewrite your protocol as follows from
> >Round 2 on:
> that's not really a problem.  all computations are done in the group 
> ZZ_p. 1/k really means the inverse of k modulo the order of g in ZZ_p. 
> So b/k does not have to be an integer.

My abstract algebra is a bit rusty, but isn't finding this value as
hard as the DLP?

Problem is: (g^X)^k = g for some given k. Find X equivalent to 1/k.

Rewrite as (g^k)^X = g

Seems like you need to take the Discrete Log of both sides to get your
X=1/k value. This is hard.

Perhaps you are thinking that g^(b/k)=g^b*g^(1/k).  But it doesn't, it
is (g^b)^(1/k).

If I'm wrong, please enlighten.

Mike Perry
Mad Computer Scientist evil labs

More information about the tor-talk mailing list