search

data61 / python-paillier

A library for Partially Homomorphic Encryption in Python
Other
605 stars 134 forks source link

Possible weakness in base generation #2

Closed eu90h closed 8 years ago

eu90h commented 9 years ago

I was implementing the Paillier cryptosystem as an exercise. I happened to stumble across this implementation and gave it a read through, particularly to see the key generation code. I noticed that the generator is always g = n + 1. This seemed weak to me, so I started digging around the published literature.

I found a paper which criticizes the choice of g = n + 1 as a base. As I understand it, this choice weakens the security properties of the cryptosystem leading to a chosen cipher-text attack.

I propose that the generator g be chosen randomly from the multiplicative group Z_n^2, per the above paper. For large given n, the probably that a random element of Z_n^2 satisfies the key condition is 1 - 1/n, which clearly approaches unity as n grows unbounded.

The new base generation would require very minor modifications to the key generation process, mainly calculating lambda = lcm((p-1), (q-1)).

If your interested, I could write a patch and submit it.

hardbyte commented 9 years ago

Thanks for taking the time to raise this issue. This generator was chosen as a speed improvement, but of course it must not degrade the security.

Here is a relevant snippet from internal discussions regarding the security properties:

The Sakurai Takagi paper discusses weaknesses in the modified Paillier Scheme of Choi et al. This doesn’t apply to our case, as we use standard Paillier. g = n + 1 is a valid choice for the generator and does not degrade security (i.e. see proof of Damgard Jurik: A Generalisation, a Simplification and some Applications of Paillier’s Probabilistic Public-Key System http://www.brics.dk/RS/00/45/BRICS-RS-00-45.pdf Section 3 Definition 1).

The ability to use a different generator could be interesting however, and contributions are very welcomed.

eu90h commented 9 years ago

Thanks for the link to the paper, you are completely correct about the generators safety. I'm coming from a math background and only recently began studying cryptography, very fun but I should clearly be more careful!

Anyhow, I'm torn on writing a patch now, don't fix what ain't broke and all that. If you feel it would benefit your program, I'll happily write it. Otherwise we can close this issue.

Apologies for the false alarm and thanks again for the paper.