FHE

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 ${\mathcal {C}}$ and the plaintext ${\mathcal {P}}$ have the algebraic structure of a ring and that $Decrypt:{\mathcal {C}}\to {\mathcal {P}}$ is a ring homomorphism.

Definition. A homomorphic encryption scheme ${\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 ${\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 .