How does Kyber Encryption Work

Kyber 的私钥 $\mathbf{s}$ 由一些随机多项式组成，且要求它们的系数值很小。关于要求系数值很小的原因可参见节 2.3.1 。

对于 Baby Kyber 来说，假设私钥 $\mathbf{s}$ 为两个多项式 $$\mathbf{s}=\left(\begin{array}{c}-x^3-x^2+x\\ -x^3-x\end{array}\right)$$ 它们是随机产生的多项式系数很小的多项式。注： “系数很小”的意思是“和 $0$ 或者系数模数 $q=17$ 比较接近”。 上面的私钥 $\mathbf{s}$ 中多次出来的 $-1$ 系数做个模 $17$ 运算后就是 $16$ ，尽管和 $0$ 比不是很接近，但它和模数 $17$ 很接近，所以也符合“系数很小”的要求。

Kyber 的公钥由两部分组成：随机矩阵多项式 $\mathbf{A}$ 和另一个矩阵 $\mathbf{t}$ 。 在 Baby Kyber 例子中，将使用 $$\mathbf{A}=\left(\begin{array}{cc}6x^3+16x^2+16x+11& 9x^3+4x^2+6x+3\\ 5x^3+3x^2+10x+1& 6x^3+x^2+9x+15\end{array}\right)$$ 前面提到过 Bady Kyber 中，对多项式的系数进行模数 $q=17$ 计算，对多项式本身进行模 $f=x^4+1$ 多项式运算，所以 $\mathbf{A}$ 的多项式系数都小于 $17$ ，且多项式次数都小于 $4$ 。

Kyber 公钥中另一部分 $\mathbf{t}$ 的计算公式为 $$\mathbf{t}\triangleq \mathbf{A}\mathbf{s}+\mathbf{e}$$ 其中 $\mathbf{e}$ 是错误矩阵，要求是随机产生，且多项式的系数比较小。在 Baby Kyber 例子中，将使用 $$\mathbf{e}=\left(\begin{array}{c}{x}^2\\ x^2-x\end{array}\right)$$

从而，我们可以计算出公钥 $\mathbf{t}$ 为 $$\begin{array}{rl}\mathbf{t}& \triangleq \mathbf{A}\mathbf{s}+\mathbf{e}\\ & =\left(\begin{array}{c}16x^3+15x^2+7\\ 10x^3+12x^2+11x+6\end{array}\right)\end{array}$$

对于非对称加密系统来说，使用公钥对消息进行加密，使用私钥对消息进行解密。

Kyber 加密时，会使用 2 个一次一用的系数比较小的随机矩阵 $\mathbf{r},{\mathbf{e}}_{\mathbf{1}}$ ，和 1 个一次一用的系数比较小的随机多项式 $e_2$ 。 在 Baby Kyber 例子中，将使用 $$\begin{array}{rl}\mathbf{r}& =\left(\begin{array}{c}-x^3+x^2\\ x^3+x^2-1\end{array}\right)\\ {\mathbf{e}}_{\mathbf{1}}& =\left(\begin{array}{c}{x}^2+x\\ x^2\end{array}\right)\\ e_2& =-x^3-x^2\end{array}$$

在加密消息前，我们需要先把消息编码为某个多项式。 我们可以使用消息的二进制表达作为多项式的系数。比如我们想加密数字 $11$ ，它的二进制表达为 $(1011{)}_2$ ，所以待加密的数字 $11$ 可以编码为多项式 $m_b=1x^3+0x^2+1x^1+1x^0=x^3+x+1$

在加密前，还需要把 $m_b$ 的系数放大，这是通过乘以 $\lceil \frac{q}{2}\rfloor$ 来实现的（为什么在加密前要把 $m_b$ 放大呢？其原因可参考节 2.3.1）。其中记号 $\lceil x\rfloor$ 表示最接近实数 $x$ 的整数，如果实数 $x$ 恰好位于两个连续整数中间，则上向取整，比如 $\lceil 1.4\rfloor =1,\lceil 1.5\rfloor =2$ 。在我们的例子中，有 $\lceil \frac{q}{2}\rfloor =\lceil \frac{17}{2}\rfloor =\lceil 8.5\rfloor =9$ 。

也就是说待加密的数字 $11$ 最终编码为了 $$m\triangleq \lceil \frac{q}{2}\rfloor \cdot m_b=9x^3+9x+9$$

使用公钥 $\mathbf{A},\mathbf{t}$ 对消息 $m$ 进行加密，其密文由两个部分组成 $(\mathbf{u},v)$ ，它的定义为 $$\begin{array}{rl}\mathbf{u}& \triangleq {\mathbf{A}}^{\mathsf{T}}\mathbf{r}+{\mathbf{e}}_{\mathbf{1}}\\ v& \triangleq {\mathbf{t}}^{\mathsf{T}}\mathbf{r}+e_2+m\end{array}$$

代入各个值，我们可以计算出数字 $11$ 的密文的两个部分 $(\mathbf{u},v)$ 分别为 $$\begin{array}{rl}\mathbf{u}& =\left(\begin{array}{c}11x^3+11x^2+10x+3\\ 4x^3+4x^2+13x+11\end{array}\right)\\ v& =8x^3+6x^2+9x+16\end{array}$$

使用私钥 $\mathbf{s}$ 可对密文 $(\mathbf{u},v)$ 进行解密，解密步骤如下。

第一步，使用下面公式计算出带有噪声的解密结果（noisy result） $$m_{\text{noisy}}\triangleq v-{\mathbf{s}}^{\mathsf{T}}\mathbf{u}$$ 代入私钥和密文的具体值，可得 $$m_{\text{noisy}}=8x^3+{14}^2+8x+6$$

第二步，检查 $m_n$ 的各个系数，看它是更接近于 $\lceil \frac{q}{2}\rfloor =9$ ，还是更接近于 $0$ （或者 $q=17$ ）。如果更接近于 $\lceil \frac{q}{2}\rfloor$ ，则把系数改为 $\lceil \frac{q}{2}\rfloor$ ；如果更接近于 $0$ （或者 $q=17$ ），则把系数改为 $0$ 。下面依次检测一下 $m_n$ 的各个系数。

• 系数 $8$ 更接近于 $9$ ，所以改为 $9$
  
• 系数 $14$ 更接近于 $0$ （或者 $q=17$ ），所以改为 $0$
  
• 系数 $8$ 更接近于 $9$ ，所以改为 $9$
  
• 系数 $6$ 更接近于 $9$ ，所以改为 $9$
  

所以，得到解密多项式 $9x^3+0x^2+9x+9$ ，可以发现它就是加密前的多项式。

第三步，把多项式的缩小 $\lceil \frac{q}{2}\rfloor =9$ 倍，就得到原始加密数据的二进制表达 $$m_b=\frac{1}{\lceil \frac{q}{2}\rfloor }(9x^3+0x^2+9x+9)=x^3+0x^2+x+1$$
所以，我们得到二进制数据 $(1011{)}_2$ ，换算为十进制就是 $11$ ，它就是原始加密数据。

下面代码演示了前面介绍的 Baby Kyber 例子。

# polynomials/modules from: https://github.com/GiacomoPope/kyber-py

from polynomials import *
from modules import *

q = 17
n = 4  # x^4 + 1
R = PolynomialRing(q, n)
M = Module(R)

s0 = R([0,1,-1,-1])
s1 = R([0,-1,0,-1])
s = M([s0,s1]).transpose()

A00 = R([11,16,16,6])
A01 = R([3,6,4,9])
A10 = R([1,10,3,5])
A11 = R([15,9,1,6])
A = M([[A00, A01],[A10, A11]])

e0 = R([0,0,1,0])
e1 = R([0,-1,1,0])
e = M([e0,e1]).transpose()

t = A @ s + e

print("s:",s)
print("A:",A)
print("e:",e)
print("t:",t)

r0 = R([0,0,1,-1])
r1 = R([-1,0,1,1])
r = M([r0, r1]).transpose()
print("r:",r)

e1_0 = R([0,1,1,0])
e1_1 = R([0,0,1,0])
e1 = M([e1_0, e1_1]).transpose()
print("e1:",e1)

e2 = M([R([0,0,-1,-1])])
print("e2:",e2)

m = M([R([9,9,0,9])])

# Encryption
u = A.transpose() @ r + e1
v = t.transpose() @ r + e2 + m
print("u:", u)
print("v:", v)

# Decryption
m_noisy = v -  s.transpose() @ u
print("m_noisy:", m_noisy)         # m_noisy: [6 + 8*x + 14*x^2 + 8*x^3]