Difference between revisions of "BGV"
Line 6: | Line 6: | ||
Until recently, the BGV scheme was considered to be the most efficient homomorphic encryption scheme when performing the same operations on multiple ciphertexts at once. | Until recently, the BGV scheme was considered to be the most efficient homomorphic encryption scheme when performing the same operations on multiple ciphertexts at once. | ||
− | |||
− | |||
− | |||
− | |||
== New noise management technique == | == New noise management technique == |
Revision as of 13:08, 11 January 2021
In 2011, Brakerski, Gentry and Vaikuntanathan (BGV) published the paper [1] in which they introduce a new (leveled) fully homomorphic encryption (FHE) that improves performance and bases security on weaker assumptions than schemes from the previous generation.
A central conceptual contribution of this work is a new way of constructing leveled fully homomorphic encryption schemes (capable of evaluating arbitrary polynomial-size circuits), without Gentry’s bootstrapping procedure.
Until recently, the BGV scheme was considered to be the most efficient homomorphic encryption scheme when performing the same operations on multiple ciphertexts at once.
Contents
New noise management technique
@TODO
Leveled Fully Homomorphic Encryption
Most of the work done by the will focus on the construction of a leveled fully homomorphic scheme, in the sense that the parameters of the scheme depend (polynomially) on the depth of the circuits that the scheme is capable of evaluating.
Definition. We say that a family of homomorphic encryption schemes is leveled fully homomorphic if, for all , they all use the same decryption circuit, compactly evaluates all circuits of depth at most (that use some specified complete set of gates), and the computational complexity of 's algorithms is polynomial (a fixed polynomial for all ) in the security parameter , and the size of the circuit (in the case of the evaluation algorithm).
The construction: FHE without bootstrapping
The authors base the security of their scheme on the hardness of Ring-Learning with errors problems, a generalisation of the classical LWE problem.
Let be a security parameter, representing security against known attacks.
Let be a ring. For any integer , we write for the quotient .
Let be an odd modulus and a ``noise" distribution over . Let be an additional parameter of the system which is larger than .
Let us assume that the plaintext is .
- E.Setup(): Choose a -bit modulus and choose the other parameters , and , appropriately to ensure that the scheme is based on a Ring-LWE instance that achieves security against known attacks. Let and let params = .
- E.SecretKetGen(params): Draw . Set .
- E.PublicKeyGen(params, sk): Recall that the secret key is . This algorithm generates a (column) vector , uniformly and a vector . The algorithm computes
. Then, set to be the matrix obtained by setting on the first column followed by the entries of . We remark that . The algorithm outputs the public key .
- E.Enc(params, pk,m): To encrypt a message , set , sample uniformly and output the ciphertext .
- E.Dec(params, sk, c): Output . Where denotes reduction into the range .
Correctness is easy to verify, whereas we refer to the paper for details upon security.
Key switching (Dimension reduction)
Recall that in the above scheme, the decryption equation for a ciphertext that encrypts a message under the secret key can be written as where is a linear operator which depends on . To be precise, the latter is just the inner product between two vectors in .
To understand the key switching procedures, we have to (at least briefly) describe the following subroutines first:
- BitDecomp(): decomposes into its bit representation, namely where all of the . The procedure outputs the vector
- Powersof2(): outputs the vector
It is easy to see that for vectors of the same length , we have:
Now, key switching consists of two procedures:
- SwitchKeyGen():
- Run for .
- Set (Add Powersof2()), which is an element of to 's first column. Output .
- SwitchKey(): Output .
Note that, in SwitchKeyGen, the matrix consists of encryptions of under the key . Then, pieces of the key are added to these encryptions of . Thus, in some sense, the matrix consists of encryptions of pieces of (in a certain format) under the key .
The authors establish the following correctness result (See Lemma 3 in the paper):
is a valid encryption of under the key , and one can see that the noise of is larger by a small additive factor.
Modulus switching
References
- ↑ Z. Brakerski, C. Gentry, and V. Vaikuntanathan. 2014. (Leveled) Fully Homomorphic Encryption without Bootstrapping. ACM Trans. Comput. Theory 6, 3, Article 13 (July 2014), 36 pages. DOI:https://doi.org/10.1145/2633600