Fully Homomorphic Encryption Scheme with Probabilistic Encryption Based on Euler’s Theorem and Application in Cloud Computing

Abstract

Homomorphic encryption is an encryption scheme that allows different operations on encrypted data and produces the same result as well that the operations performed on the plaintext. Homomorphic encryption can be used to enhance the security measure of un-trusted systems which manipulates and stores sensitive data. Therefore, homomorphic encryption can be used in cloud computing environment for ensuring the confidentiality of processed data. In this paper, we propose a fully Homomorphic Encryption Scheme with probabilistic encryption for better security in cloud computing.

1 Introduction

Cloud computing enables sharing of services and focuses on maximizing the effectiveness of the shared resources. In the Cloud computing the user data place their data in the cloud, and any computation on the stored data will be performed on the cloud. The Cloud computing has privacy issues because the service provider can access, alter or even delete the data intentionally. Some of the cloud service providers share the information with third parties to provide the effective services. The third party can also access the user private data and modifies the information to make it beneficial to himself. Therefore, security is major thing over the cloud. To protect the private information from cloud service provider or third party—encryption is needed. But it is not enough to protect the computation done on the cloud because to perform computation, decryption of stored data is needed on the cloud.

To protect such computation on the cloud, we need an encryption scheme that enables us to perform the computation of encrypted data. The Fully Homomorphic encryption is the technique that can be used to perform computation on encrypted data [1]. Homomorphic encryption is the encryption scheme that allows to perform some computations on message without decrypting the message [2]. Therefore, using Fully Homomorphic scheme we can perform any computations on the cloud stored data without any obstruction by cloud provider [3].

Here, we propose an Euler’s Theorem-Based Fully Homomorphic Encryption Scheme with probabilistic Encryption to solve the issues of third-party control and data security of Cloud computing.

The Remaining part of the paper is organized as follows. Section 2 describes the related work. Section 3 provides the details of proposed scheme and proof of correctness of scheme. Section 4 presents a working example. Finally, Sect. 5 describes concluding remarks of contributions.

2 Related Work

In 1978, the concept of Homomorphic encryption introduced by Ronald Rivest, Leonard Adleman, and Michael Dertouzos. In 1982, Shafi Goldwasser and Silvio Micali invented an additive Homomorphic encryption that can encrypt only single bit. In 1999 Pa Paillier also given an additive Homomorphic encryption. In 2005, a security system that can compute only one multiplication and an unlimited number of additions proposed by Dan Boneh, et al. In 2009, the first fully Homomorphic encryption system that computes an arbitrary number of additions and multiplications proposed by Gentry and Halevi [4], Gentry [5]. Gentry [3] also proposed ideal lattices hardness based a fully homomorphic encryption in 2009. In 2010, A Fully homomorphic encryption scheme based on integers given by Van Dijk et al. [6]. In 2012, Xiang Guangli, Cui Zhuxiao proposed Fermat’s Little Theorem Based, Algebra Homomorphic Encryption Scheme that works for rational number [7].

3 Fully Homomorphic Encryption with Probabilistic Encryption

Our proposed scheme is fully homomorphic scheme with probabilistic Encryption, which supports both additive and multiplicative homomorphism property. It is also based on Euler’s theorem that can be thought of as a generalization of Fermat’s little theorem. The Fermat theorem uses prime modulus, and the modulus in Euler’s theorem is an integer. Two versions of Euler theorem are as follows:

• 1. If a and n are co-prime, then $a^{{{\varnothing }\left( n \right)}} { \equiv }\,1\left( {\bmod \, n} \right)\text{.}$

• 2. It removes the condition that a and n should be co-prime. If $n = \,p \times q, a < n,$ and k an integer, then $a^{{k \times {\varnothing }\left( n \right) + 1}} \equiv a\left( {\bmod \, n} \right)$.

The Euler’s theorem sometimes is helpful for quickly finding a solution to some exponentiations. The proposed Homomorphic encryption scheme consists three phases which are as follows:

• Key generation

• Message Encryption

• Message Decryption

Phase - I: Key Generation

• 1. Select two prime numbers $p$ and q

• 2. Calculate n = $p \times q$ and ${\varnothing }\left( n \right)$

• 3. Select another prime number z such that $\gcd \left( {n,z} \right) = 1$

• 4. Calculate $x = n \times z$

Phase - II: Messages Encryption

• 1. Messages addition $\left( {M_{1} + \, M_{2} } \right)$ and multiplication $(M_{1} \text{ * } \, M_{2} )$ should be less than < n., therefore, M ₁ & M ₂ will always be less than n

• 2. Select two random integer k ₁ and k ₂ for probabilistic encryption

• 3. $C_{1 } = M^{{k_{1} \times \varnothing \left( n \right) + 1 }} \bmod x$ and $C_{2 } = M^{{k_{2} \times \varnothing \left( n \right) + 1 }} \bmod x$

  Here, $C_{1 } \, {\text{and}} \, C_{2 }$ are cipher texts

• 4. Evaluate result $C_{3 }$ after performing operations on cipher texts ${{C}}_{1 }$ and ${{C}}_{2 }$

Phase - III: Message Decryption

• 1. $M = C_{3 } \bmod n$, Where $C_{3 }$ is cipher text after performing operations on $C_{1 }$ and $C_{2 }$, $n$ is private key and $M$ is plain text

Proof of Correctness of scheme

$$ \begin{aligned} C & = M^{k \times \varnothing \left( n \right) + 1 } \bmod \;x \\ D & = C \bmod \,n \\& = \left( {M^{k \times \varnothing \left( n \right) + 1} \bmod \,x} \right)\bmod \,n \\ & = \left( {M^{k \times \varnothing \left( n \right) + 1} \bmod \,n} \right)\bmod \, x \\ \end{aligned} $$

Now by second version of Euler’s theorem, we know that $\left( {a^{k \times \varnothing \left( n \right) + 1} } \right) \equiv a\left( {\bmod \,n} \right)$

$= \left( {M } \right)\bmod \, x = M,M < x$ (Hence proved)

• Homomorphism

For message M ₁ and M ₂, we have the corresponding cipher texts as C ₁ and C ₂, and random integer’s k ₁ and k ₂ used for deciphering, respectively. The multiplicative and additive Homomorphic property and their proof are presented below.

• Multiplicative homomorphism

Multiplicative homomorphism property is stated as:

$$ M_{1 } \times M_{2} = {\text{DEC}}\left[ {{\text{ENC}}\left( {M_{1 } } \right) \times {\text{ENC}}\left( {M_{2} } \right)} \right] $$

DEC represents Decryption function, and ENC represents Encryption function.

Proof

$$ \begin{aligned} C_{1 } & = \left( {M_{1}^{{k_{1} \times \varnothing \left( n \right) + 1}} \bmod \,x} \right), \\ C_{2 } & = \left( {M_{2}^{{k_{2} \times \varnothing \left( n \right) + 1}} \bmod \, x} \right) \\ C_{1 } \times C_{2 } & = \left( {M_{1}^{{k_{1} \times \varnothing \left( n \right) + 1}} \bmod \,x} \right) \times \left( {M_{2}^{{k_{2} \times \varnothing \left( n \right) + 1}} \bmod \,x} \right) \\ D\left( {C_{1} \times C_{2} } \right) & = (C_{1 } \times C_{2} ) \bmod \, n \\ & = \left[ {\left( {M_{1}^{{k_{1} \times \varnothing \left( n \right) + 1}} \bmod \, x} \right) \times \left( {M_{2}^{{k_{2} \times \varnothing \left( n \right) + 1}} \bmod \,x} \right)} \right] \bmod \,n \\ & = \left[ { \left( {M_{1}^{{k_{1} \times \varnothing \left( n \right) + 1}} \bmod \,x} \right)\bmod \, n \times \left( {M_{2}^{{k_{2} \times \varnothing \left( n \right) + 1}} \bmod \,x} \right)\bmod \, n} \right] \\ & = \left[ { \left( {M_{1}^{{k_{1} \times \varnothing \left( n \right) + 1}} \bmod \,n} \right)\bmod \, x \times \left( {M_{2}^{{k_{2} \times \varnothing \left( n \right) + 1}} \bmod \,n} \right)\bmod \, x} \right] \end{aligned} $$

Now, we know that $\left( {a^{k \times \varnothing \left( n \right) + 1} } \right) \equiv a\left( {\bmod \, n} \right)$ so

$$ = \left[ {\left( {M_{1} \bmod \, x} \right) \times (M_{2} \bmod \,x} \right)] = M_{1 } \times M_{2} $$

• Additive Homomorphism:

Additive homomorphism property is stated as:

$$ M_{1} + M_{2} = {\text{DEC}}\left[ {{\text{ENC}}\left( {M_{1} } \right) + {\text{ENC}}\left( {M_{2} } \right)} \right] $$

Proof

$$ \begin{aligned} C_{1 } & = \left( {M_{1}^{{k_{1} \times \varnothing \left( n \right) + 1}} \bmod \, x} \right),\\ C_{2 } & = \left( {M_{2}^{{k_{2} \times \varnothing \left( n \right) + 1}} \bmod \,x} \right) \\ C_{1 } + C_{2 } & = \left( {M_{1}^{{k_{1} \times \varnothing \left( n \right) + 1}} \bmod \, x} \right) + \left( {M_{2}^{{k_{2} \times \varnothing \left( n \right) + 1}} \bmod \; x} \right) \\ D\left( {C_{1} + C_{2} } \right) & = (C_{1 } + C_{2} ) \bmod \, n \\ & = \left[ {\left( {M_{1}^{{k_{1} \times \varnothing \left( n \right) + 1}} \bmod \, x} \right) + \left( {M_{2}^{{k_{2} \times \varnothing \left( n \right) + 1}} \bmod \,x} \right)} \right] \bmod \,n \\ & = \left[ { \left( {M_{1}^{{k_{1} \times \varnothing \left( n \right) + 1}} \bmod \,x} \right)\bmod \, n + \left( {M_{2}^{{k_{2} \times \varnothing \left( n \right) + 1}} \bmod \, x} \right) \bmod \,n} \right] \\ & = \left[ { \left( {M_{1}^{{k_{1} \times \varnothing \left( n \right) + 1}} \bmod \,n} \right)\bmod \,x + \left( {M_{2}^{{k_{2} \times \varnothing \left( n \right) + 1}} \bmod \, n} \right)\bmod \, x} \right] \\ \end{aligned} $$

Now we know that $\left( {a^{k \times \varnothing \left( n \right) + 1} } \right) \equiv a\left( {\bmod \, n} \right)$ so

$$ = \left[ {\left( {M_{1} } \right)\bmod \,x + \left( {M_{2} } \right)\bmod \, x} \right] = M_{1} + M_{2} $$

4 Working Example

Example

Let we take two prime number p = 5 and q = 7, then

$$ n = p \times q \to n = 5 \times 7 \to n = 35 $$

Now calculate $\varnothing \left( {\text{n}} \right)$ according to the Euler Totient function, $\varnothing \left( {35} \right) = 24,$

Now select a prime number z such that gcd(n, z) = 1

Let z = 31, and calculate gcd(35, 31) = 1,

Now, calculate x $= n \times z \to$ x $= 35 \times 31 \to x = 1085$

Now take two random integer k ₁ = 3 and k ₂ = 2, and two messages $m_{1} = 2 \;{\text{and}}\; m_{2} = 4,$ such that ($m_{1} + m_{2}$) and ($m_{1} *m_{2}$) less than n

Now $c_{1} = m{_{1}}^{{k_{1} \times \varnothing \left( n \right) + 1}} \bmod \,x$

$$ c_{1} = 2^{{3 \times \varnothing \left( {35} \right) + 1}} \, \bmod \,1085{ \to }c_{1} = 2^{3 \times 24 + 1} \bmod \,1085 \to \,c_{1} = 597 $$

And $c_{2} = m{_{2}}^{{k_{2} \times \varnothing \left( n \right) + 1}} \, \bmod \, x$

$$ c_{2} = 4^{{2 \times \varnothing \left( {35} \right) + 1}} \,\bmod \, 1085{ \to }c_{2} = 4^{2 \times 24 + 1} \bmod \, 1085{ \to } c_{2} = 39 $$

• Additive Homomorphism:

Let the addition of two encrypted messages is c ₃ then

$$ c_{3} = c_{1} + c_{2} \to c_{3} = 5 9 7+ 3 9\to c_{3} \, = 6 3 6 $$

Now decryption of this message is m ₃ then

$m_{3} \, = c_{3} \,\bmod \,n \to m_{3} = 636\,\bmod \,35 \to m_{3} = 6,$ this is equal to m ₁ + m ₂ (i.e., 2 + 4 = 6)

• Multiplicative homomorphism:

Let the multiplication of two encrypted messages is c ₄ then

$$ c_{4} = c_{1} \times c_{2} \to c_{4} = 5 9 7\times 3 9\to c_{4} = 2 3 , 2 8 3 $$

Now let the decryption of this message is m ₄ then

m ₄ = c ₄ mod n $\to$ m ₄ = 23,283 mod 35 $\to$ m ₄ = 8, this is equal to m ₁ $\times$ m ₂ (i.e. 2 $\times$ 4 = 8).

5 Conclusion

In this paper, a Fully Homomorphic encryption scheme was applied to Cloud computing with different computations on cipher text without decryption. The Homomorphic encryption schemes are used in secure electronic voting, searching over encrypted data, securing biometric information etc. The operations on small numbers are supported by Fully Homomorphic encryption scheme till now. In future, we can develop a fully Homomorphic encryption scheme that support a large number of circuits.