BGV

BGV (Brakerski-Gentry-Vaikuntanathan) Scheme

The BGV scheme, developed by Brakerski, Gentry, and Vaikuntanathan, is a homomorphic encryption scheme based on the Ring Learning with Errors (RLWE) problem.

Key Components

1. Secret Key Generation: The secret key $s$ is chosen from the polynomial ring ${\mathbb{Z}}_q[X]/(X^N+1)$.
2. Public Key Generation: The public key is generated using the secret key and consists of two polynomials $(a,b=-a\cdot s+e)$, where $a$ is a randomly chosen polynomial and $e$ is a small noise (error).
3. Encryption: To encrypt a message $m\in {\mathbb{Z}}_t[X]/(X^N+1)$, a random polynomial $r$ is selected, and the ciphertext $c=(c_1,c_2)=(a\cdot r+e_1,b\cdot r+e_2+m)$ is generated.
4. Decryption: To decrypt the ciphertext $c$, compute $m^{\prime }=c_2+s\cdot c_1(\mathrm{mod}q)$. Here, $m^{\prime }\approx m$.

Homomorphic Operations

The BGV scheme supports homomorphism for both addition and multiplication.

• Homomorphic Addition: For two ciphertexts $c^{\prime }=(c_1^{\prime },c_2^{\prime })$ and $c^{\prime \prime }=(c_1^{\prime \prime },c_2^{\prime \prime })$, addition is performed as $c=c^{\prime }+c^{\prime \prime }=(c_1^{\prime }+c_1^{\prime \prime },c_2^{\prime }+c_2^{\prime \prime })$, which corresponds to $m=m^{\prime }+m^{\prime \prime }$.
• Homomorphic Multiplication: For two ciphertexts $c^{\prime }=(c_1^{\prime },c_2^{\prime })$ and $c^{\prime \prime }=(c_1^{\prime \prime },c_2^{\prime \prime })$, multiplication is performed as $c=c^{\prime }\cdot c^{\prime \prime }=(c_1^{\prime }\cdot c_1^{\prime \prime },c_2^{\prime }\cdot c_2^{\prime \prime })$, which corresponds to $m=m^{\prime }\cdot m^{\prime \prime }$.