基于格结构的对数无证书可链接环签名技术及其在电子投票系统中的应用

《Computational Statistics & Data Analysis》：Logarithmic certificate-less linkable ring signature over lattices and application in electronic voting systems

环签名在电子投票和加密货币中广泛应用，但其匿名性导致重复投票难以防范。本文提出基于M-SIS问题的证书_less链接环签名（CL-LRS）方案，结合Fiat-Shamir转换和Merkle树技术，既消除证书管理复杂性，又实现签名链接性，防止重复投票。方案在随机预言模型下证明匿名性、不可伪造性和可链接性，签名大小为现有方案的0.35倍，256人环下仅179.12 KiB，且抗量子计算攻击。应用场景验证了其在电子投票系统中的有效性。

　　随着信息技术的迅猛发展，互联网已经深度融入我们的日常生活，传统的投票方式逐渐被电子投票（e-voting）所取代。虽然电子投票在提高效率方面带来了显著优势，但同时也伴随着关键的安全风险，例如选票可能被伪造或重复投票。在现代社会中，如何为选民的隐私信息提供可靠保护，依然是一个亟待解决的挑战。

环签名作为一种隐私保护技术，因其不可追溯的特性而被广泛应用于电子投票和加密货币领域。然而，由于环签名无法被追踪，因此无法有效防止签名的滥用，这可能导致重复投票的问题。为了解决这一问题，研究人员提出了链接环签名（Linkable Ring Signature, LRS）这一环签名的变种。链接环签名在保持匿名性的同时，允许验证者检查多个签名是否来自同一签名者，从而有助于防止重复投票。然而，现有的基于格的链接环签名方案大多依赖于传统的公钥基础设施（Public Key Infrastructure, PKI），这不仅需要复杂的证书管理，而且效率相对较低。

为了解决上述问题，本文提出了一种基于格的证书无关链接环签名（Certificate-less Linkable Ring Signature, CL-LRS）方案，该方案基于模块短整数解（Module Short Integer Solution, M-SIS）问题。该方案不仅消除了证书管理的必要性，还解决了密钥托管（Key Escrow）的问题，从而在匿名电子投票系统中有效防止重复投票。通过安全性分析，我们的方案在随机预言模型（Random Oracle Model, ROM）下被证明是匿名的、不可伪造的和可链接的。与现有的类似方案相比，这些方案的签名大小通常随着环的大小线性增长，而我们的方案将签名大小降低至对数级别。例如，在一个由256名成员组成的环中，其他方案的最优签名大小为513.03 KiB，而我们的方案仅需179.12 KiB。具体而言，每增加一倍的环成员数，签名大小仅增加0.29%，显著优于现有方案。

在应用方面，我们将该方案应用于电子投票系统，通过构建电子投票系统模型和介绍其应用流程，展示了该方案的实际可行性。在后量子计算时代，基于格的签名方案成为密码学研究的热点，因为传统基于数学问题（如RSA和椭圆曲线）的密码系统面临越来越多的威胁。基于格的环签名结合了传统环签名的匿名性和格密码的抗量子特性，为信息保护提供了更强大的安全保障。目前，基于格的环签名已经取得了多方面的进展，包括基于格的链接环签名、基于格的阈值环签名等。然而，基于格的证书无关链接环签名（CL-LRS）方案仍然较为罕见，大多数方案未能同时解决数字证书管理和密钥托管问题，同时实现链接性。

为了克服这些局限，本文提出了一种基于格的CL-LRS方案，该方案在保持链接性的同时，消除了对证书的依赖，从而在不牺牲选民匿名性的前提下，有效防止重复投票。在语法和安全性要求方面，本文定义了CL-LRS方案的结构，并提出了其在随机预言模型下的安全性证明。在效率分析方面，通过引入Merkle树技术，我们的方案实现了对数级别的签名大小，使得签名效率显著提升。此外，我们还比较了与其他方案的性能，展示了在相同参数设置下，我们的方案能够达到190位的安全级别。

在电子投票的应用场景中，我们构建了电子投票系统的模型，并详细描述了该方案在实际应用中的流程。通过这一方案，选民的隐私得到了有效保护，同时系统具备防止重复投票的能力。此外，该方案还采用了Fiat-Shamir转换，将交互式协议转换为非交互式协议，从而简化了签名过程，提高了效率。在实现过程中，我们设计了一种密钥生成机制，使得用户的私钥由用户和密钥生成中心（Key Generation Center, KGC）共同生成，避免了密钥托管问题，同时消除了对数字证书的依赖。

本文的贡献主要体现在以下几个方面：首先，我们借鉴了[12]中提出的OR sigma协议，并结合Fiat-Shamir转换，将其转化为非交互式协议，从而构建了一个基于格的CL-LRS方案。该方案不仅解决了证书管理和密钥托管问题，还通过嵌入链接标签，防止了重复投票的发生。其次，我们在安全性分析中，严格证明了该方案在随机oracle模型下满足正确性、匿名性、不可伪造性和可链接性。特别是，不可伪造性可以归约到M-SIS问题的硬度上，从而确保了方案的安全性。第三，在效率分析方面，我们通过引入Merkle树技术，使得签名大小达到对数级别，即使环成员数翻倍，签名大小的增加幅度也仅为0.29%，显著提升了签名效率。最后，在应用场景方面，我们将该方案应用于电子投票系统，展示了其在实际应用中的优势，包括消除密钥托管风险、实现高效重复投票检测，同时保持选民的匿名性。

在密码学的发展历程中，基于格的签名方案经历了多次演进。2008年，Gentry等人[13]首次提出了基于格的签名方案，采用“哈希和签名”方法，但其签名存储成本和计算效率并不理想。随后，Lyubashevsky[14]应用Fiat-Shamir转换构建了一个基于格的一次性签名方案，提高了签名效率，但存储成本仍然较高。2018年，Baum等人[15]提出了一种基于格的链接环签名方案，简化了前人的结构，避免了对大量零知识证明的依赖，从而降低了计算成本。2020年，Ye等人[16]提出了一种基于环学习问题（Ring Learning with Errors, R-LWE）的链接环签名方案，而Beullens等人[12]则引入了一种基于Merkle树的链接环签名方案，实现了对数级别的签名大小。2022年，Hu等人[17]提出了一种基于格的链接环签名方案，该方案在标准模型下运行，无需依赖随机预言模型。2024年，Khuc[18]提出了一种基于格同构问题的链接环签名方案，进一步优化了效率，降低了签名大小。尽管这些方案在一定程度上取得了进展，但大多数仍然依赖于传统的PKI，这需要通过可信的证书颁发机构（Certificate Authority, CA）进行证书管理，增加了签名方案的复杂性。

身份基密码系统（Identity-Based Cryptosystem, IBC）通过将用户的公钥与其身份信息（如电子邮件地址或姓名）绑定，解决了数字证书管理的问题。密钥生成中心（KGC）负责根据用户的身份信息生成对应的私钥，从而避免了传统PKI中对公钥证书的大量管理和验证。2021年，Tang等人[19]提出了一种基于NTRU格的身份基链接环签名（Identity-Based Linkable Ring Signature, IB-LRS）方案，采用陷阱门生成算法和拒绝采样方法生成私钥和签名，显著提高了效率，并将不可伪造性归约到短整数解（Short Integer Solution, SIS）问题，从而提供了更强的安全保障。2024年，Xie等人[20]提出了一种基于格的身份基链接环签名方案，采用双模高斯分布下的拒绝采样方法生成签名，进一步降低了签名生成的时间开销。随后，Gao等人[21]提出了一种基于Merkle树的身份基链接环签名方案，降低了存储成本。然而，身份基签名仍然面临密钥托管问题，因为KGC负责管理用户的私钥，这可能带来潜在的安全风险。

为了同时解决密钥托管和证书管理问题，证书无关签名系统（Certificate-less Signature System）允许用户的私钥由用户和KGC共同生成，无需第三方干预。这不仅消除了密钥托管的风险，还去除了对数字证书的依赖，从而简化并增强了系统的安全性。2020年，Deng等人[22]提出了一种证书无关链接环签名（CL-LRS）方案，但其安全性基于离散对数问题，这在面对量子计算攻击时显得脆弱。2022年，Dong等人[23]提出了一种基于格的CL-LRS方案，采用双模高斯分布提高效率，但其存储成本仍然较高。2025年，Gao等人[24]提出了一种基于NTRU格的CL-RS方案，该方案减少了签名大小，但未能实现链接性。

本文提出的基于格的CL-LRS方案在多个方面进行了创新和优化。首先，我们设计了一种高效的密钥生成机制，使得用户的私钥由用户和KGC分步生成，避免了密钥托管问题，同时消除了对数字证书的依赖。其次，我们通过引入链接标签，确保了签名之间的可链接性，从而防止了重复投票的发生。在实现过程中，我们采用了Fiat-Shamir转换，将交互式协议转换为非交互式协议，提高了签名效率。此外，我们还通过引入Merkle树技术，将签名大小控制在对数级别，使得在环成员数增加时，签名大小的增长幅度显著降低。

在安全性分析方面，我们严格证明了该方案在随机预言模型下满足正确性、匿名性、不可伪造性以及可链接性。不可伪造性可以归约到M-SIS问题的硬度上，从而确保了方案的安全性。在效率分析方面，我们通过实验和理论分析，展示了该方案在签名生成和验证过程中的高效性，特别是在签名大小和验证时间方面，相比现有方案有明显优势。此外，我们还比较了该方案与其他基于格的CL-LRS方案的性能，展示了其在相同安全级别下的优势。

在实际应用方面，我们将该方案应用于电子投票系统，构建了一个高效的电子投票模型，并详细描述了其应用流程。该模型不仅保持了选民的匿名性，还通过链接标签实现了对重复投票的有效检测。此外，该方案在签名生成和验证过程中，避免了对证书的依赖，从而简化了系统的复杂性，提高了效率。

综上所述，本文提出的基于格的CL-LRS方案在多个方面进行了创新和优化，解决了现有方案中的诸多问题，包括证书管理和密钥托管问题，同时实现了签名的链接性。该方案不仅具备抗量子计算的能力，还在签名效率和安全性方面表现出色，为电子投票系统提供了一种高效、安全、可靠的隐私保护机制。