Two of the major areas of developments within cybersecurity will be the usage of homomorphic encryption, and in the usage of Shamir secret sharing. With homomorphic encryption, we can encrypt values, and then operate on them with arithmetic functions (such as add, subtract and multiply), and with Shamir secret sharing, we can split secrets into shares, and then distributed them over networks. These approaches will take privacy to new levels. So let’s look at the Damgård-Jurik method [1].
Homomorphic Encryption with Damgard-Jurik |
Theory
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} \)
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.
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.
Code
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
References
[1] Damgård, I., Jurik, M., & Nielsen, J. B. (2010). A generalization of Paillier’s public-key system with applications to electronic voting. International Journal of Information Security, 9(6), 371–385.