【密码学PQC】SCloud 基于LWE的加密与密钥封装算法

我们接着来看19年提交的算法[1]，这个算法和我们之前看过的其他算法的不同点呢，是没有采用具有代数结构的格，从效率以及方案设计来看，代数结构越好，性能以及可以设计的算法应用也就越多，当然，由于良好的结构，被攻击的层面也会越大。

目前来看，具有代数结构的格，还是比较稳的，毕竟NIST发布的两个基于格设计的算法都是带着代数结构的，不过不影响我们来看这个算法，至于基础知识，我在这里，就不过多描述了。

这个算法和LAC一样，也采用的纠错码的方案，只不过，这个采用了格雷码的纠错方案，对于编码理论的细节，我们不展开来描述。

前置知识

这里，我们先来简单的回顾一些regev的加密方案，还是如果可以理解这个方案，后面再来看，新算法会容易不少。

密钥生成算法

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

加密算法

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

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

解密算法

我们只需要计算

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

算法内容

还是老样子，里面包括了3个算法，分别是密钥生成、加密算法以及解密算法，这里我们还是只看PKE，而对于KEM，这里也是直接利用了FO的结构，注意，这里里面采用的哈希函数用了SM3。

密钥生成算法

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

1. 随机选择种子
2. 利用种子，生成随机矩阵
3. 生成私钥和错误矩阵，这里分布采用了离散高斯分布
4. 计算
5. 输出公钥()以及公钥

加密算法

• 输入: 消息，公钥
• 输出: 密文

1. 利用种子还原矩阵
2. 生成，以及
3. 计算以及
4. 返回密文

解密算法

• 输入: 密文，私钥
• 输出: 消息

1. 计算
2. 返回消息

我们简单的理解一下，这个算法的正确性，具体细节，可以参考原始的资料。

因为这个大概率会比较小，可以理解为regev里面的那个错误，regev使用了round函数来拿到原始的消息，这里，可以吧round函数看做是解码函数。因为，满足之前的高斯采样，因此，利用纠错码，可以把错误给纠正回去。

代码实现

这里，我们可以直接参考提交的代码，这里，还是老样子，简单的适配一下，可以在Mac运行。

cmake_minimum_required(VERSION 3.29)project(SCloud)set(CMAKE_CXX_STANDARD 20)add_executable(SCloud main.cpp AESGCM.cpp aes/aes.c)

这个比较方便，他的大部分代码，都在一个文件当中，因此，简单做一下引入就可以了。

然后，有些过程的输出，这里，不影响算法正确性，我们直接注释，因为我这没有sprintf_s这个函数。

然后，这里，也要注释掉。

来看一下，运行的效果，速度，个人感觉比较慢（仅代表个人PC电脑结果）。

总结

本篇文章呢，我们来看了一个新的算法，这个算法的特点，可以总结两个关键词，个人看法，无代数结构+纠错码，之前看过的LAC是基于R-LWE+纠错码，从代码运行来看，这个的速度还是比较慢的，实际体验，也可能我电脑性能不太够，好了，快乐的时光过的特别快，又到了说再见的时候了，咱们下次再见。

参考资料

1. https://sfjs.cacrnet.org.cn/site/term/list_77_1.html
2. https://eprint.iacr.org/2020/095