-Homomorphic encryption (HE) is one of the efficient ways that allow many companies to store their data in an encrypted form into the Cloud and then the latter can be analyzed and worked with as if it were still in its initial form. In this paper we consider two types of homomorphic encryption (HE) schemes: the additive and the multiplicative ones. But we will be focusing on the additive one in order to calculate on the cipher-texts and get the average while decrypting the result. Therefore we will show the theoretical part of the additive homomorphic Paillier's cryptosystem which is used in order to encrypt and decrypt the messages needed, but what can be more interesting is showing in details the application part of it which is realized by a numerical example applied on Sagemath.
additive
Cloud computing is a data storing technique that gives opportunities for out-sourcing of storage and computation. It offers flexibility and cost saving, but the main disadvantage that faces many companies to use the Cloud computing in their work is the security concept. The first solution proposed was to encrypt the sensible data before storing it into the Cloud, but if ever we want to apply operations on the latter without decrypting it and without having any information about the initial data, we need to use what's called homomorphic encryption (HE). The homomorphic encryption (HE) procedure is simple: the user stores its encrypted data into the cloud and sends encrypted queries over it, the latter must be able to send back to user an answer which is in an encrypted form and while decrypting the result, the user obtains what he wants. In addition a homomorphic encryption (HE) scheme could be either additive such as Paillier’s [1] and Goldwassermicali’s [2] cryptosystems or multiplicative such as RSA [3] and EL Gamal [4] crypto-systems. This depends on what the user wants as operation to be done on his plain-texts after applying the decryption function. After all these work, in 2009 Craig Gentry had the idea of creating a new cryptosystem known as Fully homomorphic encryption scheme (FHE) [5] which can handle addition and multiplication operations at the same time, but such scheme was proved unfeasible in practice due to a massive overhead in computation and memory cost. However, the idea of this article comes from the murex’s purpose, which is to calculate a list of KPI’s such as calculating the average salary for the 10% higher salary and the average monthly earnings... After studying the elements of this list, we found that the operations needed by the latter are the addition operation and the dividing by a constant operation and then we found a new simple technique to calculate the average of given plain-texts by only using their appropriate cipher-texts.
This paper is the result of a prolonged study on Paillier’s cryptosystem and our purpose of the latter is to facilitate and to make clearer the mathematical ideas and theorems used in this cryptosystem. All this is done by giving details and proofs on every step taken, as well by giving numerical examples. So that a reader, from any field, can understand not only the Paillier’s cryptosystem but also can see direct applications on it.
The rest of this paper is decomposed as follows: in section II we define the notion of homomorphic encryption (HE) as well as its properties. In section III, we present in details Paillier’s cryptosystem which is an example of a homomorphic encryption (HE) scheme and we show, in section IV, how to apply operations on it. In section V, we give a numerical example concerning the previous section. And finally we conclude this paper in section VI by giving a conclusion and an idea about future work.
An asymmetric scheme is based on three functions:
KeyGen( ):generates two different keys, a public one noted pk and a secret one noted sk.
Encrypt(pk, mi ) : is a mathematical function that is able to transform a plain-text mi into a cipher-text ci using the public key pk.
Decrypt(sk, ci ): is a mathematical function that uses the secret key sk in order to obtain the plain-text mi from the cipher-text ci.
An asymmetric homomorphic encryption scheme, schematized in the Fig. 1, is realized by following these steps:
As a first step the client must encrypt his messages mi using Encrypt(pk, mi) function, and then he sends the resu lts to be stored into the Cloud. The next step could be that the client sends some queries f( ) to the Cloud that must be capable to compute an encryption of f(mi ) noted by Encrypt(pk,f(mi )) and we mention here that f {+, ×}. Then the Cloud returns this result to the client who will compute Decrypt(sk,Encrypt(pk,f(mi))) and obtains f(mi).
All this process, schematized in the Fig. 1, is done without having to decrypt the cipher-texts stored into the Cloud and without having any information on the initial data.
There are two types of homomorphic encryption: • •
An encryption scheme is supposed to be additive homomorphic if it verifies the following:
g(Encrypt(pk, mi))=Encrypt(pk, ∑ni=1 mi).
An encryption scheme is supposed to be multiplicative homomorphic if it verifies the following: g(Encrypt(pk, mi))=Encrypt(pk, ∏ mi) . n i=1
III. PAILLIER’S CRYPTOSYSTEM [1]
Paillier’s cryptosystem is an example of additive homomorphic encryption scheme invented by Pascal Paillier in 1999. We give in this section an explanation of the Paillier’s cryptosystem construction and its properties.
Let n be the multiplication of two chosen prime numbers p and q and let g be an element of Zn*2 . But in the rest of this article we will consider that g is equal to n+1 as Damgard, Jurik and Nielsen has chosen it in 2010 in order to make the choice of g the simplest possible [7].
The public key is given by pk=(n,g) and the secret one is given by sk=(p,q).
The key generation algorithm using Sagemath is the following: def keygen(KeySize): p=random_prime(2**( KeySize //2),lbound=2**( KeySize //2-1),proof=True) q=random_prime(2**( KeySize //2),lbound=2**( KeySize //2-1),proof=True) n=p*q g=n+1 lmd=(p-1)*(q-1) mu=(lmd**(-1))%n return p,q,n,g,lmd,mu
encryption function:
Zn one can use the following c=Encrypt(pk, m)=gmrn mod n2, * where r is a random element from Zn.
This can be represented on Sagemath as following: def encrypt(m,n,g): r=random_prime(n,proof=True) return ((g**m)*(r**n))% n**2 The decryption function is given by:
Decrypt(sk, c)=
L(cλ mod n2) L(gλ mod n2) mod n Where L(u)= u–1 and the Carmichael’s function λ is equal to n lcm(p–1,q–1).
On Sagemath this function could be represented as following: def decrypt(c,lmd,mu,n): return ((((c**lmd)%(n**2)-1)/n)*mu)%n
Remark: The decryption function gives back the plain-text m because: cλ mod n2 =(gmrn)λ mod n2 =gmλ rnλ mod n2 =gmλ mod n2 =(1+n)mλ mod n2 = ∑i=m0λCi mλ nimod n2 =(C0mλ .1+C1mλ .n+ C2mλ .n2+
n2( ∑im=3λ Cimλ ni-2))mod n2
=(1+nmλ) mod n2
(
The second part of the decryption function which is = (L(g mod n2))–1, is calculated in the key generation algorithm and so that of λ in order to not being obliged to repeat the same calculation each time we are using the Decryption algorithm and therefore we are optimizing the calculation time of the latter. is calculated as follows: gλ mod n2=(1+n)λ mod n2
=(1+nλ) mod n2 L(gλ mod n2)= 1+nλ–1 mod n
n = λ mod n So = λ–1mod n And then, Decrypt(sk, c)=
L(cλ mod n2) L(gλ mod n2) 1+nmλ–1 n λ mod n = mod n=m mod n
Before passing to the next section, we would like to explain a little bit about the equalities we have considered while calulating cλ mod n2.
•
To pass from (
Zn*2 {wwnλλ==11 mmoodd nn2
Zn*2 and 0<r<n,
Zn* which is equivalent • • • • • • • • and therefore while applying Carmichael‘s theorem one can get rnλ=1 mod n2.
To pass from (2) to (
n (x+y)n= ∑ Cnk xn-kyk
k=0 Where the n choose k combinations formula is equal to:
Ckn =
n!
k!(n-k)!
To pass from (
nimod n2 .
To pass from (
Cm0λ .1= 0!((mmλλ-)0!)! .1=1 Cm1λ .n= (mλ)! .n= mλn
1!(mλ–1)! (C2mλ .n2+n2( ∑im=3λ Cimλ ni-2)) mod n2 =0 because (integer×n2) mod n2=0 B. Paillier’s Cryptosystem Properties
Suppose that we have two plain-texts m1 ,m2 , with two cipher-texts respectively Encrypt(pk,m1 ), Encrypt(pk,m2).
Paillier’s cryptosystem verifies the following equations:
Decrypt( Encrypt(pk,m1 )Encrypt(pk,m2)
mod n2)=(m1+m2) mod n [1]. (
IV. APPLYING OPERATIONS ON PAILLIER’S CRYPTOSYSTEM
Calculating on the cipher-texts and getting the average while decrypting the results could be interesting.
To realize that, we need to follow four steps:
Step 1: Calculate an encryption of ∑ki=1mi mod n by
using (
C=[encrypt(m,n,g) for m in M ]
return mul(C) % (n**2)
Step 2: Calculate an encryption of k–1 ∑ki=1 mi mod n
by
using (
means by calculating [µ] = ( ∏ki=1 ci mod n2)k–1mod nmod n2 . This step is applied on Sagemath as following: def encrypted_mean(M, n,g): k=(len(M)**(-1))% n return (encrypted_sum(M,n,g)**k)%(n**2) •
Step 3: Apply Decrypt( ) function on [µ] to obtain ∑ ki=1 mi mod n which is the average but in Zn.
k
Decrypt(sk,[µ]) =Decrypt(sk,( ∏ki=1 ci mod n2)k–1mod nmod n2) =Decrypt(sk, (Encrypt(pk, ∑ki=1m imod n)) =(k-1mod n . ∑k mi =(k-1 ∑k
i=1 i=1 mi )mod n.
This step is applied on Sagemath as following:
def dec_mean(M,lmd,mu,n,g):
return decrypt(encrypted_mean(M,n,g),lmd,mu,n)
mod n) mod n (using (
Step 4: Applying LLL algorithm or the Extended Euclidean Algorithm to obtain the average result in Q.
Proof:
•
•
The use of LLL algorithm in our case Let a1 , a2 be two vectors that form a basis of a lattice L. The goal of LLL algorithm is to take as input a1, a2 and to give as output a new basis for the lattice L where the lengths of the vectors of the latter are as short as possible.
One of the most important properties of the LLL algorithm is that the first vector given as output represents the shortest one in the lattice L [11].
Suppose that µ*is equal to ∑ik=1 mi such that k gcd( ∑ki=1 mi,k) and gcd(k,n) are equal to 1. And suppose that µ represents the latter in Zn so that it could be written in this way: ∑ki=1 mi mod n . The condition of having k gcd(k,n) =1, taken before assure the existence of k–1 in µ.
In our case, this form is obtained after applying Decrypt formula on [µ]. So we know the value of µ and not that of ∑ki=1 mi nor that of k. A way to find the values of the latters is to apply the two-dimensional lattice theory.
We define a lattice L as following:
L = {(x,y) ∈Z2; x = yµ mod n} (
First, because one can notice that n=0µ mod n therefore (n,0) ∈L and one can also notice that µ = 1µ mod n therefore (µ,1)∈L.
Second, we have n×1–0×µ≠0 therefore (n,0) and (µ,1) are not collinear.
From (
def lattice_LLL(N,avg):
M=Matrix(2,2,[avg,1,N,0]) #The vectors of the basis in a matrix form L=M.LLL() #The new basis vectors return L[0,0]/ L[0,1] #Return the fraction formed by the shortest vector #elements which corresponds to ∑ k
i=k1 mi .
algorithm in Sagemath: def avg_LLL(M,lmd,mu,n,g):
return lattice_LLL(n,dec_mean (M,lmd,mu,n,g)) LLL 2) Extended Euclidean Algorithm idea [11]
The Extended Euclidean Algorithm gives as result the shortest vector in a given two-dimensional lattice L. The only thing that differs the Extended Euclidean Algorithm from LLL Algorithm is that the latter can handle higher dimensions. But in our case we just need two dimensional lattices therefore the two algorithms can be applied and give the same result.
To improve a given basis the Extended Euclidean Algorithm follows these steps: a) Subtract from a vector a linear combination of the others which means • • that in each time the initial vector length is getting shorter. b) Swap two vectors.
def ExtendedEuclide(N,avg): u1=0 u2=N v1=1 v2=moy while u2>sqrt(N):
Q = u2 // v2 [t1,t2]=[u1-v1*Q,u2-v2*Q] [u1,u2]=[v1,v2] [v1,v2]=[t1,t2] return u2/u1 Average Function using Extended Euclidean algorithm in Sagemath: def avg_Euclide(M,lmd,mu,n,g): return ExtendedEuclide (n,dec_mean(M,lmd,mu,n,g)) V. PRACTICAL EXAMPLE OF CALCULATING THE AVERAGE
USING THE CIPHER-TEXTS
Using Sagemath, we show in this part an example that illustrates the previous sections. [nb, min, max, KeySize] = [10, 100, 500, 24] random.seed(int(time.time())) M=[random.randint(min,max) for m in range(nb)] p,q,n,g,lmd,mu=keygen(KeySize) print("Average using LLL= "+str(avg_LLL(M,lmd,mu,n,g))) print("Average using Extended Euclide= "+str(avg_Euclide(M,lmd,mu,n,g)))
Suppose that we have p = 3623 and q = 3833. In this case we have n=pq= 13886959, g=n+1= 13886960, λ= 13879504 and [L(gλ mod n2)]–1= 594224.
Using the public key pk=(n,g), the secret key sk=(p,q) and random numbers r, one can compute cipher-texts given by c=Encrypt(pk, m)=gmrn mod n2 as shown in the table below. [µ] = ( ∏k ci 2 2
In our case, the average of the plain-texts is equal to 1843/5. To obtain it using only the cipher-texts one must follow the steps given in section IV.
As mentioned before the first step is to calculate k–1mod n mod n ) mod n which is equal in our case to 40 1i=012169206101. In the second step, while decrypting the latter; one can obtain 8332544 as a result. Finally, to have the average value in Q, one must apply the Extended Euclidean Algorithm or the LLL algorithm and obtain 1843/5. So this example make us sure that in this way we can always calculate safely on the cipher-texts and obtain the same result as if we are applying the average on the plain-texts.
VI. CONCLUSION AND FUTURE WORK
In this paper, we reviewed the companies’ problem concerning the security issue while using the Cloud Computing in their work and how it can be solved by the homomorphic encryption idea. We present in particular the Murex’s KPIs list based on addition and ordering operations. For additional issue we used an important additive homomorphic scheme known by Paillier’s cryptosystem and we reviewed a numerical application on it. However, in fact, we realized that this cryptosystem could not achieve the ordering idea because of the existence of the modulus in its encryption function.
Based on this problem, future work will focus on finding a new secured cryptosystem that can handle the additive and the ordering issue at the same time. Our objective is to allow Murex Company (and other companies that provide technology solutions to financial market) to calculate their KPIs list easily and efficiently.
We thank Dr. Eric Filiol (ESIEA University, France) for valuable discussions and feedback.
We would also like to thank Murex Company for placing their trust and confidence in our abilities to achieve our purpose.
Finally, the authors would like to acknowledge the National Council for Scientific Research of Lebanon (CNRS – L) for granting a doctoral fellowship for Christiana Zaraket.