Difference between revisions of "Homomorphic encryption"
| Line 18: | Line 18: | ||
== Definition == | == Definition == | ||
| − | Every encryption scheme <math>\mathcal E </math> is composed of three algorithms: KeyGen, Encrypt and Decrypt and two sets P (the plaintext space) and C (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 [[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 [[symmetric]] or [[asymmetric]], but we will focus here on the asymmetric case. |
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>. | 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>. | ||
| − | A '''homomorphic encryption scheme''' has a fourth algorithm Evaluate, which is associated to a set <math> \mathcal F </math> of permitted functions. For any function $f \in \mathcal F$ and any ciphertexts <math> c_1,\dots, c_t \in \mathcal C </math> with <math>c_i = Encrypt(m_i, pk) </math>, the algorithm <math>Evaluate(f,c_1,\dots, c_t,pk) </math> outputs a ciphertext <math>c</math> that encrypts <math> f(m_1, \dots, m_t) </math>. In other words, we want that <math> Decrypt(c,sk) = f(m_1, \dots, m_t)</math>. As a shorthand we say that <math> \mathcal E </math> can ''handle functions'' in <math> \mathcal F </math>. For a function <math>g \not \in \mathcal F</math>, <math>Evaluate(g,c_1, \dots, c_t,pk) </math> is not guaranteed to output anything meaningful. | + | A '''homomorphic encryption scheme''' has a fourth algorithm <math>Evaluate</math>, which is associated to a set <math> \mathcal F </math> of permitted functions. For any function $f \in \mathcal F$ and any ciphertexts <math> c_1,\dots, c_t \in \mathcal C </math> with <math>c_i = Encrypt(m_i, pk) </math>, the algorithm <math>Evaluate(f,c_1,\dots, c_t,pk) </math> outputs a ciphertext <math>c</math> that encrypts <math> f(m_1, \dots, m_t) </math>. In other words, we want that <math> Decrypt(c,sk) = f(m_1, \dots, m_t)</math>. As a shorthand we say that <math> \mathcal E </math> can ''handle functions'' in <math> \mathcal F </math>. For a function <math>g \not \in \mathcal F</math>, <math>Evaluate(g,c_1, \dots, c_t,pk) </math> is not guaranteed to output anything meaningful. |
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. | 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. | ||
Revision as of 15:14, 3 March 2020
Intuitive idea
Suppose one would like to delegate the ability of processing its data without giving away access to it. This type of situation becomes more and more frequent with the widespread use of cloud computing. To store unencrypted data in the cloud is very risky and, for some types of data such as medical records, can even be illegal.
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 [1] and we follow the presentation in his paper.
Alice's plan
Use a transparent impenetrable glovebox (see image) secured by a lock for which only Alice has the key. Using the gloves, a worker can assemble pieces of jewellery using the materials that were previously locked inside the box by Alice. When the pieces are finished, she unlocks the box with her key and extracts them.
The locked glovebox with the raw precious materials inside is an analogy for an encryption of some data Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle m_1, \dots, m_t } which can be accessed only using the decryption key. The gloves should be regarded as the malleability or the homomorphic property of the encryption. The finished piece of jewellery in the box can be thought of as the encryption of , a desired computation using the initial data. The lack of physical access to the raw precious materials in the box is an analogy for the fact that knowing encryptions of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle m_1, \dots, m_t } or Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle f(m_1, \dots, m_t) } does not give any information about Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle m_1, \dots, m_t } or Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle f(m_1, \dots, m_t) } , without the knowledge of the decryption key.
Of course, Alice's jewellery store, like any analogy, does not represent some aspect of homomorphic encryption very well and one does not have to take it too literally. Some flaws of this analogy are discussed in Section 4 of Gentry's aforementioned article.
Definition
Every encryption scheme Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mathcal E } is composed of three algorithms: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle KeyGen, Encrypt} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle Decrypt} and two sets Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mathcal P } (the plaintext space) and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mathcal C} (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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \lambda } . Encryption schemes can be symmetric or asymmetric, but we will focus here on the asymmetric case.
Basically, given a security parameter Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \lambda } , one generates using KeyGen a pair Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle (sk,pk) } . The next two algorithms describe how to associate to a plaintext Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle m \in \mathcal P } a ciphertext Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle c = Encrypt(m,pk) \in \mathcal C } using the public key Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle pk } and viceversa, how to associate to a ciphertext Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle c \in \mathcal C } a plaintext Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle m = Decrypt(c,sk) } , using the secret key Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle s_k } such that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle Decrypt(Encrypt(m,pk),sk)=m} .
A homomorphic encryption scheme has a fourth algorithm Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle Evaluate} , which is associated to a set Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mathcal F } of permitted functions. For any function $f \in \mathcal F$ and any ciphertexts Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle c_1,\dots, c_t \in \mathcal C } with Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle c_i = Encrypt(m_i, pk) } , the algorithm Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle Evaluate(f,c_1,\dots, c_t,pk) } outputs a ciphertext Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle c} that encrypts Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle f(m_1, \dots, m_t) } . In other words, we want that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle Decrypt(c,sk) = f(m_1, \dots, m_t)} . As a shorthand we say that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mathcal E } can handle functions in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mathcal F } . For a function Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle g \not \in \mathcal F} , Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle Evaluate(g,c_1, \dots, c_t,pk) } is not guaranteed to output anything meaningful.
As described so far, it is trivial to construct an encryption scheme that can handle all functions. We can just define Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle Evaluate(f,c_1, \dots, c_t, pk) } to output Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle (f,c_1, \dots, c_t) } without processing the ciphertexts Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle c_i } at all. Then, we modify Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle Decrypt} slightly. To decrypt Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle (f,c_1, \dots,c_t) } first decrypt Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle c_1, \dots, c_t } to obtain Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle m_1, \dots, m_t } and then apply Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle f } 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.
