当前位置：首页 > news >正文

Kyber原理解析

news 2025/7/13 6:09:12

Kyber是一种IND-CCA2安全的密钥封装机制。Kyber的安全性基于在模格（MLWE问题）中解决LWE问题的难度。Kyber的构造采⽤两阶段⽅法：⾸先介绍⼀种⽤来加密固定32字节⻓度的消息原⽂的IND-CPA安全性的公钥加密⽅案，我们称之为 CPAPKE， CPAPKE由密钥生成（ CPAPKE.KeyGen）、加密（ CPAPKE.Encrypt）、解密（ CPAPKE.Decrypt）三个算法组成。然后，我们使⽤略微调整的Fujisaki-Okamoto（FO）变换来构建IND-CCA2安全性的CCAKEM，CCAKEM方案由密钥生成（CCAKEM.KeyGen）、封装（CCAKEM.Encaps）、解封装（CCAKEM.Decaps）三个算法组成。

由CPAPKE通过FO变换转换成CCAKEM并不复杂，本文我们主要举例解释一下CPAPKE的三个算法，Kyber出于安全性考虑，系统参数都较大，这里我们只为了简要解释原理，因此采用了压缩版的参数。假设q=17, 多项式模数 $f=x^4+1$ 。

1.密钥对生成

添加图片注释，不超过 140 字（可选）

对于密钥对生成阶段，我们会获得密钥对（pk,sk）,其中pk=t=As+e, sk=s。A，s, e都是随机生成的，我们假设其取值如图上所示，最终计算获得： $t = (-15x^6-26x^5-41x^4-18x^3+8x, -11x^6-9x^5-23x^4-24x^3+x^2-15x)$

由于多项式系数取值模数 $f=x^4+1$ ,可以简单理解为 $x^4=-1$ ,对t进行转换：

$t=(-15x^6-26x^5-41x^4-18x^3+8x,-11x^6-9x^5-23x^4-24x^3+x^2-15x)=(15x^2+26x+41-18x^3+8x,11x^2+9x+23-24x^3+x^2-15x)=(-18x^3+15x^2+34x+41,-24x^3+12x^2-6x+23)$

（将 $x^4$ 转换为-1）

又由于q=17, 我们进一步对系数取模得到：

$t=(16x^3+15x^2+7,10x^3+12x^2+11x+6)$

综上，密钥生成阶段我们生成了密钥对 $pk=(16x^3+15x^2+7,10x^3+12x^2+11x+6),sk=(-x^3-x^2+x,-x^3-x)$

2.密钥封装

添加图片注释，不超过 140 字（可选）

密钥封装阶段我们从公钥中恢复了种子 ρ ，从而恢复出密钥对生成阶段的矩阵A，又随机生成了 r, $e_1$ , $e_2$ , 并假设我们的输入 $message=(11)_{10}=(1011)_2$ .转化为多项式系数后 $m_b=x^3+x+1$

添加图片注释，不超过 140 字（可选）

$Decompressq(m_b,1)=q/2 \ast m_b=9m_b=9x^3+9x+9$ ,

再结合之前生成的，A，r, $e_1$ , $e_2$ , 计算 $u=A^Tr+e_1=(11x^3+11x^2+10x+3,4x^3+4x^2+13x+11)$

$v=t^Tr+e_2+Decompress_q(m_b,1)=7x^3+6x^2+8x+15$

3.密钥解封装

添加图片注释，不超过 140 字（可选）

根据密钥封装阶段的u,v和密钥对生成阶段的sk, 我们计算出密钥解封装阶段的 $m_n=8x^3+14x^2+8x+6$ ,最后我们将 $m_n$ 的多项式系数与 q/2 ， 0 对比并取round，获取了round后的多项式 $m_{round}=9x^3+9x+9$ ,最终我们计算 $m_b=1/9\ast m_{round}=x^3+x+1=1x^3+0x^2+1x+1$ ,取系数得 $message=(1011)_2=(11)_{10}$ .