Homomorphic encryption

Homomorphic encryption is a form of encryption which allows specific types of computations to be carried out on ciphertext and obtain an encrypted result which decrypted matches the result of operations performed on the plaintext. For instance, one person could add two encrypted numbers and then another person could decrypt the result, without either of them being able to find the value of the individual numbers.

This 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 unecrypted data to each of those services[1]. Homomorphic encryption schemes are malleable by design. The homomorphic property of various cryptosystems can be used to create secure voting systems,[2] 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, and two fully homomorphic, but less efficient 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.

Partially homomorphic cryptosystems

In the following examples, the notation $\mathcal{E}(x)$ is used to denote the encryption of the message x.

If the RSA public key is modulus $m$ and exponent $e$, then the encryption of a message $x$ is given by $\mathcal{E}(x) = x^e \;\bmod\; m$. The homomorphic property is then

$\mathcal{E}(x_1) \cdot \mathcal{E}(x_2) = x_1^e x_2^e \;\bmod\; m = (x_1x_2)^e \;\bmod\; m = \mathcal{E}(x_1 \cdot x_2)$

ElGamal

In the ElGamal cryptosystem, 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,m\cdot h^r)$, for some random $r \in \{0, \ldots, q-1\}$. The homomorphic property is then

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

Goldwasser-Micali

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 $\mathcal{E}(b) = x^b r^2 \;\bmod\; m$, for some random $r \in \{0, \ldots, m-1\}$. The homomorphic property is then

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

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

Benaloh

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 $\mathcal{E}(x) = g^x r^c \;\bmod\; m$, for some random $r \in \{0, \ldots, m-1\}$. The homomorphic property is then

$\mathcal{E}(x_1) \cdot \mathcal{E}(x_2) = (g^{x_1} r_1^c)(g^{x_2} r_2^c) = g^{x_1+x_2} (r_1r_2)^c = \mathcal{E}(x_1 + x_2 \;\bmod\; c )$

Paillier

In the Paillier cryptosystem, 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 \;\bmod\; m^2$, for some random $r \in \{0, \ldots, m-1\}$. The homomorphic property is then

$\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 \;\bmod\; m)$

Fully homomorphic encryption

Each of the examples listed above allows homomorphic computation of only one operation (either addition or multiplication) on plaintexts. A cryptosystem which supports both addition and multiplication (thereby preserving the ring structure of the plaintexts) is known as fully homomorphic encryption (FHE) and is far more powerful. Using such a scheme, any circuit can be homomorphically evaluated, effectively allowing the construction of programs which may be run on encryptions of their inputs to produce an encryption of their output. Since such a program never decrypts its input, it can be run by an untrusted party without revealing its inputs and internal state. The existence of an efficient and fully homomorphic cryptosystem would have great practical implications in the outsourcing of private computations, for instance, in the context of cloud computing.[3]

The "homomorphic" part of a fully homomorphic encryption scheme can also be described in terms of category theory. If C is the category whose objects are integers (i.e., finite streams of data) and whose morphisms are computable functions, then (ideally) a fully homomorphic encryption scheme elevates an encryption function to a functor from C to itself.

The utility of fully homomorphic encryption has been long recognized. The problem of constructing such a scheme was first proposed within a year of the development of RSA.[4] A solution proved more elusive; for more than 30 years, it was unclear whether fully homomorphic encryption was even possible. During this period, the best result was the Boneh-Goh-Nissim cryptosystem which supports evaluation of an unlimited number of addition operations but at most one multiplication.

Craig Gentry[5] using lattice-based cryptography showed the first fully homomorphic encryption scheme as announced by IBM on June 25, 2009.[6][7] His scheme supports evaluations of arbitrary depth circuits. His construction starts from a somewhat homomorphic encryption scheme using ideal lattices that is limited to evaluating low-degree polynomials over encrypted data. (It is limited because each ciphertext is noisy in some sense, and this noise grows as one adds and multiplies ciphertexts, until ultimately the noise makes the resulting ciphertext indecipherable.) He then shows how to modify this scheme to make it bootstrappable—in particular, he shows that by modifying the somewhat homomorphic scheme slightly, it can actually evaluate its own decryption circuit, a self-referential property. Finally, he shows that any bootstrappable somewhat homomorphic encryption scheme can be converted into a fully homomorphic encryption through a recursive self-embedding. In the particular case of Gentry's ideal-lattice-based somewhat homomorphic scheme, this bootstrapping procedure effectively "refreshes" the ciphertext by reducing its associated noise so that it can be used thereafter in more additions and multiplications without resulting in an indecipherable ciphertext. Gentry based the security of his scheme on the assumed hardness of two problems: certain worst-case problems over ideal lattices, and the sparse (or low-weight) subset sum problem.

Regarding performance, ciphertexts in Gentry's scheme remain compact insofar as their lengths do not depend at all on the complexity of the function that is evaluated over the encrypted data. The computational time only depends linearly on the number of operations performed. However, the scheme is impractical for many applications, because ciphertext size and computation time increase sharply as one increases the security level. To obtain 2k security against known attacks, the computation time and ciphertext size are high-degree polynomials in k. Recently, Stehle and Steinfeld reduced the dependence on k substantially.[8] They presented optimizations that permit the computation to be only quasi-k3.5 per boolean gate of the function being evaluated.

Gentry's Ph.D. thesis[9] provides additional details. Gentry also published a high-level overview of the van Dijk et al. construction (described below) in the March 2010 issue of Communications of the ACM.[10]

In 2009, Marten van Dijk, Craig Gentry, Shai Halevi and Vinod Vaikuntanathan presented a second fully homomorphic encryption scheme,[11] which uses many of the tools of Gentry's construction, but which does not require ideal lattices. Instead, they show that the somewhat homomorphic component of Gentry's ideal lattice-based scheme can be replaced with a very simple somewhat homomorphic scheme that uses integers. The scheme is therefore conceptually simpler than Gentry's ideal lattice scheme, but has similar properties with regards to homomorphic operations and efficiency. The somewhat homomorphic component in the work of van Dijk et al. is similar to an encryption scheme proposed by Levieil and Naccache in 2008,[12] and also to one that was proposed by Bram Cohen in 1998.[13] Cohen's method is not even additively homomorphic, however. The Levieil-Naccache scheme is additively homomorphic, and can be modified to support also a small number of multiplications.

In 2010, Nigel P. Smart and Frederik Vercauteren presented a refinement of Gentry's scheme giving smaller key and ciphertext sizes, but which is still not fully practical.[14] At the rump session of Eurocrypt 2010, Craig Gentry and Shai Halevi presented a working implementation of fully homomorphic encryption (i.e. the entire bootstrapping procedure) together with performance numbers.[15]

In 2010 Riggio and Sicari presented a practical application of homomorphic encryption to a hybrid wireless sensor/mesh network. The system enables transparent multi-hop wireless backhauls that are able to perform statistical analysis of different kinds of data (temperature, humidity, etc.) coming from a WSN while ensuring both end-to-end encryption and hop-by-hop authentication.[16]

Recently, Coron, Naccache and Tibouchi proposed a technique allowing to reduce the public-key size of the van Dijk et al. scheme to 600 KB.[17] In April 2013 the HElib was released, via GitHub, to the open source community which "implements the Brakerski-Gentry-Vaikuntanathan (BGV) homomorphic encryption scheme, along with many optimizations to make homomorphic evaluation runs faster."[18]

Criticisms

'Visions of a fully homomorphic cryptosystem have been dancing in cryptographers' heads for thirty years. I never expected to see one. It will be years before a sufficient number of cryptographers examine the algorithm that we can have any confidence that the scheme is secure.' Bruce Schneier[19]

References

1. ^ Craig Stuntz (2010-03-18). "What is Homomorphic Encryption, and Why Should I Care?".
2. ^ Ron Rivest (2002-10-29). "Lecture Notes 15: Voting, Homomorphic Encryption".
3. ^ Daniele Micciancio (2010-03-01). "A First Glimpse of Cryptography's Holy Grail". Association for Computing Machinery. p. 96. Retrieved 2010-03-17.
4. ^ R. L. Rivest, L. Adleman, and M. L. Dertouzos. On data banks and privacy homomorphisms. In Foundations of Secure Computation, 1978.
5. ^ Craig Gentry. Fully Homomorphic Encryption Using Ideal Lattices. In the 41st ACM Symposium on Theory of Computing (STOC), 2009.
6. ^ http://www-03.ibm.com/press/us/en/pressrelease/27840.wss
7. ^ Michael Cooney (2009-06-25). "IBM touts encryption innovation". Computer World. Retrieved 2009-07-14.
8. ^ Damien Stehle; Ron Steinfeld (2010-05-19). "Faster Fully Homomorphic Encryption" (PDF). International Association for Cryptologic Research. Retrieved 2010-09-15.
9. ^ Craig Gentry. "A Fully Homomorphic Encryption Scheme (Ph.D. thesis)" (PDF).
10. ^
11. ^ Marten van Dijk; Craig Gentry, Shai Halevi, and Vinod Vaikuntanathan (2009-12-11). "Fully Homomorphic Encryption over the Integers" (PDF). International Association for Cryptologic Research. Retrieved 2010-03-18.
12. ^
13. ^ Bram Cohen. "Simple Public Key Encryption".
14. ^
15. ^ Craig Gentry; Shai Halevi. "A Working Implementation of Fully Homomorphic Encryption" (PDF).
16. ^ Roberto Riggio; Sabrina Sicari. "Secure Aggregation in Hybrid Mesh/Sensor Networks" (PDF).
17. ^ Jean-Sébastien Coron; David Naccache, Mehdi Tibouchi. "Public Key Compression and Modulus Switching for Fully Homomorphic Encryption over the Integers" (PDF).
18. ^ Halevi, Shai. "An Implementation of homomorphic encryption". Retrieved 30 April 2013.
19. ^ Schneier, Bruce. "Homomorphic Encryption Breakthrough". Schneier on Security. Retrieved 22 April 2013.