A Survey Report On Partially Homomorphic Encryption Techniques In Cloud Computing

A Survey Report On Partially Homomorphic Encryption Techniques In Cloud Computing

1. S. Ramachandram 2. R.Sridevi 3. P. Srivani

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

2. Associate Professor, Jntuh, Dept Of Cse,Hyd

3. 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.

1. 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, collision-resistant 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.

2. 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 public-key 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:

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

     2. 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.

     1. Alice computes N = p q.

     2. She then finds some non-residue 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:

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

     2. 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 non-residue 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 (p-1), gcd(r, (p-1)/r) = 1 and gcd(q-1,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 y-I 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 n-th 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 public-key and the encryption of

     and , one can compute the encryption of

     .

     Key Generation

     1. 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 .

     2. Compute and

        .

     3. Select random integer where

     4. 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

1. Let be a message to be encrypted where

2. Select random where

3. Compute cipher text as:

Decryption

1. Cipher text

2. 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 pi-1.

    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

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

    2. Compute and

       .

    3. Choose an element such that

       for a known relative prime to

       and .

    4. 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 .

1. Select random where .

2. Compute cipher text as:

.

Decryption

1. Cipher text

2. Compute . If c is a valid cipher text then

3. 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 .

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

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

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

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

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

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

6. http://en.wikipedia.org/wiki/Okamoto%E2

   %80%93Uchiyama_cryptosystem

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

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

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