Homomorphic encryption - Revision history

Gturcas: /* Examples */

2020-12-30T08:09:07Z

Examples

Gturcas: /* Examples */

2020-12-30T08:06:19Z

Examples

Gturcas: /* References */

2020-12-30T08:02:24Z

References

Gturcas: /* Definition */

2020-12-30T08:01:38Z

Definition

Gturcas: /* Definition */

2020-12-30T07:53:51Z

Definition

Gturcas: /* Definition */

2020-12-30T07:52:29Z

Definition

Gturcas at 06:37, 25 May 2020

2020-05-25T06:37:32Z

Gturcas: /* References */

2020-05-25T06:33:26Z

References

Gturcas: /* Examples */

2020-03-09T07:54:35Z

Examples

Gturcas: /* Examples */

2020-03-09T07:54:10Z

Examples

@@ Line 35: / Line 35: @@
 Below we list a few examples of homomorphic encryption schemes. We hope that just presenting the public key together with the <math>Encrypt</math> is enough to give the reader a clear picture of the whole scheme.
-In the [[ElGamal encryption|ElGamal cryptosystem]], in a cyclic group <math>G</math> of order <math>q</math> with generator <math>g</math>, if the public key is <math>(G, q, g, h)</math>, where <math>h = g^x</math>, and <math>x</math> is the secret key, then the encryption of a message <math>m</math> is <math>\mathcal{E}(m) = (g^r,m\cdot h^r)</math>, for some random <math>r \in \{0, \ldots, q-1\}</math>. The homomorphic property is then
+In the [https://en.wikipedia.org/wiki/ElGamal_encryption ElGamal cryptosystem], in a cyclic group <math>G</math> of order <math>q</math> with generator <math>g</math>, if the public key is <math>(G, q, g, h)</math>, where <math>h = g^x</math>, and <math>x</math> is the secret key, then the encryption of a message <math>m</math> is <math>\mathcal{E}(m) = (g^r,m\cdot h^r)</math>, for some random <math>r \in \{0, \ldots, q-1\}</math>. The homomorphic property is then
 :<math>
@@ Line 47: / Line 47: @@
 '''Goldwasser–Micali'''
-In the [[Goldwasser–Micali cryptosystem]], if the public key is the modulus <math>n</math> and quadratic non-residue <math>x</math>, then the encryption of a bit <math>b</math> is <math>\mathcal{E}(b) = x^b r^2 \;\bmod\; n</math>, for some random <math>r \in \{0, \ldots, n-1\}</math>. The homomorphic property is then
+In the [https://en.wikipedia.org/wiki/Goldwasser%E2%80%93Micali_cryptosystem Goldwasser–Micali cryptosystem], if the public key is the modulus <math>n</math> and quadratic non-residue <math>x</math>, then the encryption of a bit <math>b</math> is <math>\mathcal{E}(b) = x^b r^2 \;\bmod\; n</math>, for some random <math>r \in \{0, \ldots, n-1\}</math>. The homomorphic property is then
 :<math>
@@ Line 57: / Line 57: @@
 </math>
-where <math>\oplus</math> denotes addition modulo 2, (i.e. [[Exclusive disjunction|exclusive-or]]).
+where <math>\oplus</math> denotes addition modulo 2, (i.e. [https://en.wikipedia.org/wiki/Exclusive_or Exclusive disjunction]).
 Other examples include the [https://en.wikipedia.org/wiki/RSA_(cryptosystem) RSA ],

@@ Line 34: / Line 34: @@
 Below we list a few examples of homomorphic encryption schemes. We hope that just presenting the public key together with the <math>Encrypt</math> is enough to give the reader a clear picture of the whole scheme.
 In the [[ElGamal encryption|ElGamal cryptosystem]], in a cyclic group <math>G</math> of order <math>q</math> with generator <math>g</math>, if the public key is <math>(G, q, g, h)</math>, where <math>h = g^x</math>, and <math>x</math> is the secret key, then the encryption of a message <math>m</math> is <math>\mathcal{E}(m) = (g^r,m\cdot h^r)</math>, for some random <math>r \in \{0, \ldots, q-1\}</math>. The homomorphic property is then
@@ Line 66: / Line 58: @@
 where <math>\oplus</math> denotes addition modulo 2, (i.e. [[Exclusive disjunction|exclusive-or]]).
 == References ==

← Older revision		Revision as of 08:02, 30 December 2020
Line 68:		Line 68:

	== References ==		== References ==
−	~~{{Reflist\|30em}}~~

@@ Line 26: / Line 26: @@
 As described so far, it is trivial to construct an encryption scheme that can handle all functions. We can just define <math>Evaluate(f,c_1, \dots, c_t, pk) </math> to output <math> (f,c_1, \dots, c_t) </math> without processing the ciphertexts <math>c_i </math> at all. Then, we modify <math>Decrypt</math> slightly. To decrypt <math>(f,c_1, \dots,c_t) </math> first decrypt <math>c_1, \dots, c_t </math> to obtain <math>m_1, \dots, m_t </math> and then apply <math> f </math> to them. But this does not fit the purpose of ''delegating'' the processing of information. In the jewellery store analogy, this is as if the worker sends the box back to Alice without doing any work on the raw precious materials. Then Alice has to assemble the jewellery herself.
-The purpose of delegating computation is to reduce one's workload. In terms of running times, in a practical encryption scheme, decrypting <math>c = Evaluate(f,c_1,\dots, c_t,pk) </math> should require the same amount of computation as decrypting <math> c_1 </math> or any of the ciphertexts <math> c_i </math> for that matter. Some schemes require additionally that <math> c </math> is of the same size as <math>c_1 </math>. This property is called [[compactness]]. Also, in a practical encryption scheme, the algorithms <math>KeyGen </math>, <math>Encrypt</math> and <math> Decrypt</math> should be effectively computable. In terms of complexity, one usually requires that these algorithms should be polynomial in a security parameter <math> \lambda </math>.
+The purpose of delegating computation is to reduce one's workload. In terms of running times, in a practical encryption scheme, decrypting <math>c = Evaluate(f,c_1,\dots, c_t,pk) </math> should require the same amount of computation as decrypting <math> c_1 </math> or any of the ciphertexts <math> c_i </math> for that matter. Some schemes require additionally that <math> c </math> is of the same size as <math>c_1 </math>. This property, called compactness, whose precise definition can be found in  <ref name = BRA> Brakerski, Z., Vaikuntanathan, V.: Efficient fully homomorphic encryption from (standard) LWE, R. Ostrovsky editor, IEEE 52nd Annual Symposium on Foundations of
 An encryption scheme is fully homomorphic ([[FHE]]) if it can handle all functions, is compact and the <math>Evaluate </math> is efficient. The trivial solution presented above is not fully homomorphic, since the size of the cirphertexts outputed by <math> Evaluate </math> depend on the function being evaluated. Moreover, in the trivial example the time needed to decrypt such a ciphertext depends on the evaluated function as well.

@@ Line 18: / Line 18: @@
 == Definition ==
-Every encryption scheme <math>\mathcal E </math> is composed of three algorithms: <math> KeyGen, Encrypt</math>  and <math>Decrypt</math> and two sets <math> \mathcal P </math> (the plaintext space) and <math> \mathcal C</math> (the ciphertext space). All of the algorithms must be efficient, in the sense that they must run in polynomial time with respect to an a priori fixed security parameter <math> \lambda </math>. Encryption schemes can be [https://en.wikipedia.org/wiki/Symmetric-key_algorithm symmetric] or [[asymmetric]], but we will focus here on the asymmetric case.
+Every encryption scheme <math>\mathcal E </math> is composed of three algorithms: <math> KeyGen, Encrypt</math>  and <math>Decrypt</math> and two sets <math> \mathcal P </math> (the plaintext space) and <math> \mathcal C</math> (the ciphertext space). All of the algorithms must be efficient, in the sense that they must run in polynomial time with respect to an a priori fixed security parameter <math> \lambda </math>. Encryption schemes can be [https://en.wikipedia.org/wiki/Symmetric-key_algorithm symmetric] or [https://en.wikipedia.org/wiki/Public-key_cryptography asymmetric]. We will focus here on the asymmetric case (commonly known as public key encryption).
 Basically, given a security parameter <math> \lambda </math>, one generates using KeyGen a pair <math> (sk,pk) </math>. The next two algorithms describe how to associate to a plaintext <math> m \in \mathcal P </math> a ciphertext <math> c = Encrypt(m,pk) \in \mathcal C </math> using the public key <math> pk </math> and viceversa, how to associate to a ciphertext <math> c \in \mathcal C </math> a plaintext <math> m = Decrypt(c,sk) </math>, using the secret key <math> s_k </math> such that <math> Decrypt(Encrypt(m,pk),sk)=m</math>.

@@ Line 6: / Line 6: @@
 On the other hand, at first thought encrypting data seems to cancel out the possible benefits of cloud computing unless one gives the cloud the secret decryption key, sacrificing privacy. Fortunately, there are methods of encrypting data in a ''malleable'' way, such that the encryption can be manipulated without decrypting the data.
-To explain the ideas in a tangible manner, we are going to use a physical analogy: Alice, who owns a jewellery store and wants her workers to process raw precious materials into jewellery pieces. Alice is constantly concerned about giving her workers complete access to the materials in order to minimise the possibility of theft. The analogy was coined by Gentry [https://doi.org/10.1145/1666420.1666444] and we follow the presentation in his paper.
+To explain the ideas in a tangible manner, we are going to use a physical analogy: Alice, who owns a jewellery store and wants her workers to process raw precious materials into jewellery pieces. Alice is constantly concerned about giving her workers complete access to the materials in order to minimise the possibility of theft. The analogy was coined by Gentry <ref name = G10> C. Gentry. Computing arbitrary functions of encrypted data. In "Communications of the ACM", 2010.</ref> and we follow the presentation in his paper.
 '''Alice's plan'''

← Older revision		Revision as of 06:33, 25 May 2020
Line 67:		Line 67:

	== References ==		== References ==
−	~~<references> </references>~~	+	{{Reflist\|30em}}

@@ Line 37: / Line 37: @@
 '''Paillier'''
 '''ElGamal'''
 In the [[ElGamal encryption|ElGamal cryptosystem]], in a cyclic group <math>G</math> of order <math>q</math> with generator <math>g</math>, if the public key is <math>(G, q, g, h)</math>, where <math>h = g^x</math>, and <math>x</math> is the secret key, then the encryption of a message <math>m</math> is <math>\mathcal{E}(m) = (g^r,m\cdot h^r)</math>, for some random <math>r \in \{0, \ldots, q-1\}</math>. The homomorphic property is then