Difference between revisions of "FHE"
(Created page with "== Intuition == == Definition == == Examples == == References ==") |
|||
| Line 1: | Line 1: | ||
== Intuition == | == Intuition == | ||
| − | == Definition == | + | == Definitions == |
| + | |||
| + | 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>. | ||
| + | |||
| + | TODO: Write about the practical reasons for using a <i> leveled </i> scheme. | ||
| + | |||
| + | <b>Definition.</b> A homomorphic encryption scheme <math>\mathcal E</math> is called compact if there exists a polynomial function <math> s=s(\lambda) </math> such that | ||
| + | the output length of <math>Eval(f,c,pk)</math> is at most <math>s(\lambda) </math> bits long, regardless of the ring homomorphism <math> f : \mathcal C^{t} \to \mathcal C </math> or the number of ciphertext inputs <math> t</math>, for any tuple <math>c = (c_1, \dots, c_t) \in \mathcal C^{t}</math> of ciphertexts. | ||
| + | |||
| + | A homomorphic encryption scheme as above, but for which we do not require that <math> s(\lambda) </math> | ||
| + | is polynomial in <math> \lambda </math> is called <b> bounded </b>. | ||
== Examples == | == Examples == | ||
== References == | == References == | ||
Revision as of 11:33, 9 March 2020
Contents
Intuition
Definitions
Let us fix 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 } . Assume that the 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 \mathcal C } and the 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 \mathcal P } 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) } 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 is at most 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 , 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 .
