Paillier scheme Sample Clauses

Paillier scheme. ‌ The Paillier cryptosystem [32] is a probabilistic asymmetric algorithm for public- key cryptography first proposed by Xxxxxx Xxxxxxxx in 1999 in his paper “Public- Key Cryptosystems Based on Composite Degree Residuosity Classes”. This paper offers a trapdoor mechanism from the family of trapdoors in the discrete logarithm technique based on composite residuosity classes. This scheme has an additive homomorphic property, i.e., allows adding two ci- phertexts without corrupting the result. The computation behaves just as if the corresponding plaintexts are added (without the need of decryption). However, a drawback of the Paillier cryptosystem is its efficiency which is a common issue for any scheme based on homomorphic encryption. Several optimi- sation propositions has already been made. For instance, Xxxxxxxx himself proposed a variant, namely Scheme 3, of the original proposal, namely Scheme 1, which uses abound 𝛼 on exponentiation power size to speed up the computation of the encryp- tion in particular. Another improving method can be the use of pre-computation of some values, for instance, the exponentiation of either the message 𝑔𝑚 or the noise 𝑟𝑛 as suggested in the article [17]. The use-cases of the Paillier cryptosystem are, for instance, in electronic voting [2], machine learning on encrypted data [6], and can be also used in other algorithms that demand high confidentiality even during processing between mutually authen- ticated parties because of other features such as the self-binding ability (ability to change one ciphertext into another without changing the content of the decryption) [33].

Paillier scheme. 1‌ In Scheme 1 are the public key 𝑝𝑘 and secret key 𝑠𝑘 generated by the following algorithm. First are chosen two large prime numbers 𝑝 and 𝑞 at random such that they are independent of each other and that GCD(𝑝𝑞, (𝑝 − 1)(𝑞 − 1)) = 1 (this property is assured if both primes are of equal length). Than is computed the parameter 𝑛 = 𝑝𝑞 and parameter 𝜆 as LCM(𝑝 − 1, 𝑞 − 1) followed by the generation of parameter 𝑔 ∈ Z𝑛* 2 at random. At this point must be ensured that 𝑛 divides the 𝑔 by checking the existence of modular multiplicative inverse 𝜇 as 𝑏 𝜇 = (𝐿(𝑔𝜆 mod 𝑛2))−1 mod 𝑛, (2.5) 𝑛 where function 𝐿(𝑥) = 𝑥−1 where the notation 𝑎 denotes the quotient of 𝑎 divided by 𝑏. The public key 𝑝𝑘 is than the ordered set of parameters 𝑛 and 𝑔 and the secret key 𝑠𝑘 is the ordered set of parameters 𝜆 and 𝜇. The encryption of a message 𝑚 is computed as 𝑐 = 𝑔𝑚 · 𝑟𝑛 mod 𝑛2, (2.6) where 𝑚 must be in range ⟨0, 𝑛) and parameter 𝑟 is a generated number from interval (0, 𝑛) at random. The decryption process is essentially exponentiation modulo 𝑛2. The ciphertext is decrypted as 𝑚 = 𝐿(𝑐𝜆 mod 𝑛2) · 𝜇 mod 𝑛. (2.7)