safety of Pohlig-Hellman with a common modulus?

[David Wagner]

Steve Bellovin  wrote:
>Is it safe to use Pohlig-Hellman encryption with a common modulus?  
>That is, I want various parties to have their own exponents, but share 
>the same prime modulus.  In my application, a chosen plaintext attack 
>will be possible.  (I know that RSA with common modulus is not safe.)

Yes, I believe so.  The security of Pohlig-Hellman rests on the difficulty
of the discrete log problem.  Knowing the discrete log of g^y doesn't help
me learn the discrete log of g^x (assuming x,y are picked independently).
This is not like RSA, where using a common modulus allows devastating
attacks.

There is a small caveat, but it is pretty minor.  There are some
precomputation attacks one can do which depend only on the prime p; after
a long precomputation, one can compute discrete logs mod p fairly quickly.
The more people who use the same modulus, the more attractive such a
precomputation effort will be.  So the only reason (that I know of)
for using different modulii with Pohlig-Hellman is to avoid putting all
your eggs in one basket.

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com