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.

Let’s analyze whether the encoding scheme in Summary D-2.1 preserves isomorphism: homomorphic and bijective.

Homomorphism: Let’s denote the above encoding scheme as the mapping $\sigma$. Suppose we have two integers $m_1,m_2$ as follows:

$m_1=\underset{i=0}{\overset{n-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}(b_{1,i}\cdot 2^i)$, $m_2=\underset{i=0}{\overset{n-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}(b_{2,i}\cdot 2^i)$

Then,

$\sigma (m_1+m_2)=\sigma \left(\underset{i=0}{\overset{n-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}(b_{1,i}\cdot 2^i)+\sum _{i=0}^{n-1}(b_{2,i}\cdot 2^i)\right)$

$=\sigma \left(\underset{i=0}{\overset{n-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}(b_{1,i}+b_{2,i})\cdot 2^i\right)$

$=\underset{i=0}{\overset{n-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}(b_{1,i}+b_{2,i})\cdot X^i$

$=\underset{i=0}{\overset{n-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{b}_{1,i}\cdot X^i+\sum _{i=0}^{n-1}{b}_{2,i}\cdot X^i$

$=\sigma \left(\underset{i=0}{\overset{n-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}(b_{1,i}\cdot 2^i)\right)+\sigma \left(\underset{i=0}{\overset{n-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}(b_{2,i}\cdot 2^i)\right)$

$=\sigma (m_1)+\sigma (m_2)$

$\sigma (m_1\cdot m_2)=\sigma \left(\underset{i=0}{\overset{n-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}(b_{1,i}\cdot 2^i)\cdot \sum _{i=0}^{n-1}(b_{2,i}\cdot 2^i)\right)$

$=\sigma \left(\underset{i=0}{\overset{2\cdot (n-1)}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}\sum _{j=0}^i(b_{1,j}\cdot b_{2,i-1})\cdot 2^i\right)$

$=\underset{i=0}{\overset{2\cdot (n-1)}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}\sum _{j=0}^i(b_{1,j}\cdot b_{2,i-1})\cdot X^i$

$=\underset{i=0}{\overset{n-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{b}_{1,i}\cdot X^i\cdot \sum _{i=0}^{n-1}{b}_{2,i}\cdot X^i$

$=\sigma \left(\underset{i=0}{\overset{n-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}(b_{1,i}\cdot 2^i)\right)\cdot \sigma \left(\underset{i=0}{\overset{n-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}(b_{2,i}\cdot 2^i)\right)$

$=\sigma (m_1)\cdot \sigma (m_2)$

Since $\sigma (m_1+m_2)=\sigma (m_1)+\sigma (m_2)$ and $\sigma (m_1\cdot m_2)=\sigma (m_1)\cdot \sigma (m_2)$, the encoding scheme in Summary D-2.1 is homomorphic.

One-to-Many Mappings: This encoding scheme preserves one-to-many mappings between the input integers and the encoded polynomials, because there is more than 1 way to encode the same input integer $m$, which can be encoded as different polynomials. For example, suppose that we have the following two input integers and their summation: $m_1=0111$, $m_2=0010$, $m_{1+2}=m_1+m_2=1001$. Then, their encoded polynomials are as follows:

$M_1(X)=0X^3+1X^2+1X+1$

$M_2(X)=0X^3+0X^2+1X+0$

$M_{1+2}(X)=0X^3+1X^2+2X+1$

$$ However, the following polynomial is also mapped to $m_{1+2}=1001$:

$M_3(X)=1X^3+0X^2+0X^1+1$

That being said, both polynomials are mapped to the same $m_{1+2}$ (i.e., $1001$) as follows:

$M_{1+2}(2)=4+4+1=9$

$M_3(2)=8+1=9$

Although the encoding scheme in Summary D-2.1 is not bijective but only one-to-many mappings, it preserves homomorphism and the decoded number decomposition sums to the same original integer. Therefore, this encoding scheme can be validly used for fully homomorphic encryption.