Paillier cryptosystem

The Paillier cryptosystem was presented by Pascal Paillier at the Eurocrypt in 1999. This is an asymmetrical cryptosystem , the security of which is based on the fact that it is not possible to efficiently check for a composite module whether an element in a th root has modulo or not. A special feature of the Paillier cryptosystem is that two encrypted messages can be added without first decrypting the messages. ${\displaystyle n}$ ${\displaystyle (\mathbb {Z} /n^{2}\mathbb {Z} )}$ ${\displaystyle n}$ ${\displaystyle n^{2}}$

The process is often referred to as the successor to the Okamoto Uchiyama cryptosystem . It is also a special case of the Damgård-Jurik cryptosystem .

Procedure

In the following, the key generation and the algorithms for encrypting and decrypting messages are described.

Generation of the public and private key

The key pair is generated as follows:

• One generates two random prime numbers so that . In practice, n should have at least 1024, but better 1536 or 2048 binary digits . You then bet as well . ${\displaystyle p,q}$ ${\displaystyle \operatorname {ggT} (pq,(p-1)(q-1))=1}$ ${\displaystyle n=pq}$ ${\displaystyle \lambda =\operatorname {kgV} (p-1,q-1)}$
• One randomly chooses in such that the order of divides. ${\displaystyle g}$ ${\displaystyle (\mathbb {Z} /n^{2}\mathbb {Z} )^{*}}$ ${\displaystyle n}$ ${\displaystyle g}$

The public key consists of , the private key consists of . ${\displaystyle (n,g)}$ ${\displaystyle (\lambda )}$

Simplification : The key generation can also be simplified as follows:

• One chooses a security parameter and the two prime numbers randomly in , i.e. with the same bit length. ${\displaystyle k}$ ${\displaystyle p,q}$ ${\displaystyle {\left\{1||\{0,1\}^{k-1}\right\}}}$
• One defines as well . ${\displaystyle g=n+1}$ ${\displaystyle \lambda =(p-1)(q-1)}$

Encrypt messages

To encrypt a message , proceed as follows: ${\displaystyle m\in (\mathbb {Z} /n\mathbb {Z} )}$

• First you choose a random one . ${\displaystyle r\in (\mathbb {Z} /n\mathbb {Z} )^{*}}$
• The encrypted message is then given through . ${\displaystyle c=g^{m}r^{n}\mod n^{2}}$

Decrypting messages (decoding)

To decrypt, you first define the function . For a cipher text is then carried out as follows: ${\displaystyle L(x)={\frac {x-1}{n}}}$ ${\displaystyle c\in (\mathbb {Z} /n^{2}\mathbb {Z} )^{*}}$

• One sets where the logarithmic function is from above. ${\displaystyle m={\frac {L(c^{\lambda }\mod n^{2})}{L(g^{\lambda }\mod n^{2})}}\mod n}$ ${\displaystyle L()}$

In this step it should be noted that the division must be carried out modulo , i. i.e., by multiplying by the multiplicative inverse . The division in the calculation of the logarithmic function is carried out over the whole numbers. ${\displaystyle n}$ ${\displaystyle L()}$

Simplification : If you have chosen the simplified variant of key generation, the decryption results in:

• One sets , whereby the division is to be understood modulo again . ${\displaystyle m={\frac {L(c^{\lambda }\mod n^{2})}{\lambda }}\mod n}$ ${\displaystyle n}$

safety

Under the Decisional Composite Residuosity assumption, it can be shown that the method is semantically secure against selected plaintext attacks . This assumption means that it is not possible to efficiently check for a composite module whether an element in a -th root has modulo or not. ${\displaystyle n}$ ${\displaystyle (\mathbb {Z} /n^{2}\mathbb {Z} )}$ ${\displaystyle n}$ ${\displaystyle n^{2}}$

Homomorphism properties

The Paillier cryptosystem is additive- homomorphic , which means that unknown plaintexts can be added through operations on key texts :

• By multiplying two key texts , the encrypted plain texts are added: ${\displaystyle c_{1},c_{2}}$ ${\displaystyle m_{1},m_{2}}$

${\displaystyle g^{m_{1}}r_{1}^{n}\cdot g^{m_{2}}r_{2}^{n}=g^{m_{1}+m_{2}}(r_{1}r_{2})^{n}=g^{m_{1}+m_{2}}r'^{n}\mod n^{2}=m_{1}+m_{2}\mod n.\,}$.

Sometimes two special cases are of particular interest:

• By multiplying a ciphertext with an arbitrary value can for encrypted clear text is added: ${\displaystyle c}$ ${\displaystyle g^{\Delta m}}$ ${\displaystyle \Delta m}$ ${\displaystyle m}$

${\displaystyle g^{m}r^{n}\cdot g^{\Delta m}=g^{m+\Delta m}r^{n}\mod n^{2}}$

• By multiplying a key text with , i. H. the addition of the encrypted value "0", encryption can be randomized again without changing the message : ${\displaystyle c}$ ${\displaystyle \Delta r^{n}}$ ${\displaystyle m}$ ${\displaystyle m}$

${\displaystyle g^{m}r^{n}\cdot \Delta r^{n}=g^{m}(r\Delta r)^{n}=g^{m}r'^{n}\mod n^{2}}$

• By exponentiation of a key text by a natural number , the encrypted message comparable w -facht be ${\displaystyle c}$ ${\displaystyle w}$ ${\displaystyle m}$

${\displaystyle (g^{m}r^{n})^{w}=g^{wm}(r^{w})^{n}=g^{wm}r'^{n}\mod n^{2}}$.

However, there is no known possibility of multiplying the messages contained in them by means of operations on two key texts.

advantages

The homomorphic properties are u. a. exploited in connection with the following applications.

• E-voting : After all eligible voters have encrypted their votes (in the simplest case a 1 for yes , a 0 for no ) and transmitted them to the electoral authority, all key texts are multiplied; the resulting ciphertext contains the sum of the yes votes (in encrypted form). The result of the election is obtained by decoding. It is important that the party performing the first step does not need to know the secret key, which means that no individual votes can be decrypted.
• eCash
• Zero-knowledge evidence in the Universal Composability Model

disadvantage

Due to the listed homomorphic properties, however, the method is not IND-CCA safe, i. H. not safe under selected ciphertext attacks . Every encryption system that has this security would have to be non-deformable , a property that contradicts homomorphism. In the literature one also finds transformations to transform the Paillier cryptosystem into an IND-CCA-safe variant. Whether these transformations are appropriate or not depends on the particular application.

Complete example

The steps outlined above are illustrated here using a small example.

Key generation

First we choose the security parameter , then choose and . This now allows us to choose the simplified variant of key generation. With this we get: ${\displaystyle k=10}$ ${\displaystyle p=1.019}$ ${\displaystyle q=883}$

${\displaystyle n=p\cdot q=899777}$

${\displaystyle g=n+1=899778}$

${\displaystyle \lambda =(p-1)\cdot (q-1)=897876}$

The public key is given by: ${\displaystyle (n,g)=(899.777,899.778).}$

The secret key is . ${\displaystyle (\lambda )=(897.876)}$

Preliminary work

In a first step, the text to be encrypted must be translated into numbers smaller than the number . To do this, we simply replace each letter with its position in the alphabet: ${\displaystyle n}$

A=01 B=02 C=03 usw. (00 = Leerzeichen)

We are now encrypting three characters at a time, as four consecutive letters could possibly deliver too great a value.

Klartext:  P  A  I  L  L  I  E  R
Kodierung: 16 01 09 12 12 09 05 18 00

Encryption

We have three plaintexts to encrypt ( , and ), for each of which we need one. ${\displaystyle m_{1}=160109}$ ${\displaystyle m_{2}=121209}$ ${\displaystyle m_{3}=051800}$ ${\displaystyle r_{i}\in (\mathbb {Z} /n\mathbb {Z} )^{*}}$

r1 =  12312
r2 = 623543
r3 = 215688

The encryptions thus result in: ${\displaystyle c_{i}}$

ci = gmirin mod n2
c1 = 899778160109 12312899777 mod 809598649729 = 594091908920
c2 = 508000332395
c3 = 783129227180

Decryption

Since we had chosen the simplified variant for key generation, we can decrypt the messages by:

mi = L(ci ${\displaystyle \lambda }$ mod n2) /  ${\displaystyle \lambda }$ mod n

It is important here that the division is carried out. We therefore calculate the multiplicative inverse of modulo using the extended Euclidean algorithm and thus obtain . This results in the decryption to: ${\displaystyle \mod n}$ ${\displaystyle \lambda }$ ${\displaystyle n}$ ${\displaystyle \lambda ^{-1}=141522\mod n}$

m1 = L(594091908920897876 mod 809598649729) * 141522 mod 899777 = 160109
m2 = 121209
m3 = 051800

By inverting the substitution rule , these values ​​can now be translated back into letters.

credentials

1. ↑ Pascal Paillier: Public-Key Cryptosystems Based on Composite Degree Residuosity Classes (English) . In: Eurocrypt 99 , Springer Verlag, 1999, pp. 223-238. 
2. ↑ Eiichiro Fujisaki and Tatsuako Okamoto: How to Enhance the Security of Public-Key Encryption at Minimum Cost (English) . In: PKC 99 , Springer Verlag, 1999, pp. 53-68. 
3. ↑ Pascal Paillier and David Pointcheval: Efficient Public-Key Cryptosystems provably Secure Against Active Adversaries (English) . In: ASIACRYPT 99 , Springer Verlag, 1999, pp. 165-179.