Paillier Shines a Light On a New World of Computing

Paillier Shines a Light On a New World of Computing

We need to move to an information world where every single data element is be encrypted at every point, no matter if it is at rest, in motion, or in process. The in-process part is our greatest challenge, and only homomorphic encryption will solve this problem. In the future our data processors may operate on encrypted values.

The Paillier cryptosystem is one method which supports partially homomorphic encryption, where two encrypted values can be added together, and the decryption of the result gives the addition. We thus use and public key to encrypt the values, and a private key to decrypt the result. So, rather than try and lay out the maths on the page, here is the screen shot of the method from the Wikipedia:

So, I’ll show you how we decode these scribbles, and code it with some simple code, and reveal the magic of homomorphic encryption. If you just want to watch, here’s a demo:

In this case we start with two prime numbers (p and q), and then compute n. Next we get the Lowest Common Multiplier for (p-1) and (q-1), and then we get a random number g:

def gcd(a,b):
    while b > 0:
        a, b = b, a % b
    return a
    
def lcm(a, b):
    return a * b / gcd(a, b)

n = p*q

gLambda = lcm(p-1,q-1)

g = randint(0,100)

The next two steps involve calculating the value of the L function, and then gMu, which is the inverse of l mod n (I will show the inverse function later in the article):

l = (pow(g, gLambda, n*n)-1)//n
gMu = inverse_of(l, n)

The public key is then (n,g) and the private key is (gLamda,gMu).

cipher is then computed from the message (the function pow(a,b,n) raises a to the power of b, and then takes a mod of n):

k1 = pow(g, m, n*n)
k2 = pow(r, n, n*n)

cipher = (k1 * k2) % (n*n)

And is decrypted with:

l = (pow(cipher, gLambda, n*n)-1) // n

mess= (l * gMu) % n

A sample run with p=17, q=19, and m=10 is:

p= 17 	q= 19
g= 45 	r= 59
================
Mu:		66 	gLambda:	144
================
Public key (n,g):		323 45
Private key (lambda,mu):	144 66
================
Message:	10
Cipher:		336
Decrypted:	10

With Pallier we should be able to take values and then encrypt with the public key and then add them together:

m1=2
k3 = pow(g, m1, n*n)
cipher2 = (k3 * k2) % (n*n)
ciphertotal = (cipher* cipher2) % (n*n)
l = (pow(ciphertotal, gLambda, n*n)-1) // n
mess2= (l * gMu) % n
print "Result:\t\t",mess2

and when we run we get:

p= 17 	q= 19
g= 86 	r= 91
================
Mu:		40 	gLambda:	144
================
Public key (n,g):		323 86
Private key (lambda,mu):	144 40
================
Message:	10
Cipher:		95297
Decrypted:	10
================
Now we will add a ciphered value of 2 to the encrypted value
Result:	12

and so it has computed the right value.

Coding

Here is the final Python coding [here]:

We need to make sure that g only uses Z∗n². For p=41 and q=43, we get n=1763 [n²=3108169]. The valid g values are thus [here]:

Value is:	3108169
Multiplicative group for Zn up to 100 is:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 42 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 83 84 85 87 88 89 90 91 92 93 94 95 96 97 98 99 100 
The number of values is:  96

Homomorphic encryption and JavaScript

So here is an example of implementing the Paillier method with JavaScript:

Conclusions

Paillier is partially homomorphic, where we can add encrypted values, but we cannot use the full range of maths functions. For that we need full homomorphic encryption, and when we manage to get this to work at scale, we will have a new computing model in place, where every single data element will be encrypted, no matter if it is at rest, in motion, or in process. The in-process part is our greatest challenge, and only homomorphic encryption will solve this problem.