【PQC密码学】埃奎斯: 一类基于非对称(M)LWE和(M)SIS的密钥封装机制解读

本篇文章呢，我们接着来看国内算法竞赛当中的密码体系[1]，本篇文章呢，我们来看一下AIGIS-PKE算法，这个算法呢，其实和ML-PKE是比较像的，后续我再说，这个和ML-PKE为什么像。

这个名字的由来呢，是埃奎斯(Aigis，希腊古典文字)[2]：希腊神话中宙斯和雅典娜使用的盾牌都叫埃奎斯（其中前者又叫宙斯之盾，后者又叫雅典娜之盾），是希腊神话中唯一能抵抗宙斯“雷霆”攻击的法器，不是我猜的蛤，作者在参考资料里面给出了。(这里英文写法是aegis, 希腊语发音是aigís)，搞一张图看看。

本文不会涉及证明，有兴趣的读者可以参考资料[1]的中的提交。这里，我们只看PKE的方案，对于KEM，只需要添加FO结构就可以了。

知识回顾

这里，我们先来简单的回顾一些regev的加密方案。

密钥生成算法

1. 随机选择矩阵
2. 计算
3. 其中公钥私钥

加密算法

这个加密算法，只能加密一个比特，因此对于明文消息，我们有

1. 计算
2. 然后计算
3. 最终输出密文

解密算法

我们只需要计算

1. 然后把做一个round，放到0和1上

这里，我们还是，简单的回顾一下round函数吧，虽然说，Kyber也已经讲过了，稍微水一点字数，哈哈哈。

Round函数

这个函数的作用呢，是对于其中q是一个素数，把他映射到之上。我们知道当中的元素，可以是在之内，也可以是在之内的，因此具体的round函数定义如下

来看一个例子，这里，我们令，这是Aigis里面在参数I和II下，选用的q，对应的round函数如下

然后，我们再来回顾一下Kyber-PKE的方案，这里还是简单的来回顾一下，这里我们省略NTT的步骤。

密钥生成

1. 选择一个种子
2. 计算其中
3. 选择
4. 选择
5. 计算

最终公钥是，私钥是

加密算法

这里，我们的消息，然后我们按照如下的方式加密

1. 利用还原矩阵
2. 采样
3. 采样
4. 采样
5. 计算
6. 计算
7. 最终，压缩输出，

解密算法

解密也比较简单，

1. 还原
2. 计算

AIGIS算法

好了，接下来，我们就来看一下，AIGIS的算法结构。

参数选择

具体的参数选择，文档和在PQMagic当中开源的实现的选择的参数不一样，可能他们后续又更新过算法，这里，我们按照开源的代码的参数来描述，而不是按照文档中的来，再看文档和代码的时候，要注意这块的差异，还有就是，这里给出的PRNG在文档中默认是AES，代码实现当中默认实现是SM3，并且去掉了AES的PRNG。

密钥生成

• 输入: 安全参数
• 输出: 公钥和私钥

1. 生成一个种子: 用于后续扩展矩阵和生成私钥
2. ，这里采用哈希函数扩展两个“新种子”
3. 生成矩阵，注意: 这里直接用NTT表示
4. 采样，然后得到对应的NTT表示
5. 采样注意，这里和的分布不同
6. 计算
7. 输出公钥: ，私钥: ，注意，真实实现进行了模切换和编码

加密算法

• 输入: 公钥, 明文消息m
• 输出: 密文c

1. 还原
2. 采样，然后得到对应的NTT表示
3. 采样注意，这里和的分布不同
4. 采样
5. 计算
6. 计算，注意多项式表示
7. 输出密文

解密算法

• 输入: 密文，私钥
• 输出: 明文m

好了，这里实际上就解密完成了。到这里，算法基本上就讲完了，然后对比上面之前回顾的Kyber-PKE的方案，可以发现，他们两个结构是非常相似的。

总结

本文呢，来看了一下AIGIS-ENC算法的过程，总体来说，这个如果之前对于Kyber比较熟悉的话，理解这个应该并不难，这里的核心在于，在kyber里面，除了参数I，其他的两个他们都是相等的，而对于这个算法来说，他们都是不同的，对于他们的安全性证明，详细的可以看一下原始的资料，这里就不描述了，只给出一个结论。

而对于代码的实现，读者参考[4]里面的实现吧，注意这个参数，和原始的Paper是有差异的就可以了，好了，快乐的时光过得特别快，又到了说再见的时候了，咱们下次再见。

参考资料

1. https://sfjs.cacrnet.org.cn/site/term/list_77_1.html
2. https://en.wikipedia.org/wiki/Aegis
3. Oded Regev. On lattices, learning with errors, random linear codes, and cryptography.
4. https://pqcrypto.dev/