The Paillier cryptosystem supports homomorphic encryption, where two encrypted values can be subtracted and the decryption of the result gives the result. In this case we will use 1,024 bit prime numbers for \(p\) and \(q\) and thus produce a modulus with 2,048 bits (\(n=pq\)).
Paillier Subtraction with Kryptology |
Background
First we select two large prime numbers (\(p\) and \(q\)) and compute:
\(n=pq\)
\(\varphi=(p-1)(q-1)\)
\( \lambda =\operatorname {lcm} {\varphi} \)
and where lcm is the least common multiple. We then select random integer \(g\) for:
\( \displaystyle g \in \mathbb {Z} _{n^{2}}^{*} \)
We must make sure that \(n\) divides the order of \(g\) by checking the following:
\( \mu =(L(g^{\lambda }{\bmod {n}}^{2}))^{-1}{\bmod {n}}\)
and where \(L\) is defined as \(L(x)=\frac {x-1}{n}\). The public key is \((n ,g)\) and the private key is \((\lambda ,\mu )\).
To encrypt a message (\(M\)), we select a random \(r\) value and compute the ciphertext of:
\(c=g^{m}\cdot r^{n} \pmod {n^{2}}\)
and then to decrypt:
\(m=L(c^{\lambda }{\bmod n}^{2})\cdot \mu {\pmod n} \)
Adding and scalar multiply
If we take two ciphers (\(C_1\) and \(C_2\)), we get:
\(C_1 = g^{m_1}\cdot r_1^{n} \pmod {n^{2}} \)
\(C_2 = g^{m_2}\cdot r_2^{n} \pmod {n^{2}} \)
If we now multiply them we get:
\(C_1 \cdot C_2 = g^{m_1}\cdot r_1^{n} \cdot g^{m_2}\cdot r_2^{n} \pmod {n^{2}}\)
\(C_1 \cdot C_2 = g^{m_1+m_2}\cdot r_1^{n} \cdot r_2^{n} \pmod {n^{2}}\)
And we adding two values requires a multiplication of the ciphers.
Subtract
If we take two ciphers (\(C_1\) and \(C_2\)), we get:
\(C_1 = g^{m_1}\cdot r_1^{n} \pmod {n^{2}} \)
\(C_2 = g^{m_2}\cdot r_2^{n} \pmod {n^{2}} \)
If we now divide them we get:
\(\frac{C_1} {C_2} = \frac{ g^{m_1}\cdot r_1^{n}}{g^{m_2}\cdot r_2^{n}} \pmod {n^{2}} \)
\(\frac{C_1} {C_2} = g^{m_1-m_2} \frac{r_1^{n}}{r_2^{n}} \pmod {n^{2}} \)
And thus a subtraction is equivalent to a divide operation. For this we perform a modular divide operation.
inv_cipher2, _ := crypto.Inv(cipher2, pub.N2)
and which is:
\(C_2^{-1} = \textrm{InverseMod}(C_2,n^2)\)
What we also need to do, is perform this operation when the result is greater than a given threshold:
\(m = m - n\)
Coding
The coding is:
from damgard_jurik import keygen import sys val_1, val_2 = 42, 12 n_b=64 if (len(sys.argv)>1): val_1=int(sys.argv[1]) if (len(sys.argv)>2): val_2=int(sys.argv[2]) if (len(sys.argv)>3): n_b=int(sys.argv[3]) public_key, private_key_ring = keygen( n_bits=n_b, s=1, threshold=3, n_shares=3 ) print(f"Using Damgard-Jurik method with {n_b}-bit key, and a threshold of three and three shares\n") print(f"Public key. n={public_key.n}, s={public_key.s}, m={public_key.m}, threshold={public_key.threshold}, delta={public_key.delta}") c_1, c_2 = public_key.encrypt(val_1), public_key.encrypt(val_2) c_add = c_1 + c_2 res1 = private_key_ring.decrypt(c_add) c_sub = c_1 - c_2 res2 = private_key_ring.decrypt(c_sub) c_mult= c_1 * val_2 res3 = private_key_ring.decrypt(c_mult) print(f"\nval_1: {val_1}") print(f"val_2: {val_2}") print(f"\nc_1: {c_1.value}") print(f"c_2: {c_2.value}") print(f"c_1+c_2: {c_add.value}") print(f"c_1-c_2: {c_sub.value}") print(f"c_1*c_2: {c_mult.value}") print(f"\nDecrypt (Add): {res1}") print(f"Decrypt (Subtract): {res2}") print(f"Decrypt (Multiply): {res3}")
A sample run is:
Using Damgard-Jurik method with 64-bit key, and a threshold of three and three shares Public key. n=174743826971117924232203186477859825289, s=1, m=43685956742779481051423225748488060689, threshold=3, delta=6 val_1: 9 val_2: 3 c_1: 27429320619805987848765352451564237217145248338366944942206061954884249278992 c_2: 14769913771126168413630660895236067257037103416139804498830583273184880216135 c_1+c_2: 12086035254029813325315665006256800980915988130367594983597188460984693331181 c_1-c_2: 921687804424968958981627966721274246800285129994018401822135562246021703624 c_1*c_2: 21809874053261031282086634289802837387921962314468453992976726818561314427636 Decrypt (Add): 12 Decrypt (Subtract): 6 Decrypt (Multiply): 27