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 10: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 such that the output length of is at most bits long, regardless of the ring homomorphism 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 .
