Efficient FHE from (Standard) LWE - Revision history

Gturcas: /* The Bootstrappable Scheme BTS */

2021-01-04T13:15:18Z

The Bootstrappable Scheme BTS

Gturcas: /* Bootstrapping BTS into a Fully Homomorphic encryption scheme */

2021-01-04T13:11:06Z

Bootstrapping BTS into a Fully Homomorphic encryption scheme

Gturcas: /* A Somewhat Homomorphic encryption Scheme SH */

2021-01-04T13:10:01Z

A Somewhat Homomorphic encryption Scheme SH

Gturcas: /* A Somewhat Homomorphic encryption Scheme SH */

2021-01-04T13:09:26Z

A Somewhat Homomorphic encryption Scheme SH

Gturcas at 13:05, 4 January 2021

2021-01-04T13:05:01Z

Gturcas at 13:03, 4 January 2021

2021-01-04T13:03:38Z

Gturcas at 13:02, 4 January 2021

2021-01-04T13:02:50Z

Gturcas at 13:01, 4 January 2021

2021-01-04T13:01:13Z

Gturcas at 12:59, 4 January 2021

2021-01-04T12:59:11Z

Gturcas at 12:58, 4 January 2021

2021-01-04T12:58:16Z

@@ Line 85: / Line 85: @@
 Although the scheme <math> SH </math> presented in the previous section is not bootstrappable, the authors introduce a new "dimension-modulus reduction" technique which allows them to transform <math> SH </math> into a scheme which has much shorter ciphertexts and lower decryption complexity.
-The new scheme inherits the parameters <math> (n,m,q, \chi, L) </math> from <math> SH </math> and has additional parameters <math> (k,p, \hat{\chi}) </math>, which we will refer to as the small parameters.
+The new scheme inherits the parameters <math> (n,m,q, \chi, L) </math> from <math> SH </math> and has additional parameters <math> (k,p, \hat{\chi}) </math>, to which the authors refer as "small parameters".
 The parameters <math>n,q \in \mathbb N </math> are the "long" dimension and the "long" modulus. while <math>k,p </math> are the "short" dimension and modulus, respectively. <math>\chi, \hat{\chi} </math> are the long and short noise distributions taken over <math>\mathbb Z_{q} </math> and <math> \mathbb Z_p </math>. The parameter <math> m</math> is used just for key generation and the parameter <math>L </math> is an upper bound on the multiplicative depth of the evaluated function.
-Let us call this new scheme <math>BTS </math>.
+For details concerning this new scheme <math>\mathrm{BTS}</math> as well as the proof that this is boostrappable, hence can (at least in theory) evaluate any circuit, we refer to the article listed below.
-In the paper there is a discussion of the optimal parameter values. We choose not to include that here, but instead we consider the following easy to understand values as an example.
+== References ==

← Older revision		Revision as of 13:11, 4 January 2021
Line 96:		Line 96:

	TODO: Keygen, Encrypt, HomEval, Decrypt.		TODO: Keygen, Encrypt, HomEval, Decrypt.
−
−	~~== Bootstrapping BTS into a Fully Homomorphic encryption scheme ==~~
−
−	~~'''Efficiency of the Scheme'''~~

@@ Line 75: / Line 75: @@
 By computing <math> w_{mult} - \langle v_{mult}, s_{l+1} \rangle </math> one will see that indeed this will be equal to the plaintext output <math> \mu \mu' </math> plus some noise term that depends on the input ciphertexts <math>c, c' </math> and also on the evaluation key <math> \Psi</math>.
-The advantages of using this re-liniarisation technique for multiplications are detailed in Section 1.1 of [https://eprint.iacr.org/2011/344.pdf 1].
+The advantages of using this re-liniarisation technique for multiplications are detailed in Section 1.1 of [https://eprint.iacr.org/2011/344.pdf [1]].
 <b> Decryption </b>: In this scheme, we only want to decrypt ciphertexts of the form <math>c = ((v,w),L) </math>, which are the ones that are <math>SH.Eval(\dots)</math> outputs. The algorithm <math>SH.Dec_{s_L}(c)</math> computes and <b> outputs </b>:

@@ Line 75: / Line 75: @@
 By computing <math> w_{mult} - \langle v_{mult}, s_{l+1} \rangle </math> one will see that indeed this will be equal to the plaintext output <math> \mu \mu' </math> plus some noise term that depends on the input ciphertexts <math>c, c' </math> and also on the evaluation key <math> \Psi</math>.
-TODO: Talk about the advantage of using this re-liniarization, maybe in a separate section.
+The advantages of using this re-liniarisation technique for multiplications are detailed in Section 1.1 of [https://eprint.iacr.org/2011/344.pdf 1].
 <b> Decryption </b>: In this scheme, we only want to decrypt ciphertexts of the form <math>c = ((v,w),L) </math>, which are the ones that are <math>SH.Eval(\dots)</math> outputs. The algorithm <math>SH.Dec_{s_L}(c)</math> computes and <b> outputs </b>:

@@ Line 3: / Line 3: @@
 introduced a fully homomorphic encryption scheme which is based only on the [https://en.wikipedia.org/wiki/Learning_with_errors LWE] assumption. The authors show that the security of the scheme can be reduced to the worst-case hardness of [https://en.wikipedia.org/wiki/Lattice_problem short vector problem] on arbitrary latices.
-They start by introducing a somewhat homomorphic encryption scheme SH, which is then transformed into a bootstrappable scheme BTS. In doing so, the authors deviate from previously known techniques of “squashing” the decryption algorithm of SH that has been used by Dijk, Gentry, Halevi and Vaikuntanathan in [[FHE over the Integers]] and instead introduce a new “dimension-modulus reduction” technique, which shortens the ciphertexts and simplifies the decryption circuit of SH. This is all achieved without introducing additional assumptions, such as the hardness of the sparse subset-sum problem.
+They start by introducing a somewhat homomorphic encryption scheme SH, which is then transformed into a bootstrappable scheme BTS. In doing so, the authors deviate from previously known techniques of “squashing” the decryption algorithm of SH that has been used by Dijk, Gentry, Halevi and Vaikuntanathan in [[FHE over the Integers]] and instead introduce a new “dimension-modulus reduction” technique, which shortens the ciphertexts and simplifies the decryption circuit of SH. This is all achieved without introducing additional assumptions, such as the hardness of the [https://eprint.iacr.org/2011/567.pdf sparse subset-sum problem].
 This scheme has particularly short ciphertexts and for this reasons the authors managed to use it for constructing an efficient single-server private information retrieval (PIR) protocol.

@@ Line 1: / Line 1: @@
 As anounced in the title, Brakerski and Vaikuntanathan <ref> Z. Brakerski, F. Vaikuntanathan, Efficient Fully Homomorphic Encryption from (Standard) LWE, SIAM J. Comput., 43(2), 831–871.</ref>
-introduced a fully homomorphic encryption scheme which is based only on the [https://en.wikipedia.org/wiki/Learning_with_errors LWE] assumption. The authors show that the security of the scheme can be reduced to the worst-case hardness of [[short vector problems]] on arbitrary latices.
+introduced a fully homomorphic encryption scheme which is based only on the [https://en.wikipedia.org/wiki/Learning_with_errors LWE] assumption. The authors show that the security of the scheme can be reduced to the worst-case hardness of [https://en.wikipedia.org/wiki/Lattice_problem short vector problem] on arbitrary latices.
 They start by introducing a somewhat homomorphic encryption scheme SH, which is then transformed into a bootstrappable scheme BTS. In doing so, the authors deviate from previously known techniques of “squashing” the decryption algorithm of SH that has been used by Dijk, Gentry, Halevi and Vaikuntanathan in [[FHE over the integers]] and instead introduce a new “dimension-modulus reduction” technique, which shortens the ciphertexts and simplifies the decryption circuit of SH. This is all achieved without introducing additional assumptions, such as the hardness of the sparse subset-sum problem.