Homomorphic encryption


Homomorphic encryption

Homomorphic Encryption is a form of encryption where one can perform a specific algebraic operation on the plaintext by performing a (possibly different) algebraic operation on the ciphertext. Depending on one's viewpoint, this can be seen as a positive or negative attribute of the cryptosystem. Homomorphic encryption schemes are malleable by design and are thus unsuited for secure data transmission. On the other hand, the homomorphic property of various cryptosystems can be used to create [http://web.mit.edu/6.857/OldStuff/Fall02/handouts/L15-voting.pdf secure voting systems] (pdf), collision-resistant hash functions and private information retrieval schemes.

There are several efficient Homomorphic cryptosystems:

*RSA Cryptosystem
*ElGamal cryptosystem
*Goldwasser-Micali cryptosystem
*Benaloh cryptosystem
*Okamoto-Uchiyama cryptosystem
*Paillier cryptosystem
*Naccache-Stern cryptosystem
*Damgård-Jurik cryptosystem
*Boneh-Goh-Nissim cryptosystem

Examples

In the following examples, we use the notation mathcal{E}(x) to denote the encryption of the message "x".

Unpadded RSA

If the public key is "m","e", then the encryption of a message "x" is given by mathcal{E}(x) = x^e mod m. Then we have the homomorphic property

:mathcal{E}(x_1) cdot mathcal{E}(x_2) = x_1^e x_2^e mod m = (x_1x_2)^e mod m = mathcal{E}(x_1 cdot x_2 mod m)

ElGamal

In a group G, if the public key is (G, q, g, h), where h = g^x, and x is the secret key, then the encryption of a message m is mathcal{E}(m) = (g^r,xcdot h^r), for some r in {0, ldots, q-1}. Then we have the homomorphic property

:mathcal{E}(x_1) cdot mathcal{E}(x_2) = (g^{r_1},x_1cdot h^{r_1})(g^{r_2},x_2 cdot h^{r_2}) = (g^{r_1+r_2},(x_1cdot x_2) h^{r_1+r_2}) = mathcal{E}(x_1 cdot x_2)

Goldwasser-Micali

If the public key is the modulus "m", and quadratic non-residue "x", then the encryption of a bit "b" is mathcal{E}(b) = r^2 x^b mod m. Then we have the homomorphic property

:mathcal{E}(b_1)cdot mathcal{E}(b_2) = r_1^2 x^{b_1} r_2^2 x^{b_2} = (r_1r_2)^2 x^{b_1+b_2} = mathcal{E}(b_1 oplus b_2)

where oplus denotes addition modulo 2, (i.e. exclusive-or).

Benaloh

If the public key is the modulus "m", the base "g" and the blocksize "r", then the encryption of a message "x" is g^x u^r mod m. Then we have the homomorphic property

:mathcal{E}(x_1) cdot mathcal{E}(x_2) = (g^{x_1} u_1^r)(g^{x_2} u_2^r) = g^{x_1+x_2} (u_1u_2)^r = mathcal{E}(x_1 + x_2 mod phi(m)/r )

Paillier

If the public key is the modulus "m" and the base "g", then the encryption of a message "x" is mathcal{E}(x) = g^x r^m mod m^2. Then we have the homomorphic property

:mathcal{E}(x_1) cdot mathcal{E}(x_2) = (g^{x_1} r_1^m)(g^{x_2} r_2^m) = g^{x_1+x_2} (r_1r_2)^m = mathcal{E}( x_1 + x_2 mod m)

Open question

While these examples allow one-to-one group operation on plaintexts (either addition or multiplication in these examples), no one has created a cryptosystem which preserves the ring structure of the plaintexts, i.e. allows both addition and multiplication. The best result in this direction is the Boneh-Goh-Nissim cryptosystem which, through operations on the cipthertext, allows addition of plaintext followed by a single multiplication followed by an arbitrary number of additions. This allows evaluation of polynomials of degree 2 on the plaintext through operations on the ciphertext. The system is only practical when the space of plaintexts is relatively small.

References

* [http://www.adastral.ucl.ac.uk/~helger/crypto/link/public/homomorphic.php Homomorphic encryption] in [http://www.adastral.ucl.ac.uk/~helger/crypto/ Cryptology Pointers]
* [http://www.cs.virginia.edu/~pev5b/writing/academic/thesis/node7.html Homomorphic encryption]
* [http://citeseer.ist.psu.edu/726875.html Sufficient conditions for collision-resistant hashing]


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • ElGamal encryption — In cryptography, the ElGamal encryption system is an asymmetric key encryption algorithm for public key cryptography which is based on the Diffie Hellman key agreement. It was described by Taher Elgamal in 1984 [Taher ElGamal, A Public Key… …   Wikipedia

  • Cryptographic Test Correction — is a technique, published in 2008 by Eric Levieil and David Naccache [1] for shifting the burden of correcting Multiple Choice Questionnaires (MQC) to examinees. Because the corrector is only interested in the number of correct answers and not in …   Wikipedia

  • Malleability (cryptography) — Malleability is a property of some cryptographic algorithms.[1] An encryption algorithm is malleable if it is possible for an adversary to transform a ciphertext into another ciphertext which decrypts to a related plaintext. That is, given an… …   Wikipedia

  • Mix network — This article is about cryptographic concept. For the social network, see The Mix Network. Simple decryption mix net. Messages are encrypted under a sequence of public keys. Each mix node removes a layer of encryption using its own private key.… …   Wikipedia

  • Dept. of Computer Science, University of Delhi — संगणक विज्ञान विभाग Established 1981 Students 200 Location New Delhi, India Campus …   Wikipedia

  • Verifiable secret sharing — In cryptography, a secret sharing scheme is verifiable if auxiliary information is included that allows players to verify their shares as consistent. More formally, verifiable secret sharing ensures that even if the dealer is malicious there is a …   Wikipedia

  • Гомоморфное Шифрование — криптографическая система, которая позволяет проводить определенные математические действия с открытым текстом путем произведения (в общем случае других) операций с зашифрованным текстом. Существует несколько частично гомоморфных систем… …   Википедия

  • Гомоморфное шифрование — Гомоморфное шифрование  криптографическая система, которая позволяет проводить определенные математические действия с открытым текстом путем произведения (в общем случае других) операций с зашифрованным текстом. Существует несколько частично …   Википедия

  • Paillier cryptosystem — The Paillier cryptosystem, named after and invented by Pascal Paillier 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. This… …   Wikipedia

  • Naccache–Stern cryptosystem — Note: this is not to be confused with the Naccache–Stern knapsack cryptosystem. The Naccache–Stern cryptosystem is a homomorphic public key cryptosystem whose security rests on the higher residuosity problem. The Naccache–Stern cryptosystem was… …   Wikipedia


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.