【密码学】门限FALCON签名代码实现

admin 2026-07-14 06:12:35 网络安全文章 来源:ZONE.CI 全球网 0 阅读模式

文章总结: 本文档详细介绍了门限FALCON签名算法的代码实现思路与过程。核心思想是保持验证侧不变,仅修改依赖秘密陷门的原像采样步骤,用更适合MPC的Klein采样器替代原FFO采样器。实现中显式展开基矩阵并采用直观的Gram-Schmidt正交化,一维采样器设计为MPC友好的几何分布包络与拒绝采样。文档强调该实现仅供学习参考,使用玩具参数,不适合生产环境。 综合评分: 86 文章分类: 安全开发,技术标准


cover_image

【密码学】门限 FALCON 签名代码实现

原创

Litt1eQ Litt1eQ

Coder小Q

2026年7月13日 08:30 山东

在小说阅读器读本章

去阅读

【密码学】门限 FALCON 签名代码实现

这个实现仅代表我的理解,仅供学习参考使用,不要直接用于生产环境,请自行评估https://github.com/Litt1eQ/Thresholdizing-FALCON

Bob: Alice,上次你给我讲了门限 FALCON 的论文[1]——第一个“签出来的东西能被原封不动的 FALCON 验证器验证通过”的门限方案。FALCON 是 NIST 第三轮选定进入标准化的签名算法之一[4]。理论我大概懂了。但现在我想换个角度:假设我要自己动手实现它,我该怎么想?从哪儿下第一笔?

Alice: 好问题。比起看”别人改完的结果”,把自己代入”从零设计”的过程,你能学到的更多。我们就按一个实现者的角度,一步步推理下去——每一段代码,都是某个设计决策的自然结果。

Eve: 而且你会发现,真正花心思的不是写代码,而是想清楚哪些该动、哪些不该动。

先把环境和跑法说清楚

Bob: 动手之前,我拿什么跑?

Alice: 这份实现是在 FALCON 官方参考实现上扩展出来的;仓库里的 README.txt 标注基线版本为 2020-09-30,原始 C 实现的主要作者是 Thomas Pornin[2-3]。工具链不复杂,但有几个兼容性边界需要说清楚:

  • 编译器:建议使用 clang 或 gcc(Makefile 默认 clang -O3)。FALCON 基线代码以 C99 为主,但新增代码使用了 unsigned __int128,这是 GCC/Clang 扩展,并非标准 C99 类型。
  • 依赖:不引入第三方库;除标准 C 库外,新增路径使用 expl/floorl/sqrtl/ldexpllong double 和 unsigned __int128。因此,“64 位平台”本身还不够,编译器和 ABI 也必须支持这些类型与函数。
  • 链接:当前 Makefile 的 LIBS 为空;部分 Unix-like 平台仍需把它改成 -lm,FALCON 原始 README 也明确保留了这一可能性。
make            # 生成 test_falcon、test_thfalcon、speed
./test_thfalcon # 一个独立的门限签名小样例

跑起来大致是这样(玩具参数 logn=4、3 方、门限 2):

keygen: logn=4 parties=3 threshold=2
setup: dim=32 precision=73 sigma_i=[1.211672, 1.547202] ccs=[0.783138, 1.000000]
aVOLE: z=x*y mod p verified
quorum 0,1 signature verified: 60 bytes
quorum 1,2 signature verified: 60 bytes

Eve: 留意最后两行——测试程序确实调用未改动的 falcon_verify 验证了这两份 60 字节签名。precision=73 则是这份台架统一采用的保守参数:论文的精度分析给 Falcon-512 推导出 72 位、给 Falcon-1024 推导出 73 位,而论文实验对两组参数统一使用了 73 位[1]。这里的输出只能证明玩具参数下的代码路径跑通,不能单独证明论文里的安全界。

思路一:先找到”唯一需要动的那一步”

Alice: 实现一个复杂系统,第一件事通常是划清边界——哪些需要自己写,哪些可以原封不动地借用。我们回到 GPV 范式的签名流程问自己:这一整条链路里,哪一步是”跟私钥有关、又非线性”的?

Bob: 让我想想……取随机盐、把消息哈希成目标点 ——这些是公开操作;最后检查范数、编码签名——也是公开的。真正碰到陷门 、又不是简单线性运算的,只有中间那一步:用陷门做原像采样(高维离散高斯采样)。

Alice: 对,这个观察是整个实现的出发点。它直接推出两个结论:

  1. 既然只有采样这一步依赖秘密陷门,那么论文把主要 MPC 工作集中在采样器中;哈希、打开采样结果后的签名计算以及验证侧操作都可以公开完成[1]。
  2. 只要采样结果满足同一 NTRU 格上的公钥关系、短向量界和标准编码约定,签名的字节格式与验证逻辑就不必修改。论文进一步用 Rényi 散度分析说明定点 Klein 采样分布与理想分布足够接近,以维持目标安全级别;这里不应把它简化成“与原 FFO 输出严格同分布”[1]。

Eve: 换句话说,实现的思路是:保持验证侧不变,只调整采样这一步。这个原则后面每个决策都会用到。

Bob: 所以我甚至不用碰 vrfy.ccodec.cfft.ckeygen.c 里的核心逻辑?

Alice: 不用。你要写的新东西,是一个”生成签名”的替换件;它对外的输入输出,要和原来那个采样签名函数保持一致,才能顺利接进现有管线。

思路二:采样器怎么选、怎么写

Bob: 那采样这一步,我照搬 FALCON 原来的 FFO 采样器不就行了?

Alice: 这正是第二个关键决策点。你得先问:FFO 适合搬进 MPC 吗?论文的答案是不适合——FFO 是一棵递归的傅里叶采样树,严重依赖双精度浮点,而且学界还没有它的定点精度分析。在 MPC 里,浮点运算的代价很高。

Eve: 于是论文换了一个更老、但结构更规整的采样器:Klein 采样器。它把高维采样拆成 2n 次一维高斯和线性代数;论文的 MPC 协议可用整数和定点运算表达,因此更适合 MPC[1]。不过当前仓库的直观版 sign_dyn_klein 仍大量使用 long double,不能和论文的定点 MPC 实现画等号。

Bob: 那我要怎么把 Klein 写出来?

Alice: 顺着”我要正确、要能和论文逐行对照”这个目标去想,你会做一个很关键的取舍:先不追求快,先追求直白。FALCON 原版用 FFT/LDL 树组织采样所需的数据;这份教学实现则显式展开  基矩阵。矩阵本身需要  空间,而当前朴素 Gram–Schmidt 三重循环需要  时间,并且 sign_dyn_klein 每次签名都会重算。因此它适合玩具参数和代码对照,不是 Falcon-512/1024 的实用替代实现。

Bob: 那第一步就是把陷门  展开成矩阵?

Alice: 对。Klein 需要基矩阵 ,而 FALCON 的密钥是 4 个多项式,它们对应反循环(anticirculant)矩阵。所以你自然会写一个”把多项式旋转着填进矩阵行”的辅助函数:

static void
klein_make_basis(int32_t *basis, const int8_t *f, const int8_t *g,
    const int8_t *F, const int8_t *G, unsigned logn)
{
&nbsp; &nbsp;&nbsp;size_t&nbsp;n = MKN(logn), dim = n <<&nbsp;1, row;
&nbsp; &nbsp;&nbsp;for&nbsp;(row =&nbsp;0; row < n; row ++) {
&nbsp; &nbsp; &nbsp; &nbsp;&nbsp;int32_t&nbsp;*brow = basis + row * dim;
&nbsp; &nbsp; &nbsp; &nbsp; klein_rotated_poly(brow, g, n, row, &nbsp;1,&nbsp;0); &nbsp;&nbsp;// 上半:[ g | -f ]
&nbsp; &nbsp; &nbsp; &nbsp; klein_rotated_poly(brow, f, n, row,&nbsp;-1, n);
&nbsp; &nbsp; &nbsp; &nbsp; brow = basis + (n + row) * dim;
&nbsp; &nbsp; &nbsp; &nbsp; klein_rotated_poly(brow, G, n, row, &nbsp;1,&nbsp;0); &nbsp;&nbsp;// 下半:[ G | -F ]
&nbsp; &nbsp; &nbsp; &nbsp; klein_rotated_poly(brow, F, n, row,&nbsp;-1, n);
&nbsp; &nbsp; }
}

Eve: 这里有个容易踩的坑——klein_rotated_poly 里”下标绕过 n 时要取反号”。这不是笔误,是  这个分圆多项式的负循环(negacyclic)结构。想不到这一点,矩阵就错了。

Alice: 基矩阵准备好后,第二步是 Gram–Schmidt 正交化,得到  和每行范数平方——因为 Klein 要往正交基上投影。当前代码为了直观而用 long double 存这些值;这是工程上的演示选择,不等价于论文证明过的 72/73 位定点表示,也没有给不同平台上的 long double 做安全精度证明。

Bob: 第三步就是采样主循环了?

Alice: 对,而且它基本对应论文 Algorithm 2。你会按  逐维做三件事:投影求中心、采一维高斯、回代更新目标:

for&nbsp;(i = dim; i >&nbsp;0; i --) {
&nbsp; &nbsp; row = i -&nbsp;1;
&nbsp; &nbsp; dot =&nbsp;0.0L; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;// d_i = <t_i, b*_i> / ||b*_i||²
&nbsp; &nbsp;&nbsp;for&nbsp;(col =&nbsp;0; col < dim; col ++)
&nbsp; &nbsp; &nbsp; &nbsp; dot += target[col] * bstar[row * dim + col];
&nbsp; &nbsp; di = dot / norm2[row];
&nbsp; &nbsp; zi = klein_sample_z(&p, di, sigmas[row], sigma_min, sigma_max);
&nbsp; &nbsp;&nbsp;if&nbsp;(zi !=&nbsp;0) &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp;// t_{i-1} = t_i - z_i · b_i
&nbsp; &nbsp; &nbsp; &nbsp;&nbsp;for&nbsp;(col =&nbsp;0; col < dim; col ++)
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; target[col] -= (long&nbsp;double)zi * basis[row * dim + col];
}

Eve: 在论文协议中,di 是私有中心、sigmas[row] = σ/‖b*_i‖ 是私有标准差——这正是第一个技术贡献要解决的“私有中心、私有标准差的一维高斯”[1]。当前单进程代码在重建陷门后以明文 long double 处理它们,所以这里只是在复现采样公式,而不是保护这些私有量。

思路三:一维采样器如何设计成”MPC 友好”

Bob: 那 klein_sample_z 该怎么想?

Alice: 先看 FALCON 原版怎么做一维采样:它用逆变换从半高斯里取基样本,需要 32 次高精度比较。搬进 MPC 太贵。所以论文换了思路——用几何分布做包络,再用拒绝采样纠正形状。

你顺着”什么在 MPC 里便宜”去想,就会得到这个设计:

  1. 令 ,几何分布样本的第  位是独立伯努利变量,概率是公开常数 [1,6]。这里改用 ,是为了避免和 FALCON 模数  混淆。
  2. 接受概率 ,其中  又能按位拆成乘积——这是论文在 Wei 等人的 BerExp 技术上扩展出的 MPC 友好路径[1,5]。

于是采样器自然长这样:

static&nbsp;int
klein_sample_z(prng *p,&nbsp;long&nbsp;double&nbsp;mu,&nbsp;long&nbsp;double&nbsp;sigma,
&nbsp; &nbsp;&nbsp;long&nbsp;double&nbsp;sigma_min,&nbsp;long&nbsp;double&nbsp;sigma_max)
{
&nbsp; &nbsp;&nbsp;longdouble&nbsp;base = floorl(mu), center = mu - base;
&nbsp; &nbsp;&nbsp;for&nbsp;(;;) {
&nbsp; &nbsp; &nbsp; &nbsp;&nbsp;int&nbsp;z0 &nbsp;= klein_geo_tau_half(p); &nbsp; &nbsp; &nbsp; &nbsp;&nbsp;// z0 ~ 几何分布 G(e^{-τ})
&nbsp; &nbsp; &nbsp; &nbsp;&nbsp;int&nbsp;bit = (int)prng_get_u8(p) &&nbsp;1;
&nbsp; &nbsp; &nbsp; &nbsp;&nbsp;int&nbsp;z &nbsp; = ((bit <<&nbsp;1) -&nbsp;1) * z0 + bit; &nbsp;&nbsp;// z = (2b-1)·z0 + b
&nbsp; &nbsp; &nbsp; &nbsp;&nbsp;longdouble&nbsp;dz = (longdouble)z - center;
&nbsp; &nbsp; &nbsp; &nbsp;&nbsp;longdouble&nbsp;x &nbsp;= (dz*dz)/(2*sigma*sigma) &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;// (z-μ)²/2σ²
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;- (longdouble)z0 * KLEIN_TAU &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;// - z0·τ
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;+ (sigma_max*sigma_max*KLEIN_TAU*KLEIN_TAU)/2;
&nbsp; &nbsp; &nbsp; &nbsp;&nbsp;if&nbsp;(klein_bernoulli(p, sigma_min / sigma) &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp;// B(σ_min/σ)
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; && klein_bernoulli(p, expl(-x))) &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;// · B(e^{-x})
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp;return&nbsp;(int)base + z;
&nbsp; &nbsp; }
}

Bob: 这就是论文 Algorithm 3——几何基样本、符号位、变换 z=(2b-1)z0+b、指数 x、两个伯努利接受。

Alice: 而几何采样器就是”逐位做伯努利采样”这个想法的直接实现:

#define&nbsp;KLEIN_GEO_LOGM &nbsp; THFALCON_GEOMETRIC_LOGM &nbsp;&nbsp;// = 5
static&nbsp;int&nbsp;klein_geo_tau_half(prng *p)&nbsp;{
&nbsp; &nbsp;&nbsp;int&nbsp;x =&nbsp;0;
&nbsp; &nbsp;&nbsp;for&nbsp;(i =&nbsp;0; i < KLEIN_GEO_LOGM; i ++) {
&nbsp; &nbsp; &nbsp; &nbsp;&nbsp;long&nbsp;double&nbsp;e &nbsp;= expl(-KLEIN_TAU * (1u&nbsp;<< i)); &nbsp;&nbsp;// τ = 1/2
&nbsp; &nbsp; &nbsp; &nbsp;&nbsp;long&nbsp;double&nbsp;pi = e / (1.0L&nbsp;+ e);
&nbsp; &nbsp; &nbsp; &nbsp;&nbsp;if&nbsp;(klein_bernoulli(p, pi)) x += (int)(1u&nbsp;<< i);
&nbsp; &nbsp; }
&nbsp; &nbsp;&nbsp;return&nbsp;x;
}

Eve: 这里每一个“魔法数字”都有论文依据: 表示用 5 位几何样本,即当前代码中的 (截断界 ); 接近论文数值最优点 0.4843,又能省去一次额外乘法,对应约 0.72 的半高斯包络接受率[1]。这些常数被集中定义在头文件里,便于核对。

Alice: 采样收尾也很直接:四舍五入成 ,然后复用原版的范数检查,不用自己重写:

if&nbsp;(ok && Zf(is_short)(s1tmp, s2tmp, logn)) {
&nbsp; &nbsp;&nbsp;memcpy(sig, s2tmp, n *&nbsp;sizeof&nbsp;*sig); &nbsp; &nbsp; &nbsp;// sig[] 放 s2,契约和原版一致
&nbsp; &nbsp;&nbsp;break;
}

Bob: 我懂了——验证器能接受,是因为 Klein 路径仍构造满足同一公钥方程和范数界的 ,并沿用标准签名编码;这不要求它与 FFO 路径逐比特或严格同分布。至于采样分布是否足够接近理想高斯,则是论文安全分析解决的问题[1]。

思路四:怎么把新采样器接进现有 API 而不重写管线

Alice: 现在你有了一个新的采样签名函数。下一个问题是:怎么让外部调用得到它,同时又不复制一大堆已有代码?

Bob: 我第一反应是复制一份 falcon_sign_dyn,把里面的采样调用换掉……

Alice: 不建议这么做——那样你会有两份几乎一样的哈希/取盐/编码逻辑,以后改一处容易漏另一处。更好的思路是:把已有的签名收尾函数抽出一个”走哪条路”的开关,其余流程不动:

static&nbsp;int
falcon_sign_dyn_finish_inner(...,&nbsp;void&nbsp;*tmp,&nbsp;size_t&nbsp;tmp_len,&nbsp;int&nbsp;use_klein)
{
&nbsp; &nbsp; ...
&nbsp; &nbsp; oldcw = set_fpu_cw(2);
&nbsp; &nbsp;&nbsp;if&nbsp;(use_klein)
&nbsp; &nbsp; &nbsp; &nbsp; Zf(sign_dyn_klein)(sv, rng, f, g, F, G, hm, logn, atmp);
&nbsp; &nbsp;&nbsp;else
&nbsp; &nbsp; &nbsp; &nbsp; Zf(sign_dyn)(sv, rng, f, g, F, G, hm, logn, atmp); &nbsp;&nbsp;// 原版 FFO 路径
&nbsp; &nbsp; set_fpu_cw(oldcw);
&nbsp; &nbsp; ... &nbsp;&nbsp;// 取盐、hash_to_point、压缩编码……全部复用
}

Eve: 关键在于——除了这一个 if,整条管线是共享的。原来的公开入口传 use_klein=0,新增入口传 1vrfy.c 没有为这条路径做特殊处理,测试调用的也是原有 falcon_verify()。因此这里的“未修改验证器”是代码层面可直接核对的事实。

Bob: 这层改动很小,也容易审查,它其实说明:Klein 路径是原版管线里一个可以直接替换的组件。

思路五:门限外壳怎么搭——先想清信任模型

Alice: 到这里,单机版的”Klein 签名”已经通了。现在才轮到真正的门限层。这里最容易犯的错,是一上来就想写”完整的、跨网络的、带恶意安全的 MPC”。

Eve: 而正确的第一步,是先决定你这一版要建模到什么程度。

Bob: 什么意思?

Alice: 论文的协议跑在一个抽象的算术黑盒  之上。你有两个选择:(a) 真的去实现一个分布式、带 MAC、能抵抗恶意方的 MPC 引擎;或者 (b) 先写一个单进程的”理想 ABB 台架”——在一台机器上把协议的行为和数据流忠实地模拟出来,用来验证”逻辑对不对、精度够不够”。

这一版的明智选择是 (b)。所以这份代码从文件头就自称:Ideal-ABB threshold harness。它要的是正确性和可对照论文,不是可部署的保密性。

Bob: 那门限密钥生成怎么办?总不能在一台机器上把完整私钥生成出来吧?

Alice: 这恰恰是你要照着论文的信任模型来决策的地方。论文把 NTRUGen 和密钥分发建模为可信初始化,并把优于通用 MPC 的分布式 NTRU 求解留作开放问题[1]。这份台架据此复用 falcon_keygen_make 生成完整密钥,再额外用 Shamir 多项式逐系数分享:

falcon_keygen_make(rng, logn, sk, sk_len, pubkey, ...); &nbsp;&nbsp;// 公钥就是标准 FALCON 公钥
th_decode_privkey(f, g, F, G, sk, ...);
th_share_poly(party_shares,&nbsp;0, f, ...); &nbsp;&nbsp;// 逐系数 Shamir 分享
th_share_poly(party_shares,&nbsp;1, g, ...); &nbsp;&nbsp;// 域取素数 2^61-1
...

Eve: 顺带澄清一个容易混淆的参数:台架把 Shamir 分享和简化 ABB 算术域设成梅森素数 ,便于用 unsigned __int128 做模乘;另有一个  的宽域仅用于容纳 73 位归一化 GSO 数值。论文实验的算术域参数则是 [1]。因此  是本仓库的演示实现选择,不是论文参数。

Bob: 签名时呢?

Alice: 既然是理想台架,签名的建模就很直接:凑齐法定人数、拉格朗日重建陷门、走前面写好的 Klein 路径:

th_validate_share_set(signer_shares, signer_count, &logn); &nbsp;&nbsp;// 份额一致、≥threshold、编号互异
th_recover_trapdoor(f, g, F, G, signer_shares, signer_count, ...); &nbsp;// Lagrange 插值
Zf(hash_to_point_vartime)(&hd, hm, logn);
Zf(sign_dyn_klein)(sv, rng, f, g, F, G, hm, logn, atmp);

Eve: 这里有一件事要跟读者说清楚,免得误会:这一步是真的把完整陷门重建出来、在本机集中签名。真实的门限 FALCON 里  是不会被任何一方重建的。所以这是”理想功能的行为模拟”——它保证”给对人数就能签、给错就拒、签出来能验证”,但它本身不提供 MPC 的保密性。这条边界值得如实说明。

Alice: 而且你会顺手加上负向的健壮性检查,因为理想功能也要拒绝非法输入。比如重建后用原版 Zf(complete_private) 重算  和重建值比对,不一致就报错;只给一个份额就直接拒签。

思路六:把 MPC 构件逐个”建模”出来

Bob: 那我在 test_thfalcon 里看到的 A2B/B2A、DPF、aVOLE、PCG 是干嘛的?签名主流程里好像没调它们。

Alice: 这是“台架”思路的另一部分:代码给论文涉及的若干对象写了单进程模型和关系测试。不过必须逐项看清它们模拟到了哪一层;这些函数大多会在本进程内打开、重构或直接生成明文值,不能据此声称已经实现了安全 MPC。

于是你会照着论文的构件清单,一个个建模:

  • 认证份额:用集中持有的全局键模拟 SPDZ 风格的算术 MAC 和布尔 MAC,并增加  宽域。它能检测测试中篡改后的打开结果,但不是分布式密钥生成、批量 MAC-check 或主动安全协议。
  • A2B / B2A:函数先在本进程中打开原份额,再按另一种表示重新分享;它验证表示转换结果,不模拟安全转换协议的通信与泄漏性质。
  • 两方 DPF:代码直接展开并分享完整单位向量,再逐点打开校验;没有实现论文引用的紧凑 DPF 密钥、树展开协议或 one-bit leakage 安全模型。
  • aVOLE:代码直接采样明文 、计算  后分别认证。它验证了相关式;论文中“通用认证三元组是三次关系,而固定且已认证的  可把 aVOLE 降为二次关系、使用两方 DPF”的协议洞见仍来自论文,而不是这个辅助函数本身[1]:
check(avole_z == (uint64_t)(((unsigned&nbsp;__int128)avole_x * avole_y)
&nbsp; &nbsp; % THFALCON_ABB_FIELD),&nbsp;"aVOLE relation",&nbsp;-1);
  • aVOLE 的 PCG 外形测试:构造稀疏向量,经一个确定性生成的矩阵压缩后检查 。它复现了“稀疏向量经  扩展”的数据形状,但没有实现或证明 dual-LPN 安全性、紧凑种子扩展、恶意安全 DPF 与论文声称的亚线性通信。

Eve: 所以这些模块更准确的定位是“接口与代数关系的单元测试”。它们可以帮助理解未来真实实现需要哪些对象,但不能直接拼接成论文协议,也不能替代集中重建。

思路七:精度——把”论文的定点分析”落进代码

Bob: 我注意到前面 Klein 采样用的是浮点 long double,但你又反复提”73-bit 定点精度”。这两个怎么统一?

Alice: 这正是最后一个需要严格区分“论文结论”和“代码覆盖范围”的地方。论文用 Rényi 散度证明 Falcon-512 的 72 位、Falcon-1024 的 73 位定点精度足以达到相应目标[1]。这份代码提供了 73 位数值量化、参数范围和 Algorithm 5 公式的测试辅助函数,但实际概率计算与采样仍使用 long doubleexpl 和明文伯努利抽样,因此不是严格定点、布尔共享上的论文采样器。

Eve: 这里还有一个必须如实记录的代码偏差:thfalcon_algorithm5_acceptance_probability_for_test() 在 b=1 时把接受指数里的候选整数写成了 z=z0,但论文 Algorithm 3/5 和主路径 klein_sample_z() 使用的是 z=z0+1;同一个测试采样函数返回样本时也会加 1。也就是说,material-backed 测试路径当前存在一个 b=1 分支的 off-by-one,不应称为 Algorithm 5 的精确复现。标准验证器仍可能接受其输出,因为验证只检查公钥关系、编码与范数,不检查采样分布。

比如下面这个辅助函数按定点位分解 ,用来数值核对 BerExp 应对应的概率:

for&nbsp;(j =&nbsp;0; j < total_bits; j ++)
&nbsp; &nbsp;&nbsp;if&nbsp;(((scaled >> j) &&nbsp;1u) !=&nbsp;0)
&nbsp; &nbsp; &nbsp; &nbsp; p *= expl(-ldexpl(1.0L, (int)j - (int)fractional_bits));

Eve: 这些常数集中在头文件中:FIXED_POINT_PRECISION = 73GEOMETRIC_LOGM = 5、BerExp 位权范围 [-42, 13]TAU = 1/2。其中统一取 73 位对应论文实验参数;论文理论表分别给 Falcon-512 和 Falcon-1024 72/73 位。代码也把在线归一化 GSO 向量的分数位设成 ;玩具参数 logn=4 时就是输出里的  位[1]。

Alice: 还有一条 material-backed 测试路径:先把基矩阵、归一化 GSO 向量、、 编成认证份额;签名时把它们全部打开,在本机用 long double 重算并逐项比对,再用打开后的数值采样。测试说明这些编码物料在 logn=4 下能驱动一条最终被 falcon_verify 接受的路径;考虑到上面的 off-by-one,它既没有精确复现 Algorithm 5,也没有证明秘密物料在签名期间保持隐藏或独立验证论文的分布误差界。

小结:一个实现者的决策链

Bob: 我把这条”从零开始怎么想”的思路串一遍,你看对不对:

  1. 划边界:先想清 GPV 里唯一”私有非线性”的一步是高斯采样,据此决定”只动采样,保持验证侧不变”。
  2. 选采样器:判断 FFO 对 MPC 不友好,换 Klein;教学版显式保存  基矩阵,但朴素 GSO 是 ,只适合小参数。
  3. 设计一维采样:顺着”什么在 MPC 里便宜”,推出”几何分布 + 逐位伯努利 + 拒绝纠正”,并理解每个常数(、)的来历。
  4. 接线:用一个 use_klein 开关复用已有管线,而不是复制。
  5. 定信任模型:门限层只做单进程理想台架;keygen 按可信初始化处理,再用本仓库自选的 Shamir 方案分享。
  6. 建关系测试:为认证份额、DPF、aVOLE、PCG 写简化模型,验证接口和代数关系,但不把它们称作安全协议实现。
  7. 对照精度参数:用 73 位容器和辅助函数检查论文参数及编码;实际签名仍依赖明文 long double,而 material-backed 采样还存在一个 b=1 分支的 off-by-one,并非论文的定点 MPC。

Alice: 对。用一句话概括:验证侧保持不变,围绕采样器搭一条可运行的教学路径;凡是复用原版的地方尽量复用,同时明确区分“标准签名兼容性测试”“论文公式的数值对照”和“真正安全的分布式 MPC 实现”。

Eve: 我再补一句关于边界的话,免得有人拿它去生产:这是一份学术参考 / 正确性台架——门限签名走的是“重建完整陷门后集中签”的理想模拟,不是跨网络、主动安全的 MPC;所谓 DPF、aVOLE、PCG 和 A2B/B2A 是单进程关系模型;定点辅助函数也没有替代浮点采样,material-backed 采样还有上述 off-by-one。示例只覆盖 logn=4,而显式基与朴素 GSO 对标准参数并不实用。比较合适的定位,是把它当成“论文到代码的可运行注解”,而不是可上线的库或论文实现的复现。

Bob: 从“只动采样这一个点”的判断,到几何分布采样器的每一步,再到素域上的 Shamir 份额和 73 位参数容器……我总算明白了:写这样一份实现,花心思的不是写代码本身,而是在每个选择上做对决策。

Alice: 这就是把论文读进代码的乐趣——你写下的每一行,背后都站着一个”为什么这么做”。

本次对话,就这么愉快地结束了。接下来,Alice、Bob 和 Eve 又会遇到什么故事呢?且听下回分解。快乐的时光过得特别快,又到了说再见的时候了,咱们下次再见~

参考文献

[1] GARG R, ESCUDERO D, POLYCHRONIADOU A, et al. Thresholdizing Standardized FALCON Signatures[EB/OL]. IACR Cryptology ePrint Archive, Report 2026/1300, 2026[2026-07-13]. https://eprint.iacr.org/2026/1300.

[2] FALCON PROJECT. FALCON: Fast-Fourier Lattice-based Compact Signatures over NTRU: Specification[EB/OL]. 2020[2026-07-13]. https://falcon-sign.info/falcon.pdf.

[3] FALCON PROJECT. FALCON Reference Implementation[CP/OL]. 2021-11-01[2026-07-13]. https://falcon-sign.info/Falcon-impl-20211101.zip.

[4] ALAGIC G, APON D, COOPER D, et al. Status Report on the Third Round of the NIST Post-Quantum Cryptography Standardization Process: NIST IR 8413-upd1[R]. Gaithersburg: National Institute of Standards and Technology, 2022. https://doi.org/10.6028/NIST.IR.8413-upd1.

[5] WEI C, YU R, FAN Y, et al. Securely Sampling Discrete Gaussian Noise for Multi-Party Differential Privacy[C]//Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security. New York: Association for Computing Machinery, 2023: 2262-2276. https://doi.org/10.1145/3576915.3616641.

[6] DWORK C, KENTHAPADI K, MCSHERRY F, et al. Our Data, Ourselves: Privacy via Distributed Noise Generation[C]//Advances in Cryptology—EUROCRYPT 2006. Berlin, Heidelberg: Springer, 2006: 486-503. https://doi.org/10.1007/11761679_29.


免责声明:

本文所载程序、技术方法仅面向合法合规的安全研究与教学场景,旨在提升网络安全防护能力,具有明确的技术研究属性。

任何单位或个人未经授权,将本文内容用于攻击、破坏等非法用途的,由此引发的全部法律责任、民事赔偿及连带责任,均由行为人独立承担,本站不承担任何连带责任。

本站内容均为技术交流与知识分享目的发布,若存在版权侵权或其他异议,请通过邮件联系处理,具体联系方式可点击页面上方的联系我

本文转载自:Coder小Q Litt1eQ Litt1eQ《【密码学】门限 FALCON 签名代码实现》

评论:0   参与:  0