【密码学PQC】FatSeal: 一种基于格的高效签名算法解读

本篇文章，我们接着来看19年国内算法竞赛当中的算法，「FatSeal」[1]，这个算法采用了NTRU[2]的结构，有意思的一点呢，这个算法没有采用和之前的格的密码体系的采样方法，也就是高斯分布或者中心二项分布，而是采用了均匀分布，相对来说，均匀分布的采样还是好做的。

背景知识

这里，默认读者，理解NTRU的结构，以及格密码的相关知识，不熟悉的读者可以自行查阅一下相关资料，这里不在展开描述了。

算法过程

这里，对于算法过程也分为了3个，和之前的签名一样，分别是密钥生成，签名算法以及验签算法，接下来我们一起来看一下这三个算法，这里，我们用粗体表示多项式，注意，这里不是向量，这个算法的运算在环上。

密钥生成算法

• 输入: 对于参数
• 输出: 公钥、私钥

1. 随机选取，使得在下存在逆元，因为后面要计算的逆，其中，的系数要小于某个范围
2. 计算
3. 最终公钥: ，私钥

签名算法

• 输入: 消息(这里需要转换为多项式系数)，私钥
• 输出: 签名

1. 随机初始化k，长度为
2. 进入循环，满足某个条件，输出签名
1. 随机均匀采样
2. 计算
3. 计算
4. 判断，四个条件，有一个满足，重新执行上面步骤
3. 计算
4. 输出签名

验签算法

• 输入：签名，公钥，消息
• 输出：验签状态

1. 判断，如果成立，验签失败
2. 计算
3. 判断，如果成立，验签成功，否则验签失败

整个算法过程，还是比较容易理解的，那么接下来，我们简单看一下，他的正确性证明。

正确性证明

具体，证明过程来源于资料1，我加了一点我的理解。我们实际上只需要证明

我们已知

因此，我们有

然后，注意到

(密钥生成2)也就是

因此，可以得到

注意到的定义

我们有

这里，我对原文有些疑问，不确定是不是笔误，

这里，按照定义，应该是，但是不影响最后的证明，我不确定，是我理解错了，还是这有问题，然后，我问了下deepseek[3]，得到的结果和我是一致的。

现在AI是真的智能，大概看了下，他的推导问题不大。如果有读者，发现，我这哪有问题，也欢迎和我交流，我们接着来看证明，注意到

因此，我们有

也就是说，加了不影响的区间，这里和ML-DSA里面的思想差不多，好了，到这里，算法就证明完成了。

代码实现

因为原来提供的代码，是只能在Windows下运行，我们这里稍微改动一些，采用cmake来做。

cmake_minimum_required(VERSION 3.10)project(FatSeal C)set(CMAKE_C_STANDARD 11)set(CMAKE_C_STANDARD_REQUIRED ON)find_package(OpenSSL REQUIRED)include_directories(${CMAKE_SOURCE_DIR}/include ${OPENSSL_INCLUDE_DIR})set(SOURCES        byte.c        fips202.c        main.c        ntt.c        poly.c        rand.c        rng.c        sig.c)set(HEADERS        byte.h        fips202.h        ntt.h        params.h        poly.h        rand.h        rng.h        sig.h        sig_api.h)add_executable(${PROJECT_NAME} ${SOURCES} ${HEADERS})target_link_libraries(${PROJECT_NAME} PRIVATE OpenSSL::Crypto)

然后，测试代码也改动一下

#include<stdio.h>#include"params.h"#include"sig_api.h"#include"rand.h"#include"rng.h"intmain(){unsignedchar rd[48];unsignedchar sk[N2 + N_BYTES], pk[N_BYTES], sm[ULEN + RLEN + L_BYTES];unsignedchar m[MLEN];unsignedlonglong pk_size = 0, sk_size = 0, sm_size = 0;  randombytes(rd, 48);  rand_init(rd, 48);  randombytes(m, MLEN);if (sig_keygen(pk, &pk_size, sk, &sk_size)) {printf("Key generation failed!n");return-1;  }printf("Generated key pair:n");printf("Public key size: %llun", pk_size);printf("Secret key size: %llun", sk_size);if (sig_sign(sk, sk_size, m, MLEN, sm, &sm_size)) {printf("Signature generation failed!n");return-1;  }printf("Generated signature, size: %llun", sm_size);int verify_result = sig_verf(pk, pk_size, sm, sm_size, m, MLEN);if (verify_result == 1) {printf("Success: Signature verified correctly!n");  } else {printf("Signature verification failed! (error code: %d)n", verify_result);  }return0;}

可以发现，非常的nice。

总结

本篇文章呢，我们看了一个基于NTRU结构的签名算法，和其他的不同的是，这个没有采用高斯分布或者中心二项分布，还是比较有意思的，至于安全性证明，读者可以参考原始的paper，好了，快乐的时光过的特别快，又到了说再见的时候了，咱们下次再见，~~溜了溜了。

参考资料

1. https://sfjs.cacrnet.org.cn/site/term/list_77_1.html
2. https://www.ntru.org/
3. deepseek.com/