Difference between revisions of "BGV"
| Line 1: | Line 1: | ||
| − | + | In 2011, Brakerski, Gentry and Vaikuntanathan (BGV) published the paper <ref name = "BGV"> 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</ref> 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 | A central conceptual contribution of this | ||
| Line 14: | Line 14: | ||
@TODO | @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. | ||
| + | |||
| + | <b> Definition.</b> We say that a family of homomorphic encryption schemes <math> \mathcal E^{(L)}: L \in \mathbb Z^{+} </math> is leveled fully homomorphic if, for all <math>L \in \mathbb Z^{+} </math>, they all use the same decryption circuit, <math>\mathcal E^{(L)} </math> compactly evaluates all circuits of depth at most <math> L </math> (that use some specified complete set of gates), and the computational complexity of <math> \mathcal E^{(L)} </math>'s algorithms is polynomial (a fixed polynomial for all <math>L </math>) in the security parameter <math> L</math>, and the size of the circuit (in the case of the evaluation algorithm). | ||
Revision as of 13:44, 5 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.
Modulus switching
@TODO
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).
- ↑ 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
