基于格密码的对数级身份基环签名方案及其可链接变体研究

为解决区块链中隐私保护与防重复消费的矛盾问题，研究人员基于格密码（lattice）的MSIS假设，构建了具有对数通信成本的身份基环签名（IBRS）及其可链接变体。该方案通过Merkle树实现匿名性，签名尺寸仅随环规模N呈对数增长（N=512时仅99.52KiB），显著优于线性方案（2695.74KiB），为抗量子攻击的匿名投票和加密货币提供了高效解决方案。

　　

随着区块链技术的普及，隐私保护与交易透明性之间的矛盾日益凸显。传统环签名（如Monero采用的方案）虽能隐藏交易者身份，但面临量子计算威胁，且线性增长的签名尺寸导致存储开销巨大。更棘手的是，恶意用户可能利用环签名的匿名性重复投票或双花（double spending），而现有可链接方案（如Torres等人的工作）在N=512时签名尺寸高达3000KiB，难以实际应用。

针对上述问题，中国研究人员提出了一种基于格密码（lattice）的创新方案。该工作通过Fiat-Shamir启发式将Sigma协议转化为非交互式证明，结合Merkle树实现成员验证，构建了首个对数级身份基环签名（IBRS）。在随机预言模型（ROM）下，方案的安全性依赖于模块小整数解（Module Small Integer Solution, MSIS）假设——一种公认的抗量子计算难题。当环规模N从32增至512时，签名尺寸仅从96.90KiB微增至99.52KiB，较线性方案（154.06KiB→2695.74KiB）有数量级优势。此外，研究者通过引入标签矩阵B扩展出可链接变体（IBLRS），能有效检测重复签名行为，为匿名选举等场景提供双重保障。

关键技术方法
研究采用格密码框架下的拒绝采样技术（rejection sampling）优化签名效率，通过Merkle树深度logN路径压缩证明规模，参数选择满足R_q=Z[X]/(q,X^t+1)环上的MSIS困难性。实验对比了8种方案，包括VLR群签名和NTRU格方案。

研究结果

1. 身份基环签名构造：利用TrapGen算法生成主密钥，用户身份直接作为公钥，通过OR-proof实现环成员匿名性。
2. 可链接性扩展：新增IBLRS.Link算法，通过标签τ=H(B∥M)检测重复签名，安全性分析显示其满足强不可伪造性。
3. 效率对比：当N=512时，方案签名尺寸仅为同类最优方案的3.7%，且验证时间与logN成正比。

结论与意义
该研究首次实现格上对数级IBRS，解决了大规模环应用中存储爆炸的瓶颈问题。其可链接变体为区块链防双花和匿名选举提供了可落地的解决方案，例如系统可监控投票者是否用同一身份多次投票（见图1流程）。未来工作可探索标准模型下的构造，进一步降低拒绝采样带来的计算损耗。论文发表于《Computer Standards》，为后量子密码学在隐私保护领域的应用树立了新标杆。