Talk:Paillier cryptosystem

From Wikipedia, the free encyclopedia

[edit] Article Accuracy

I think there may be an error in the description of the Encryption algorithm. Step 2 says r\in \mathbb Z^{*}_{n^{2}} , but page 7 of the original paper says "select a random r < n", so shouldn't it be r\in \mathbb Z^{*}_{n} -Mike

Not sure, whether it is an error or an attempt to make the description easier to understand. What is really neccessary is that rn is a random element of the subgroup of order \varphi(n) of \mathbb Z^{*}_{n^{2}}. This can either be achieved by selecting a random element r\in\mathbb Z^{*}_{n^{2}} or by selecting 0 < r < n such that gcd(r,n) = 1. That the later is possible follows from (r+kn)^n\equiv r^n\pmod{n^2}. 85.0.108.196 09:04, 24 April 2007 (UTC)

[edit] Security

Heh folks! What's its actual status? Have any breaks been found? What's its likely future? Inquiring minds want to know! ww 16:38, 12 Jun 2004 (UTC)

here here! 69.203.127.36 05:51, 6 December 2005 (UTC)
Paillier's security is based on the same assumptions as RSA. JuanXonValdez 22:07, 13 December 2005 (UTC)
No, the security is not based on the same assumptions. Both are based on the difficulty of integer factorization, yes. However, RSA is also based on the RSA problem, whereas Paillier is also based on something else called the higher-order residuosity problem (as opposed to quadratic residuosity problem). Lowellian 08:26, 14 January 2006 (UTC)
In the Paillier system we're dealing with the Composite Residuosity problem (CR) and the intractability of distinguishing n-th residues mod n^2, the Decisional Composite Residuosity Assumption, (DCRA). As the paper says, CR is the problem of "deciding n-th residuosity, i.e. distingishing n-th residues from non n-th residues." In this case z is an n-th residue mod n^2 if there is a y such that z = y^n mod n^2 . By the way... the wikipedia description of the scheme is vastly different from how it was defined in the original paper. It's going to have to get corrected. Offsite 16 February 2006

I want to try this deterministic variant of Paillier system.

Original definition E(m) = g^m.r^n mod (n^2) What happens when we set r=1?

We are assuming that g != 1 mod n .. thus the order of g > n

Is this variant secure?

It is not semantically secure, because a plaintext always encrypts to the same ciphertext (given the same key). The main property of probabilistic encryption (e.g. Paillier's) is that given the same plaintext and the same key, it will encrypt randomly to one of potentially a bajillion ciphertexts (excuse the made-up number). Though the original Paillier system is IND-CPA secure, it is still not IND-CCA2 secure. Check out the notion of ciphertext indistinguishability. Offsite 21:15, 20 March 2006 (UTC)

[edit] Implementation

Is there somewhere a commercial or open-source implementation of this algorithm ? The references give all the technical background one would want on this subject, but no real-life products are listed. Is there any ? --Iv 12:01, 24 April 2007 (UTC)