Difference between revisions of "FHE"
| Line 1: | Line 1: | ||
== Intuition == | == Intuition == | ||
| + | |||
| + | Let <math> \mathcal E = (\mathcal C, \mathcal P, KeyGen, Encrypt, Decrypt, Evaluate) </math> be a [[Homomorphic encryption|homomorphic encryption scheme]]. A desirable property of <math> \mathcal E </math> is the possibility of evaluation arbitrary functions on ciphertexts from <math> \mathcal C </math> in a meaningful way. Clearly the complexity of <math>Evaluate(f,c)</math> must depend on the complexity of the function <math>f </math>. To measure the latter, we use <math> S_f </math>, the size of a [[boolean circuit]] that computes <math>f </math>. The algorithm <math> Evaluate </math> is efficient if there exists a polynomial <math> g </math> such that for any function <math> f </math> that is represented by a circuit of size <math> S_f </math>, the complexity of <math> Evaluate(f,c_1, \dots, c_t, pk) </math> is at most <math>S_f \cdot g(\lambda) </math>. | ||
| + | |||
== Definitions == | == Definitions == | ||
| Line 5: | Line 8: | ||
Let us fix a security parameter <math> \lambda </math>. Assume that the ciphertext <math> \mathcal C </math> and the plaintext <math> \mathcal P </math> have the algebraic structure of a ring and that <math> Decrypt : \mathcal C \to \mathcal P</math> is a ring homomorphism. | Let us fix a security parameter <math> \lambda </math>. Assume that the ciphertext <math> \mathcal C </math> and the plaintext <math> \mathcal P </math> have the algebraic structure of a ring and that <math> Decrypt : \mathcal C \to \mathcal P</math> is a ring homomorphism. | ||
| − | <b>Definition.</b> A [[Homomorphic encryption|homomorphic encryption scheme]] <math> \mathcal E = (\mathcal C, \mathcal P, KeyGen, Encrypt, Decrypt) </math> is called <i> leveled</i> if the decryption algorithm is correct for for a certain number of ring operations made on <math>\mathcal C </math>. | + | <b>Definition.</b> A [[Homomorphic encryption|homomorphic encryption scheme]] <math> \mathcal E = (\mathcal C, \mathcal P, KeyGen, Encrypt, Decrypt, Evaluate) </math> is called <i> leveled</i> if the decryption algorithm is correct for for a certain number of ring operations made on <math>\mathcal C </math>. |
TODO: Write about the practical reasons for using a <i> leveled </i> scheme. | TODO: Write about the practical reasons for using a <i> leveled </i> scheme. | ||
Revision as of 10:50, 9 March 2020
Contents
Intuition
Let 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 = (\mathcal C, \mathcal P, KeyGen, Encrypt, Decrypt, Evaluate) } be a homomorphic encryption scheme. A desirable property of is the possibility of evaluation arbitrary functions on ciphertexts from in a meaningful way. Clearly the complexity of must depend on the complexity of the function . To measure the latter, we use , the size of a boolean circuit that computes . The algorithm is efficient if there exists a polynomial such that for any function that is represented by a circuit of size , the complexity of is at most .
Definitions
Let us fix a security parameter . Assume that the ciphertext and the plaintext have the algebraic structure of a ring and 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 : \mathcal C \to \mathcal P} is a ring homomorphism.
Definition. A homomorphic 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 = (\mathcal C, \mathcal P, KeyGen, Encrypt, Decrypt, Evaluate) } is called leveled if the decryption algorithm is correct for for a certain number of ring operations made on 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 } .
TODO: Write about the practical reasons for using a leveled scheme.
Definition. A homomorphic 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 called compact if there exists a polynomial 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 s=s(\lambda) } such that the output length 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 Eval(f,c,pk)} is at most 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(\lambda) } bits long, regardless of the ring homomorphism 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 : \mathcal C^{t} \to \mathcal C } or the number of ciphertext inputs 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 t} , for any tuple 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 = (c_1, \dots, c_t) \in \mathcal C^{t}} of ciphertexts.
A homomorphic encryption scheme as above, but for which we do not require 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 s(\lambda) } is polynomial 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 \lambda } is called bounded .
