BFV

BFV (Brakerski-Fan-Vercauteren) Scheme

The BFV scheme is similar to the BGV scheme but is based on the Learning with Errors (LWE) problem. It was proposed by Fan and Vercauteren as an improvement to the BGV scheme.

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 composed of $(a,b=-a\cdot s+e)$.
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=(a\cdot r+e_1,b\cdot r+e_2+\Delta \cdot m)$ is generated.
4. Decryption: To decrypt the ciphertext $c$, compute $m^{\prime }=\lceil \frac{c_2+s\cdot c_1}{\Delta }\rfloor (\mathrm{mod}t)$. Here, $\Delta$ is the scaling factor.

Homomorphic Operations

The BFV scheme also supports homomorphism for addition and multiplication.

• Homomorphic Addition: $c=c^{\prime }+c^{\prime \prime }=(c_1^{\prime }+c_1^{\prime \prime },c_2^{\prime }+c_2^{\prime \prime })$
• Homomorphic Multiplication: $c=c^{\prime }\cdot c^{\prime \prime }$