BFV - Revision history

Gturcas: /* Overview of the BFV scheme */

2020-12-30T10:07:22Z

Overview of the BFV scheme

Gturcas: /* Making the scheme fully homomorphic */

2020-12-30T10:05:45Z

Making the scheme fully homomorphic

Gturcas at 10:04, 30 December 2020

2020-12-30T10:04:35Z

Gturcas at 11:56, 26 May 2020

2020-05-26T11:56:50Z

Gturcas at 11:18, 26 May 2020

2020-05-26T11:18:32Z

Gturcas: /* Description of the scheme */

2020-05-26T11:01:00Z

Description of the scheme

Gturcas: /* Description of the scheme */

2020-05-26T10:46:47Z

Description of the scheme

Gturcas: /* Description of the scheme */

2020-05-26T10:46:09Z

Description of the scheme

Gturcas: /* Description of the scheme */

2020-05-26T10:43:33Z

Description of the scheme

Gturcas at 10:36, 26 May 2020

2020-05-26T10:36:24Z

@@ Line 10: / Line 10: @@
 The homomorphic operations on ciphertext, that will be described later, will carry through encryption to addition and multiplication operations in the plaintext <math> \mathcal R_t </math>.
-If we wish to encrypt an integer or a rational number, then we need to [[encode]] it first into a plaintext polynomial in <math> \mathcal R_t </math> and the result can be encrypted only after that. We mention that distinction should be made between <b> encoding </b> and <b> encrypting </b> data. The first one is a public operation, i.e. anybody can reverse it by <b> decoding </b>, whereas the latter can be reverse just by someone who knows the (secret) encryption key. In
+If we wish to encrypt an integer or a rational number, then we need to encode it first into a plaintext polynomial in <math> \mathcal R_t </math> and the result can be encrypted only after that. We mention that distinction should be made between <b> encoding </b> and <b> encrypting </b> data. The first one is a public operation, i.e. anybody can reverse it by <b> decoding </b>, whereas the latter can be reverse just by someone who knows the (secret) encryption key. In
 order to be able to compute additions and multiplications on, for example, integers in encrypted form,
 the encoding must be such that addition and multiplication of encoded polynomials in <math> \mathcal R_t </math>

@@ Line 69: / Line 69: @@
 ==Making the scheme fully homomorphic==
-What is described above is a somewhat homomorphic encryption scheme. As all existing schemes that are based on [[LWE]] or [[ring-LWE]], a small “noise” component is added to the message during encryption (the vectors <math>e_1,e_2 </math> sampled from the distribution <math> \chi </math> above). Computing homomorphically on ciphertexts will cause these noise to grow up to the point when it becomes so large (in practice, this happens when a certain norm of the vectors <math>e_1,e_2</math> is larger than <math> 1/2 \cdot \lfloor q/t \rceil </math> ) that decryption fails. The bootstrapping approach by Gentry can then be used to lower the noise in a ciphertext to a fixed level determined by the complexity of the decryption circuit. Gentry’s idea of bootstrapping is really simple, namely run
+What is described above is a somewhat homomorphic encryption scheme. As all existing schemes that are based on [https://en.wikipedia.org/wiki/Learning_with_errors LWE] or [https://en.wikipedia.org/wiki/Ring_learning_with_errors ring-LWE], a small “noise” component is added to the message during encryption (the vectors <math>e_1,e_2 </math> sampled from the distribution <math> \chi </math> above). Computing homomorphically on ciphertexts will cause these noise to grow up to the point when it becomes so large (in practice, this happens when a certain norm of the vectors <math>e_1,e_2</math> is larger than <math> 1/2 \cdot \lfloor q/t \rceil </math> ) that decryption fails. The bootstrapping approach by Gentry can then be used to lower the noise in a ciphertext to a fixed level determined by the complexity of the decryption circuit. Gentry’s idea of bootstrapping is really simple, namely run
 the decryption of the somewhat homomorphic scheme above in the encrypted domain, i.e. homomorphically. The result of this operation is an encryption of the same message, but with noise of a fixed
 size. If the decryption circuit can be evaluated in depth D, then the noise after bootstrapping equals the noise one would obtain by evaluating a depth D circuit, which is

@@ Line 1: / Line 1: @@
 Around 2012 Brakerski <ref>Z. Brakerski.
 Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP.
-CRYPTO 2012. http://eprint.iacr.org/2012/078.pdf </ref> proposed a new efficient FHE scheme whose security is based on the [[LWE]] problem. Later on, this scheme was ported to the [[ring-LWE]] setting by Fan and Vercauteren. <ref> J. Fan and F. Vercauteren. Somewhat practical fully homomorphic encryption. Cryptology ePrint Archive, Report
+CRYPTO 2012. http://eprint.iacr.org/2012/078.pdf </ref> proposed a new efficient FHE scheme whose security is based on the [https://en.wikipedia.org/wiki/Learning_with_errors LWE] problem. Later on, this scheme was ported to the [https://en.wikipedia.org/wiki/Ring_learning_with_errors ring-LWE] setting by Fan and Vercauteren. <ref> J. Fan and F. Vercauteren. Somewhat practical fully homomorphic encryption. Cryptology ePrint Archive, Report
 /144, Mar. 2012. https://eprint.iacr.org/2012/144.pdf </ref> The various optimisations achieved by the last two authors made the scheme suitable for implementation. One such implementation is available in Microsoft SEAL <ref name = SEAL> Microsoft Research. Microsoft SEAL (release 3.5). 2020. https://github.com/Microsoft/SEAL </ref> is an actively maintained library which makes homomorphic encryption available in an easy-to-use form both to experts and to non-experts.

← Older revision		Revision as of 11:56, 26 May 2020
Line 78:		Line 78:
	implemented in SEAL for the BFV scheme).		implemented in SEAL for the BFV scheme).

		+	== Applications ==
		+
		+	* CryptoNets: Applying Neural Networks to Encrypted Data
		+	with High Throughput and Accuracy https://www.microsoft.com/en-us/research/publication/cryptonets-applying-neural-networks-to-encrypted-data-with-high-throughput-and-accuracy/
		+
		+	* Private queries on encrypted genomic data https://www.microsoft.com/en-us/research/publication/private-queries-encrypted-genomic-data/
		+
		+	* Logistic regression over encrypted data from fully homomorphic encryption https://www.microsoft.com/en-us/research/publication/logistic-regression-over-encrypted-data-from-fully-homomorphic-encryption-2/


	== References ==		== References ==

← Older revision		Revision as of 11:18, 26 May 2020
Line 66:		Line 66:

	We remark that the last step is the only place where one has to use the evaluation key, therefore having to rely on the extra circular security assumption. In practice, if one does not need to perform bootstrapping for obtaining a fully homomorphic encryption scheme, the reliniarization step can be avoided. For example, in the SEAL library, the function Evaluator::multiply(ct_0, ct_1) performs only the first step in the multiplication and outputs <math>(c_0,c_1, c_2) </math>, a ciphertext of size <math> 3</math>. Homomorphic operations are defined naturally on ciphertexts of arbitrary size and the decryption algorithm works well without reliniarization. The only problem with this approach is that the ciphertexts will grow with the number of homomorphic multiplications we perform, so one has to know a priori an upper bound on this number in order to choose parameters correctly. The problem of choosing parameters is also a delicate one. Increasing <math> q</math> while keeping <math> n </math> constant, one obtains more room for homomorphic multiplications (good), but the security of the scheme decreases (bad). This problem can be mitigated by increasing <math> n </math> as well.		We remark that the last step is the only place where one has to use the evaluation key, therefore having to rely on the extra circular security assumption. In practice, if one does not need to perform bootstrapping for obtaining a fully homomorphic encryption scheme, the reliniarization step can be avoided. For example, in the SEAL library, the function Evaluator::multiply(ct_0, ct_1) performs only the first step in the multiplication and outputs <math>(c_0,c_1, c_2) </math>, a ciphertext of size <math> 3</math>. Homomorphic operations are defined naturally on ciphertexts of arbitrary size and the decryption algorithm works well without reliniarization. The only problem with this approach is that the ciphertexts will grow with the number of homomorphic multiplications we perform, so one has to know a priori an upper bound on this number in order to choose parameters correctly. The problem of choosing parameters is also a delicate one. Increasing <math> q</math> while keeping <math> n </math> constant, one obtains more room for homomorphic multiplications (good), but the security of the scheme decreases (bad). This problem can be mitigated by increasing <math> n </math> as well.
		+
		+	==Making the scheme fully homomorphic==
		+
		+	What is described above is a somewhat homomorphic encryption scheme. As all existing schemes that are based on [[LWE]] or [[ring-LWE]], a small “noise” component is added to the message during encryption (the vectors <math>e_1,e_2 </math> sampled from the distribution <math> \chi </math> above). Computing homomorphically on ciphertexts will cause these noise to grow up to the point when it becomes so large (in practice, this happens when a certain norm of the vectors <math>e_1,e_2</math> is larger than <math> 1/2 \cdot \lfloor q/t \rceil </math> ) that decryption fails. The bootstrapping approach by Gentry can then be used to lower the noise in a ciphertext to a fixed level determined by the complexity of the decryption circuit. Gentry’s idea of bootstrapping is really simple, namely run
		+	the decryption of the somewhat homomorphic scheme above in the encrypted domain, i.e. homomorphically. The result of this operation is an encryption of the same message, but with noise of a fixed
		+	size. If the decryption circuit can be evaluated in depth D, then the noise after bootstrapping equals the noise one would obtain by evaluating a depth D circuit, which is
		+	clearly independent of the starting noise present in the ciphertext. Therefore, if the scheme
		+	can handle circuits of depth <math> D + 1 </math> , we can still handle one multiplication after bootstrapping and thus obtain a fully homomorphic scheme. The BFV scheme is designed such that it handles its own decryption circuit, therefore it can be turned into a fully homomorphic scheme via bootstrapping.
		+
		+	Unfortunately this is slow, and requires the encryption parameters <math>(n,q) </math> to be large enough to support bootstrapping (not currently
		+	implemented in SEAL for the BFV scheme).
		+
		+

	== References ==		== References ==

← Older revision		Revision as of 11:01, 26 May 2020
Line 64:		Line 64:

	and return as output the ciphertext <math>(c_0', c_1')</math>.		and return as output the ciphertext <math>(c_0', c_1')</math>.
		+
		+	We remark that the last step is the only place where one has to use the evaluation key, therefore having to rely on the extra circular security assumption. In practice, if one does not need to perform bootstrapping for obtaining a fully homomorphic encryption scheme, the reliniarization step can be avoided. For example, in the SEAL library, the function Evaluator::multiply(ct_0, ct_1) performs only the first step in the multiplication and outputs <math>(c_0,c_1, c_2) </math>, a ciphertext of size <math> 3</math>. Homomorphic operations are defined naturally on ciphertexts of arbitrary size and the decryption algorithm works well without reliniarization. The only problem with this approach is that the ciphertexts will grow with the number of homomorphic multiplications we perform, so one has to know a priori an upper bound on this number in order to choose parameters correctly. The problem of choosing parameters is also a delicate one. Increasing <math> q</math> while keeping <math> n </math> constant, one obtains more room for homomorphic multiplications (good), but the security of the scheme decreases (bad). This problem can be mitigated by increasing <math> n </math> as well.

	== References ==		== References ==

@@ Line 36: / Line 36: @@
 the secret key under the secret key itself, and to argue security one needs to make the extra
 assumption that the encryption scheme is secure even when the adversary has access to all of
-the evaluation keys which may exist. This point is also made in the SEAL manual <ref> K. Lane. Simple Encrypted Arithmetic Library. Microsoft Research. https://www.microsoft.com/en-us/research/uploads/prod/2017/11/sealmanual-2-3-1.pdf </ref>.
+the evaluation keys which may exist. This point is also explained in the SEAL manual <ref> K. Lane. Simple Encrypted Arithmetic Library. Microsoft Research. https://www.microsoft.com/en-us/research/uploads/prod/2017/11/sealmanual-2-3-1.pdf </ref>.
 * <math>Encrypt(pk,m):</math> For <math> m \in \mathcal R_t </math>, let <math> p_k = (p_0,p_1)</math>. Sample <math> u \leftarrow \mathcal R_2 </math> uniformly and <math>e_1, e_2 \leftarrow \chi </math>. Compute and output

@@ Line 30: / Line 30: @@
 <center> <math> evk = ([-(a_is+e_i)+w^is^2]_q,a_i) </math>. </center>
-The autors note that "one can think of the evaluation key essentially as
+The autors note that one can think of the evaluation key essentially as
 a masking of the secret key raised to the power 2 (or, more generally, to some higher power).
 Unfortunately, it is not possible to argue the uniformity of the evaluation key based on the
@@ Line 36: / Line 36: @@
 the secret key under the secret key itself, and to argue security one needs to make the extra
 assumption that the encryption scheme is secure even when the adversary has access to all of
-the evaluation keys which may exist."
+the evaluation keys which may exist. This point is also made in the SEAL manual <ref> K. Lane. Simple Encrypted Arithmetic Library. Microsoft Research. https://www.microsoft.com/en-us/research/uploads/prod/2017/11/sealmanual-2-3-1.pdf </ref>.
 * <math>Encrypt(pk,m):</math> For <math> m \in \mathcal R_t </math>, let <math> p_k = (p_0,p_1)</math>. Sample <math> u \leftarrow \mathcal R_2 </math> uniformly and <math>e_1, e_2 \leftarrow \chi </math>. Compute and output

← Older revision		Revision as of 10:36, 26 May 2020
Line 56:		Line 56:

	and return as output the ciphertext <math>(c_0', c_1')</math>.		and return as output the ciphertext <math>(c_0', c_1')</math>.
		+
		+	== References ==