Single Value Encoding

D-2.1 Single Value Encoding

BFV supports two encoding schemes: single value encoding and batch encoding. In this subsection, we will explain the single value encoding scheme.

$⟨$ Summary D-2.1 $⟩$ BFV Encoding

Input Integer: Decompose the input integer $m \in ℤ_{\geq 0}$ (i.e., 0 or any positive integer) as follows:

$m = b_{n - 1} \cdot 2^{n - 1} + b_{n - 2} \cdot 2^{n - 2} + \dots + b_{1} \cdot 2^{1} + b_{0} \cdot 2^{0}$ , where each $b_{i} \in {0, 1}$

Encoded Polynomial: $M (X) = b_{0} + b_{1} X + b_{2} X^{2} + \dots + b_{n - 1} X^{n - 1} \in R_{⟨ n, t ⟩}$

Decoding: $M (X = 2) = m$

Let’s analyze whether the encoding scheme in Summary D-2.1 ensures correct decoding after addition and multiplication. This is equivalent to showing that:

$Decode (σ (m_{1}) + σ (m_{2})) = m_{1} + m_{2}$ $▹$ where $σ$ is the encoding function

$Decode (σ (m_{1}) \cdot σ (m_{2})) = m_{1} \cdot m_{2}$

Let $σ (m_{1}) = M_{1} (X)$ and $σ (m_{2}) = M_{2} (X)$ . Then,

$Decode (σ (m_{1}) + σ (m_{2})) = Decode (M_{1} (X) + M_{2} (X))$

$= Decode (M_{1 + 2} (X))$ $▹$ where $M_{1 + 2} (X) = M_{1} (X) + M_{2} (X)$

$= M_{1 + 2} (2)$ $▹$ since decoding is evaluating the polynomial at $X = 2$

$= M_{1} (2) + M_{2} (2)$ $▹$ since evaluating $M_{1 + 2} (X)$ at $X = 2$ is computationally the same as splitting $M_{1 + 2} (X)$ into $M_{1} (X)$ and $M_{2} (X)$ , evaluating $M_{1} (2)$ and $M_{2} (2)$ and summing them

Similarly, the decoding preserves correctness over multiplication as well:

$Decode (σ (m_{1}) \cdot σ (m_{2})) = Decode (M_{1} (X) \cdot M_{2} (X))$

$= Decode (M_{1 \cdot 2} (X))$ $▹$ where $M_{1 \cdot 2} (X) = M_{1} (X) \cdot M_{2} (X)$

$= M_{1 \cdot 2} (2)$ $▹$ since decoding is evaluating the polynomial at $X = 2$

$= M_{1} (2) \cdot M_{2} (2)$ $▹$ since evaluating $M_{1 \cdot 2} (X)$ at $X = 2$ is computationally the same as splitting $M_{1 \cdot 2} (X)$ into $M_{1} (X)$ and $M_{2} (X)$ , evaluating $M_{1} (2)$ and $M_{2} (2)$ and multiplying them

Therefore, the single value encoding scheme preserves the correctness of decoding after addition and multiplication.

The encoding scheme in Summary D-2.1 can be validly used for fully homomorphic encryption only if the multiplication of the encoded polynomials do not exceed the polynomial ring’s degree $n$ , because once the degree gets reduced due to an overflow, the evaluated values of polynomials lose consistency. Also, the coefficients of polynomials should not wrap modulo $t$ after additions or multiplications. Due to these constraints, the single value encoding is not a good choice for fully homomorphic encryption. Also, the single value encoding is computationally inefficient, because each polynomial can encode only a single value even if it holds $n$ coefficients.

[parent][next]