 Open Access
 Total Downloads : 746
 Authors : S. Ramachandram, R.Sridevi, P. Srivani
 Paper ID : IJERTV2IS120681
 Volume & Issue : Volume 02, Issue 12 (December 2013)
 Published (First Online): 28122013
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
A Survey Report On Partially Homomorphic Encryption Techniques In Cloud Computing
1. S. Ramachandram 2. R.Sridevi 3. P. Srivani

Professor &Vice Principal, Oucollege Of Engineering,Dept Of Cse,Hyd

Associate Professor, Jntuh, Dept Of Cse,Hyd

Research Scholar & Asso.Prof., Det Of Cse, Hitam, Hyd
Abstract: Homomorphic encryption is a form of encryption which allows specific types of computations to be carried out on cipher text and obtain an encrypted result which decrypted matches the result of operations performed on the plaintext. As cloud computing provides different services, homomorphic encryption techniques can be used to achieve security. In this paper , We presented the partially homomorphic encryption techniques.
Keywords: Homomorphic, ElGamal, Pailler, RSA, GoldwasserMicali , Benaloh, Okamoto Uchiyama cryptosystem, NaccacheStern cryptosystem, RNS.

INTRODUCTION
Security is a desirable feature in modern system architectures. Homomorphic encryption would allow the chaining together of different services without exposing the data to each of those services. For example a chain of different services from different companies could 1) calculate the tax 2) the currency exchange rate 3) shipping, on a transaction without exposing the unencrypted data to each of those services. Homomorphic encryption schemes are malleable by design. The homomorphic property of various cryptosystems can be
used to create secure voting systems, collisionresistant hash functions, private information retrieval schemes and enable widespread use of cloud computing by ensuring the confidentiality of processed data.
There are several efficient, partially homomorphic cryptosystems. Although a cryptosystem which is unintentionally homomorphic can be subject to attacks on this basis, if treated carefully, homomorphism can also be used to perform computations securely. Section 2 describes about the partially homomorphic encryption techniques.

Partially Homomorphic Encryption Techniques
RSA
In cryptography, RSA[1] is an asymmetric encryption system. If the RSA public key is modulus and exponent , then the encryption of a message is given by
.
The homomorphic property is then
ElGamal Encryption
In cryptography, the ElGamal encryption system[2] is an asymmetric encryption algorithm for public key cryptography which is based on the Diffie Helman exchange . It was described by Taher ElGamal in 1984. ElGamal encryption is used in the free GNU privacy Guard software, recent versions of PGP, and other cryptosystems. The Digital Signature Algorithm is a variant of ElGamal Signature Algorithm, which should not be confused with ElGamal encryption.
ElGamal encryption can be defined over any cyclic Group . Its security depends upon the difficulty of a certain problem in related to computing discrete logarithms.
Key Generation
The key generator works as follows:

Alice generates an efficient description of a multiplicative cyclic group of order with generator
.

Alice chooses a random from
.

Alice computes .

Alice publishes , along with the description of , as her public key. Alice retains as her private
key which must be kept secret.
Encryption
The encryption algorithm works as follows: to encrypt a message to Alice under her
public key ,

Bob chooses a random from
, then calculates
.

Bob calculates the shared secret
.

Bob converts his secret message into an element of .

Bob calculates .

Bob sends the cipher text to Alice.
Note that one can easily find if one knows . Therefore, a new is generated for every message to improve security. For this reason, is also called an ephemeral key.
Decryption
The decryption algorithm works as follows: to decrypt a cipher ext with her private key ,

Alice calculates the shared secret

and then computes which she then converts back into the plaintext message , where is inverse of In the group . (E.g. modular multiplicative inverse if is a subgroup of a multiplication group of integers modulo n).
The decryption algorithm produces the intended message, since
ElGamal encryption is probabilistic meaning that a single plain text can be encrypted to many possible cipher texts, with the consequence that a general ElGamal encryption produces a 2:1
expansion in size from plaintext to cipher text.
Encryption under ElGamal requires two exponentiation. However, these exponentiations are independent of the message and can be computed ahead of time if need be. Decryption only requires one exponentiation.
The division by can be avoided by using an alternative method for decryption. To decrypt a cipher text with Alice's private key ,

Alice calculates
.
is the inverse of . This is a consequence of Langranges Theorem, because
.

Alice then computes , which she then converts back into the plaintext message .
The decryption algorithm produces the intended message, since
.
In the ElGamal cryptosystem, in a group , if the public key is
, where , and is the secret key, then the encryption of a message is
, for some
random . The
homomorphic property is then
The GoldwasserMicali (GM) crypto system[3] is an asymmetric key encryption algorithm developed by Shaff Goldwasser and Silvio Micali in 1982. GM has the distinction of being the first probabilistic publickey encryption scheme which is provably secure under standard cryptographic assumptions. However, it is not an efficient cryptosystem, as cipher texts may be several hundred times larger than the initial plaintext. To prove the security properties of the cryptosystem, Goldwasser and Micali proposed the widely used definition of semantic security.
Because encryption is performed using a probabilistic algorithm, a given plaintext may produce very different cipher texts each time it is encrypted. This has significant advantages, as it prevents an adversary from recognizing intercepted messages by comparing them to a dictionary of known cipher texts.
The scheme relies on deciding whether a given value x is a square mod N, given the factorization (p, q) of N. This can be accomplished using the following procedure:

Compute xp = x mod p, xq = x mod q.

If and
, then x
is a quadratic residue mod N.
Key Generation
Alice generates two distinct large prime numbers p and q, randomly and independently of each other.

Alice computes N = p q.

She then finds some nonresidue x
such that the legendra symbols satisfy and hence
the Jacobi symbol is +1. The value x can for example be found by selecting random values and testing the two Legendre symbols. If (p, q) = 3 mod 4 (i.e., N is a Blum integer), then the value N 1 is guaranteed to have the required property.
The public key consists of (x, N). The secret key is the factorization (p, q).
Message encryption
Suppose Bob wishes to send a message m to Alice:

Bob first encodes m as a string of bits (m1, ., mn).

For every bit , Bob generates a random value from the group of units modulo N, or . He outputs the value
.
Bob sends the cipher text (c1, .. , cn).
Message Decryption
Alice rceives (c1, …, cn). She can recover m
using the following procedure:
1. For each i, using the prime factorization (p, q), Alice determines whether the value ci is a quadratic residue; if so, mi = 0, otherwise mi = 1.
Alice outputs the message m = (m1, …, mn).
In the Goldwasser micali cryptosystem , if the public key is the modulus m and
quadratic nonresidue x, then the encryption of a bit b is , for
some random . The
homomorphic property is then
where denotes addition modulo 2.
The Benaloh Cryptosystem[4] is an extension of the Goldwasser micali cryptosystem(GM) created in 1994 by Josh (Cohen) Benaloh. The main improvement of the Benaloh Cryptosystem over GM is that longer blocks of data can be encrypted at once, whereas in GM each bit is encrypted individually. Like many public key cryptosystem, this scheme works in the group where n is a product of two large primes. This scheme is homomorphic and hence malleable.
Key Generation
A public/private key pair is generated as follows:


Choose a block size r.

Choose large primes p and q such that r divides (p1), gcd(r, (p1)/r) = 1 and gcd(q1,r) = 1.

Set n = pq

Choose such that
.
The public key is then y, n, and the private key is the two primes p, q.
Message encryption
To encrypt a message m, where m is taken to be an element in

Choose a random

Set
Message decryption
To understand decryption, we first notice that for any m, u we have
Since m < r and
, we can conclude that
if and
only if m = 0. So if is an encryption of m, given the secret key p, q we can determine whether m=0. If r is small, we can decrypt z by doing an exhaustive
search, i.e. decrypting the messages yI z for i
from 1 to r. By pre computing values, using the Baby step Gaint step algorithm, decryption can be done in time .
The Paillier crypto system[5], named after and invented by pascal pailler in 1999, is a probabilistic asymmetric algorithm for public key cryptography. The problem of computing nth residue classes is believed to be computationally difficult. The decisional composite residuosity assumption is the intractability hypothesis upon which this cryptosystem is based.
The scheme is an additive homomorphic cryptosystem; this means that, given only the publickey and the encryption of
and , one can compute the encryption of
.
Key Generation

Choose two large prime numbers p
and q randomly and independently of
Security
each other such
that
.
The security of this scheme rests on the Higher residuosity problem specifically, given z, r and n where the factorization of n is unknown, it is computationally infeasible to determine whether z is an r th residue mod n, i.e. if there exists an x such that .
In the Benaloh cryptosystem if the public key is the modulus m and the base g with a blocksize of c, then the encryption of a
message x is , for
some random . The
homomorphic property is then
This property is assured if both primes are of equivalent length, i.e.,
for security parameter .

Compute and
.

Select random integer where

Ensure divides the order of by checking the existence of the following modular multiplicative inverse
, where function is defined
as .
Note that the notation a/b does not denote the modular multiplication of times the modular multiplicative inverse of but rather the quotient of
divided by , i.e., the largest integer value to satisfy the relation .


The public (encryption) key is .

The private (decryption) key is

If using p, q of equivalent length, a simpler variant of the above key generation steps
would be to set
and , where
.
Encryption

Let be a message to be encrypted where

Select random where

Compute cipher text as:
Decryption

Cipher text

Compute message:
Homomorphic properties
A notable feature of the Paillier cryptosystem is its homomorphic properties. As the encryption function is additively homomorphic, the following identities can be described:

Homomorphic addition of plaintexts
The product of two cipher texts will decrypt to the sum of their corresponding plaintexts,
The product of a cipher text with a plaintext raising g will decrypt to the sum of the corresponding plaintexts,

Homomorphic multiplication of plaintexts
An encrypted plaintext raised to the power of another plaintext will decrypt to the product of the two plaintexts,
More generally, an encrypted plaintext raised to a constant k will decrypt to the product of the plaintext and the constant,
However, given the Paillier encryptions of two messages there is no known way to compute an encryption of the product of these messages without knowing the private key.
The OkamotoUchiyama crypto system[6] was discovered in 1998 by T. Okamoto and
S. Uchiyama. The system works in the group , where n is of the form p2q and p and q are large primes.
Key Generation
A public/private key pair is generated as follows:

Generate large primes p and q and set .

Choose such that
The map L should be thought of as a logarithm from the cyclic group H to the additive group , and it is easy to check that L(ab) = L(a) + L(b), and that the L is an isomorphism between these two groups. As is the case with the usual logarithm, L(x)/L(g) is, in a sense, the logarithm of x with base g.

Let h = gn
.
mod n.
We have
The public key is then (n, g, h) and the private key is the factors (p, q).
Message Encryption
To encrypt a message m, where m is taken to be an element in

Select at random. Set
Message Decryption
If we define , then decryption becomes
How the system works
The group
The group has a unique subgroup of order p, call it H. By the uniqueness of H, we must have
So to recover m we just need to take the logarithm with base gp1, which is accomplished by
The NaccacheStern crypto system[7] is a homomorphic public key encryption whose security rests on the higher residuosity problem. The NaccacheStern cryptosystem was discovered by David Naccache and Jacques Stern in 1998. Like many public key cryptosystem, this scheme works in the group where n is a product of two large primes.. This scheme is homomorphic and hence malleable.
Key Generation

Pick a family of k small distinct primes p1,…,pk.

Divide the set in half and set
.
.
For any element x in , we have
xp1 mod p2 is in H, since p divides xp1 1.

Set

Choose large primes a and b such that both p = 2au+1 and q=2bv+1 are prime.

Set n=pq.

Choose a random g mod n such that
g has order (n)/4.
The public key is the numbers , n, g and the private key is the pair p, q.
When k=1 this is essentially the Benaloh cryptosystem.
Message encryption
This system allows encryption of a message
m in the group .

Pick a random .

Calculate
Then E(m) is an encryption of the message
m.
Message decryption
To decrypt, we first find m mod pi for each i, and then we apply the Chinese remainder theorem to calculate m mod .
Given a cipher text c, to decrypt, we calculate
. Thus
where .
Since pi is chosen to be small, mi can be recovered be exhaustive search,
i.e. by comparing to for
j from 1 to pi1.
Once mi is known for ech i, m can be recovered by a direct application of the Chinese remainder theorem.
The Damg ardJurik crypto system[8] is a generalization of the Pailler cryptosystem..
It uses computations modulo where
is an RSA modulus and a (positive) natural number. Paillier's scheme is the special case with . The order of can be divided by . Moreover can be written as the direct product of . is cyclic and of order , while is isomorphic to . For encryption, the message is transformed into the corresponding coset of the factor Group and the security of the scheme relies on the difficulty of distinguishing random elements in different cosets of . It is semantically secure if it is hard to decide if two given elements are in the same coset. Like Paillier, the security of DamgÃ¥rdJurik can be proven under the decisional composite residuosity assumption.
Key generation

Choose two large prime numbers p and q randomly and independently of each other.

Compute and
.

Choose an element such that
for a known relative prime to
and .

Using the chinese remainder theorem , choose such that
and
. For instance could be as in Paillier's original scheme.


The public (encryption) key is .

The private (decryption) key is .

with
xi = X modulo mi
Encryption
Let be a message to be encrypted where .

Select random where .

Compute cipher text as:
.
Decryption

Cipher text

Compute . If c is a valid cipher text then

Apply a recursive version of the pailler decryption mechanism to obtain . As is known, it is possible to compute
.
RNS is homomorphic encryption[9] technique which can be used to achieve security. A residue number system is defined by a set of N integer constants,
{m1, m2, m3, … , mN },
referred to as the moduli. Let M be the least common multiple of all the mi.
Encryption
Any arbitrary integer X smaller than M can be represented in the defined residue number system as a set of N smaller integers
{x1, x2, x3, … , xN}
Decryption
Chinese Remainder theorem can be used to decrypt the number represented in Residue Number System. The Chinese Remainder Theorem is the theorem that enables the conversion of residues back into more traditional form such as Decimal form. With this theorem, for residues {r1, r2, …, rn} of a number x, can be converted back into x, provided the greatest common divisor of any pair of moduli is 1. The theorem can be expressed as:
Where, ri is the residue, Ai is , where M is the product of moduli and Ti is the multiplicative inverse over the ring modulo
, popularly written as .

This paper presents a partially homomorphic encryption techniques used in cloud computing to achieve security.

http://en.wikipedia.org/wiki/RSA

http://en.wikipedia.org/wiki/ElGamal_encr yption

http://en.wikipedia.org/wiki/Goldwasser% E2%80%93Micali_cryptosystem

http://en.wikipedia.org/wiki/Benaloh_cryp tosystem

http://en.wikipedia.org/wiki/Paillier_crypt osystem

http://en.wikipedia.org/wiki/Okamoto%E2
%80%93Uchiyama_cryptosystem

http://en.wikipedia.org/wiki/Naccache%E 2%80%93Stern_cryptosystem

http://en.wikipedia.org/wiki/Damg%C3% A5rd%E2%80%93Jurik_cryptosystem

http://icsd.i2r.a star.edu.sg/staff/sethome/pdf/004.pdf