Talk:Paillier cryptosystem

Cryptography: Computer science High‑importance

	This article is within the scope of WikiProject Cryptography, a collaborative effort to improve the coverage of Cryptography on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.CryptographyWikipedia:WikiProject CryptographyTemplate:WikiProject CryptographyCryptography articles
High	This article has been rated as High-importance on the importance scale.
	This article is supported by WikiProject Computer science (assessed as High-importance).

Article Accuracy

The update to encryption, where $r\in Z_{n^{2}}^{*}$ , is added due to the discussion here. This is only relevant to small "lecture-sized" keys, e.g., p=11, q=13. With large key sizes, e.g., 1024-bit, the probability of r being a multiple of p or q is negligible. Still, it is important to add this caveat especially for students new to this cryptosystem. See https://crypto.stackexchange.com/a/62378/49011. 100.36.66.167 (talk) 03:47, 17 September 2018 (UTC)[reply]

The "simpler variant" may be incorrect regarding $\lambda$ . The least common multiple form works fine (use $lcm(x,y)={\frac {x\cdot y}{gcd(x,y)}}$ ). Additionally, decryption seems to fail in the cases where p==q. 100.36.66.167 (talk) 19:11, 14 September 2018 (UTC)[reply]

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

r^{n}

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)[reply]

The description of the key generation algorithm is not correct. To see this, suppose I chose the primes $p=7$ , $q=29$ and compute $n=p*q$ . Then $p$ divides $\varphi (n)$ and there is no number $g$ such that $\gcd(g,n)=1$ and $\gcd(L(g^{\varphi (n)}\mod n^{2}),n)=1$ Imraith-Nimphais (talk) 15:00, 7 August 2009 (UTC)[reply]

That's because the pair p=7,q=29 is not an "admissible" combination. To be admissible choices for p, q, must satisfy

\gcd(n,\varphi (n))=1

. This criterion appears to have first been explicitly stated in [1]. As the authors point out, "When p,q, are large and randomly chosen, this will be satisfied, except with negligible probability." Primepq (talk) 19:28, 29 August 2009 (UTC)[reply]

I think there is an error suggestion to use $\lambda =\varphi (n)$ . This could be correct only if $n$ would be prime, but it is composite, thus proper Carmichael function must be used. — Preceding unsigned comment added by Arnisut (talk • contribs) 22:44, 24 November 2011 (UTC)[reply]

"Key generation: Choose two primes p and q such that gcd(pq,(p-1)(q-1))=1. This property is assured if the primes are of equal length."

... what about p=41, q=83? 50.224.1.242 (talk) 19:56, 12 March 2018 (UTC) ... those are unequal (bit) length. 100.36.66.167 (talk) 19:13, 14 September 2018 (UTC)[reply]

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)[reply]

Paillier's security is based on the same assumptions as RSA. JuanXonValdez 22:07, 13 December 2005 (UTC)[reply]

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)[reply]

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)[reply]

Besides not being semantically secure, it is trivially insecure since if E(m) = g^m mod n^2, then the public function L(E(m))/L(g) returns the plaintext m. You can turn the Paillier cryptosystem into a deterministic scheme with some provable security though. Basically the idea is, at the time of key-generation, set e = g*r^n mod n^2 for some secret r, and add e to the public key. Then encryption can be done E(m) = e^m mod n^2. If this is instantiated with the Damgaard-Jurik variant of Paillier, this was shown to achieve a form of security for deterministic encryption. See [2] which appeared in CRYPTO 2008 for a full description of the scheme and the security achieved. Beamishboy (talk) 21:20, 7 February 2009 (UTC)[reply]

Electronic voting

It says that this algorithm can be used in an election where a user select 1 or 0 as a vote. But what happens if the user selects 2 instead ? or 5000 for what it matters ? I seen nothing forbidding it. How can an official check this is not what happened ? --Iv (talk) 13:41, 19 March 2010 (UTC)[reply]

Interesting question. According to these lecture notes, the voter must submit zero-knowledge proofs of his/her votes. -- intgr [talk] 18:26, 19 March 2010 (UTC)[reply]

External links modified

Hello fellow Wikipedians,

I have just added archive links to one external link on Paillier cryptosystem. Please take a moment to review my edit. If necessary, add {{cbignore}} after the link to keep me from modifying it. Alternatively, you can add {{nobots|deny=InternetArchiveBot}} to keep me off the page altogether. I made the following changes:

Added archive http://web.archive.org/web/20160106172152/http://www.rsasecurity.com/rsalabs/cryptobytes/CryptoBytes_January_2002_final.pdf to http://www.rsasecurity.com/rsalabs/cryptobytes/CryptoBytes_January_2002_final.pdf

When you have finished reviewing my changes, please set the checked parameter below to true or failed to let others know (documentation at {{Sourcecheck}}).

This message was posted before February 2018. After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than regular verification using the archive tool instructions below. Editors have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the RfC before doing mass systematic removals. This message is updated dynamically through the template {{source check}} (last update: 5 June 2024).

If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
If you found an error with any archives or the URLs themselves, you can fix them with this tool.

Cheers.—^{cyberbot II}_{Talk to my owner:Online} 11:15, 28 February 2016 (UTC)[reply]

Why to write the parameter r explicitly ?

Is it really necessary to write the random number r explicitly as an argument of encryption function?

For instance, the expression

D(E(m_{1},r_{1})\cdot E(m_{2},r_{2}){\bmod {n}}^{2})=m_{1}+m_{2}{\bmod {n}}.\,

could be simplified to

D(E(m_{1})\cdot E(m_{2}){\bmod {n}}^{2})=m_{1}+m_{2}{\bmod {n}}.\,

since the description of the encryption function makes it clear that the random number r is sampled when a message will be encrypted.

Lp.vitor (talk) 20:00, 29 August 2016 (UTC)[reply]

Mixup between cipher and plain

It seems to me that there is a mixup between "plaintext" and "ciphertext" in the section "Homomorphic multiplication of plaintexts". I think that the sentence should read: "A ciphertext raised to the power of another ciphertext will decrypt to the product of the two plaintexts". Moreover I think "encrypted plaintext" is really a weird formulation anyway, it should be "ciphertext". Ho33e5 (talk) 22:07, 20 September 2016 (UTC)[reply]

Edit: my first remark is false, there is no mixup. But there is still the weird "encrypted plaintext". --Ho33e5 (talk) 10:19, 12 January 2017 (UTC)[reply]