一篇基于格的无证书线性同态签名方案的学术报告

一、 研究团队与发表信息

本研究的论文题为“A Certificateless Linearly Homomorphic Signature Scheme Based on Lattice for Network Coding”，作者为宋寿东 (Songshou Dong)、姚延青 (Yanqing Yao，通讯作者)、周伊华 (Yihua Zhou) 和杨玉光 (Yuguang Yang)。作者团队来自北京航空航天大学（软件环境国家重点实验室、航空航天网络信息安全工业和信息化部重点实验室、网络空间安全学院）和北京工业大学（信息技术学院、可信计算北京市重点实验室），同时部分工作也依托于国家密码管理局（密码科学技术国家重点实验室）。

该研究已于2024年5月10日在 *The Computer Journal*（第67卷，第2739-2748页）上在线先行发表（Advance Access），其最终接收日期为2024年4月12日。这是一份由英国计算机学会（The British Computer Society）主办，牛津大学出版社出版的学术期刊。

二、 学术背景与研究目标

本研究属于密码学领域，特别是后量子密码学（Post-Quantum Cryptography, PQC）和同态签名（Homomorphic Signature）的子领域。研究的核心驱动力是解决网络编码（Network Coding）技术在实际应用中面临的安全挑战。

网络编码允许网络中的中间节点对接收到的数据包进行编码组合后再转发，这已被证明能提升网络吞吐量和鲁棒性。然而，这种特性也使其极易遭受污染攻击（Pollution Attack）：一个被污染的数据包经过中间节点编码后，会污染所有与其组合的数据包，导致目标节点无法正确解码并浪费网络资源。

线性同态签名（Linearly Homomorphic Signature）是防御污染攻击的关键密码学原语。它允许源节点对数据向量进行签名，中间节点可以在不接触私钥的情况下，对收到的有效签名进行同态运算（线性组合），生成新数据向量的有效签名。目标节点则可以验证这些签名，从而过滤掉被污染的或无效的数据。

然而，现有的同态签名方案存在几个关键缺陷： 1. 密钥托管（Key Escrow）问题：尤其是在基于身份的签名方案中，密钥生成中心（Key Generation Center, KGC）知晓所有用户的私钥，存在单点失效和滥用的风险。 2. 无法抵抗恶意的KGC：KGC有能力伪造任何用户的签名。 3. 后量子时代不安全：大多数现有方案基于大整数分解、离散对数或双线性配对问题，这些难题在量子计算机（如Shor算法）面前是脆弱的。 4. 签名效率与存储开销问题：部分方案效率较低或需要管理复杂的公钥证书。

因此，本研究旨在设计并实现一个能够抵御量子计算攻击、同时避免密钥托管和恶意KGC威胁的、高效的无证书线性同态签名方案。具体而言，研究目标包括：利用格（Lattice）密码构造方案以实现后量子安全；采用无证书（Certificateless）密码体制来消除密钥托管并抵抗恶意KGC；运用双峰高斯分布（Bimodal Gaussian Distribution）等技术优化方案的安全性和效率；最终在随机预言机模型（Random Oracle Model, ROM）下形式化地证明方案的安全性。

三、 详细的工作流程与方案构造

本研究提出的是一个完整的密码方案，其工作流程主要包含五个算法（Algorithms），构成了一个完整的无证书线性同态签名系统。研究“对象”是方案本身及其安全性，而非传统的实验样本。其核心工作流程如下：

1. 系统建立（Setup） * 过程：输入安全参数 *n*。算法运行格上的陷门生成算法 TrapGen(n, m, q)。该算法会生成一个均匀随机的矩阵 A ∈ Z_q^{n×m} 作为主公钥，同时生成一个对应的短基（陷门）T ∈ Z^{m×m} 作为主私钥。这里 q 是一个大素数，m 的维度足够大（≥ 5n log q）。 * 方法与工具：TrapGen 是格密码学中的标准算法，用于生成带有陷门的格。这并非本研究新发明，但它是构建后续方案的基础。此外，方案还设定两个抗碰撞哈希函数 H1 和 *H2*，以及一系列高斯分布参数（如标准差σ）。这些参数确保了后续抽样操作的正确性和安全性。

2. 密钥生成（KeyGen） 这是本方案实现“无证书”特性的核心步骤，分为两个阶段，形成了一个循环依赖（Circular Dependency） 的巧妙结构，以抵御中间人攻击等威胁。 * 部分私钥提取： * 签名者（身份为 *ID*）首先随机选择一个范数有界的矩阵 C_ID，计算其部分公钥 P_ID = A · C_ID mod q，并将 (ID, *P_ID) 发送给KGC。 * KGC计算 F_ID = H1(ID, P_ID)，然后利用其主私钥陷门 T，运行格上预像抽样算法 SampleMat(A, T, σ, F_ID)。该算法能生成一个短向量（矩阵）D_ID，满足 A · D_ID = F_ID mod q。D_ID 即为KGC为签名者生成的部分私钥，被安全地发送给签名者。 * 用户密钥生成： * 签名者收到 D_ID 后，验证等式 A · D_ID = H1(ID, P_ID) 是否成立。 * 若成立，签名者计算其完整的私钥 S_ID = C_ID + D_ID。其公钥对为 (A, P_ID)。值得注意的是，完整的私钥 S_ID 由用户自己选择的 C_ID 和KGC提供的 D_ID 共同构成，任何一方都无法单独获取或推知完整的 S_ID。这个过程如图4所示，清晰地展示了KGC和用户之间的交互与依赖关系。

3. 签名（Signature） 对于属于子空间 V 的一个基向量 v_i 及其标签 *τ*，签名者执行以下操作（对同一 *τ*，步骤(1)(2)仅首次执行）： * (1-2) 承诺：从高斯分布 D_σ^m 中随机采样向量 y，计算哈希值 α = H2(A·y mod q, τ)。这里的 A·y 作为一个承诺（Commitment）。 * (3) 计算消息相关值：计算内积 *h_i = <α, v_i> mod 2*，并将其扩展为一个向量 h_i。 * (4) 生成签名原型：随机选择一个比特 *b_i ∈ {0, 1}*，计算 z_i = (-1)^{b_i} * (q/2) * S_ID * h_i + y mod q。这一步引入了双峰高斯分布的思想。 * (5) 拒绝采样：以概率 *min(1, D_σ^m(zi) / [M * (0.5*D{(q/2)S_ID h_i, σ}^m(zi) + 0.5*D{-(q/2)S_ID h_i, σ}^m(z_i))])* 输出签名 *sig = (z_i, h_i, τ)*。这里的 M 是一个常数（约等于自然常数 *e*）。拒绝采样（Rejection Sampling） 是格签名中的关键技术，目的是使最终输出的签名 z_i 的分布统计上接近于高斯分布 *D_σ^m*，从而不泄露私钥 S_ID 的信息。本方案采用双峰高斯分布进行拒绝采样，相较于传统单峰方式，能以更小的标准差σ达到相同的安全效果，从而生成更短的签名，提升了效率。

4. 验证（Verification） 验证者收到签名 (z, h, τ)、消息 v、标签 τ 和签名者身份 ID 及公钥 (A, P_ID) 后： * (1) 计算 α‘ = H2( [A·z + (q/2)(H1(ID, P_ID) + P_ID)h] / l̂ mod q, τ )。其中 l̂ 是组合过程中系数的代数和（公开信息）。 * (2) 验证是否满足 *h = <α‘, v> mod 2*。 * (3) 验证签名向量的范数是否满足 *‖z‖ ≤ 2l̂σ√m*。 如果所有验证通过，则签名有效。

5. 组合（Combine） 给定 l 个三元组 (a_i, v_i, sig_i = (z_i, h_i, τ))，其中 a_i 是系数，任何中间节点（或验证者）可以公开计算： * 组合后的签名：z = Σ (a_i * z_i) mod q, h = Σ (a_i * h_i) mod q。 * 对应的组合消息：v = Σ (a_i * v_i) mod 2。 (z, h, τ) 即是对消息 v 的有效签名。这正是线性同态性的体现：对签名的线性组合，对应于对消息的同一线性组合。

四、 主要结果与安全性分析

本研究的主要结果并非实验数据，而是方案的正确性证明、效率分析以及严格的安全性证明。

1. 正确性证明 论文通过数学推导详细证明了方案的各项功能符合预期： * 签名有效性：通过代入验证算法，证明了对于一个正确生成的签名，验证算法中的等式 α‘ = α 和 h = <α, v> 恒成立。这确保了诚实生成的签名总能通过验证。 * 同态性正确性：论文证明了组合算法产生的签名 (z, h) 恰好满足验证等式，即组合后的签名是组合后消息的有效签名。推导中利用了 A·S_ID = A·(C_ID + D_ID) = P_ID + H1(ID, P_ID) 这一关键关系。 * 范数边界：基于拒绝采样和离散高斯分布的性质（引理1），证明了输出的签名向量 z_i 以及其线性组合 z 的范数均以压倒性概率小于预设的边界（*2l̂σ√m*），这保证了方案的实用性。

2. 效率分析（双峰高斯拒绝采样的优势） 论文对签名过程中的关键步骤——拒绝采样进行了深入的效率分析，这是本方案的一个亮点结果。分析表明： * 传统方法：在原始的拒绝采样中，要求标准差 *σ = τ * ‖(q/2)S_ID h_i‖*，其中 τ 是与安全参数平方根成正比的“尾割”因子，平均重复采样次数 *M ≈ e^(1)*。 * 本方案方法：采用双峰高斯分布后，签名原型为 z_i = (-1)^{b_i} * (q/2)S_ID h_i + y，其分布是两个对称高斯分布的混合。这使得在计算拒绝采样比率时，分母中的余弦双曲函数 cosh 项总是 ≥ 1。因此，可以取更小的标准差 *σ = ‖(q/2)S_ID h_i‖ / √2*，同时仍能保持平均重复次数 *M ≈ e*。由于签名大小大致为 *2σ√m*，更小的σ直接导致了更短的签名尺寸，提升了方案的效率。这是将双峰高斯技术应用于同态签名以提升效率的一个具体成果。

3. 安全性证明 论文在随机预言机模型下，对方案进行了严格的形式化安全证明，证明了其满足两个关键安全属性： * 弱上下文隐藏（Weak Context Hiding）：这是同态签名的隐私属性。论文通过定理1证明，对于在相同函数下输出相等的两个不同消息子空间，其对应的组合签名在计算上是不可区分的。证明利用了拒绝采样后签名分布的统计特性以及高斯分布的线性组合性质（引理2），说明任何多项式时间的敌手都无法赢得定义2中的安全游戏。 * 在适应性选择消息攻击下的存在性不可伪造性：这是签名的核心安全属性。论文重点针对第一类敌手（外部攻击者） 进行了详细证明（定理2）。敌手可以替换用户的公钥，但不能获取KGC生成的部分私钥。证明过程通过一个模拟游戏进行： * 模拟：挑战者C拥有格 Λ^⊥(A) 的陷门 T，他可以完美地回答敌手A对各种预言机（哈希、部分私钥、私钥、签名）的查询，即使是在敌手替换公钥的情况下。 * 规约：如果敌手A能够以一个不可忽略的概率成功伪造一个有效的签名，那么C可以利用这个伪造，结合“分叉引理（Forking Lemma）”，得到两个针对同一消息但不同哈希输出的有效签名。 * 求解SIS问题：通过这两个签名的差值，C可以构造出一个非零向量 x，满足 A·x = 0 mod q 且 ‖x‖ ≤ β，其中 *β = 4l̂σ√m + q(d√mk + σ√mk)*。这就意味着C解决了平均情况下的短整数解问题。由于SIS问题在适当参数下被假定是困难的，因此敌手成功伪造的概率必须是可以忽略的。论文指出，对第二类敌手（恶意的内部KGC） 的分析方法类似，区别在于敌手拥有主私钥但不能替换用户公钥。

五、 结论与研究价值

本研究成功设计并实现了一个基于格的无证书线性同态签名方案。结论表明： 1. 方案可行且正确：方案的五步算法构成了一个功能完整的系统，能够为网络编码提供安全的源认证和污染攻击防御。 2. 同时解决了多个痛点：格结构赋予了方案后量子时代的安全性；无证书结构从根本上避免了密钥托管问题，并能抵抗恶意的KGC；双峰高斯拒绝采样的应用在保证安全的同时提高了签名效率，产生了更短的签名。 3. 安全性可证明：在随机预言机模型下，方案被证明满足弱上下文隐藏性和针对外部攻击者及内部KGC的存在性不可伪造性，其安全性规约到标准的格上困难问题（SIS）。

该研究的价值体现在： * 科学价值：为后量子密码学，特别是同态密码学，提供了一个新颖、安全、高效的构造实例。它将无证书密码体制与格密码、同态签名相结合，展示了解决复杂安全需求时多种密码学工具融合的可能性。形式化的安全证明也为同类研究提供了参考模板。 * 应用价值：方案直接面向网络编码这一具体应用场景，其无证书、抗量子、支持同态验证的特性，使其非常适合于大规模、分布式、对安全性要求高的网络环境，如未来物联网、5G/6G网络、分布式存储等，具有明确的工程应用前景。

六、 研究亮点

本研究的突出亮点在于： 1. 问题导向的综合性解决方案：并非单一技术的改进，而是针对网络编码安全中“后量子安全”、“密钥托管”、“恶意KGC”、“效率”四大挑战，提出了一套整合了格密码、无证书密码和优化拒绝采样技术的系统性解决方案。 2. 巧妙的“循环依赖”密钥生成机制：在KeyGen算法中，用户的部分公钥 P_ID 依赖于自己选择的秘密 C_ID，而KGC生成的部分私钥 D_ID 又依赖于 P_ID，最终用户的完整私钥 S_ID 依赖于 D_ID。这种相互依赖的结构是防止各类攻击（如中间人攻击、0/1攻击）的关键设计。 3. 双峰高斯分布的应用创新：将主要用于普通数字签名优化的双峰高斯拒绝采样技术，创造性地应用于线性同态签名场景，并具体分析证明了其在减小签名尺寸、提升效率方面的优势，这是一个技术应用上的亮点。 4. 全面的安全性刻画与证明：不仅证明了抵抗外部攻击者的安全性，还考虑了抵抗内部恶意KGC的场景，并对同态签名特有的“弱上下文隐藏”属性进行了证明，安全模型较为完整。

七、 其他有价值内容

论文在引言部分对同态签名的发展历程、基于证书、基于身份和无证书三类公钥体系的优缺点进行了清晰的梳理和比较（相关工作部分），为读者提供了良好的学术背景。同时，论文在系统模型部分，用图1、图2、图3直观地对比了传统安全网络编码、基于身份的网络编码和本方案所支持的无证书网络编码的工作流程与威胁模型，有助于读者快速理解方案的应用场景和安全优势。最后，论文通过表2与多个经典方案进行了详细的对比，从公/私钥大小、签名尺寸、计算开销、是否抗恶意KGC、是否避免密钥托管等多个维度，量化地展示了本方案的性能与安全优势。