高效的可链接环签名与阈值签名：从线性反馈移位寄存器谈起

### 高效的可链接环签名与阈值签名：从线性反馈移位寄存器谈起 在当今的数字时代，密码系统的高效性与安全性是至关重要的需求。无论是在资源受限的环境中，还是为了满足各种实际应用的安全策略，研究者们都在不断探索如何在不损失安全的前提下加速密码系统。本文将深入探讨两类重要的签名方案——可链接环签名和阈值签名，并介绍基于线性反馈移位寄存器（LFSR）生成的n阶特征序列实现这些签名方案的方法。 #### 1. 背景与需求 在许多实际应用场景中，如低带宽通信环境或需要人工输入签名的情况，短数字签名和附加消息变得尤为重要。有限域的公钥密码系统，如ElGamal、DSS等，为了保证安全性，通常需要较大的底层域尺寸，这对于带宽受限的应用来说并不理想。因此，减少通信开销、降低计算成本并提高安全级别成为了密码系统设计的关键挑战。 #### 2. 环签名与可链接环签名 环签名是一种具有匿名性的签名方案，用户可以选择包括自己在内的一组可能的签名者（称为环），使用自己的私钥和环中其他成员的公钥对消息进行签名。验证者可以确认签名是由环中的某个人生成的，但无法得知实际签名者的身份。可链接环签名则在此基础上增加了链接性，即任何人都可以判断两个环签名是否由同一个私钥生成，这在电子投票系统中检测双重投票、公司员工匿名自愿问卷调查等场景中非常有用。 #### 3. 阈值签名 阈值签名是一种通过分布式计算分散签名权力的工具。在(t, n)-阈值密码学方法中，秘密信息（私钥）和计算（签名生成或解密）被分配给n个参与方，以消除单点故障。只要超过t个参与方的子集就可以联合重建秘密并执行计算，同时在存在最多t - 1个被破坏方的情况下仍能保证安全性。 #### 4. 现有方案的不足与本文的贡献 近期，一些密码系统通过用最小多项式的系数表示有限域中的元素来缩短元素的表示，从而减少密钥大小并加速计算。然而，这些方案大多缺乏正式的安全分析，而没有严格证明的密码原语或协议在实际应用中不能被视为安全的。 本文提出了基于LFSR生成的n阶特征序列的可链接环签名方案（LLRSS）和阈值签名方案（LTSS），具有以下优点： - **安全性**：安全属性依赖于状态离散对数问题（S-DLP）和状态决策Diffie-Hellman问题（S-DDH）的难度，这与传统的DLP和DDHP在GF(qn)中的计算复杂度相当。 - **高效性**：主要计算操作在GF(q)中进行，除了哈希评估和ZP中的加法/乘法外，只涉及GF(q)中元素的乘法，从而实现了快速计算。 #### 5. 预备知识 ##### 5.1 LFSR序列 设q是素数或素数的幂，f(x) = xn + a1xn - 1 + a2xn - 2 + ... + an是GF(q)上的不可约多项式，α是GF(qn)中阶为P的根。如果序列s = {sk}满足sk + n = a1sk + n - 1 + a2sk + n - 2 + ... + ansk（k ≥ 0），则称s是由f(x)生成的LFSR序列。当sk = tr(αk)（k = 0, 1, ..., n - 1）时，s被称为n阶特征序列，其周期等于α的阶。 ##### 5.2 LFSR序列的操作 - **SO1**：给定Ak（k未知）和整数l（0 ≤ k, l < P），计算Akl。 - **SO2**：给定状态¯sk（k未知）和¯sl（l未知）（0 ≤ k, l < P），计算¯sk + l。 - **SO3**：给定¯sk（k未知）和整数l（0 ≤ k, l < P），计算¯skl。 ##### 5.3 复杂度问题 - **状态离散对数问题（S-DLP）**：给定(q, n, P, ¯s1, ¯sk)，计算k。 - **状态决策Diffie-Hellman问题（S-DDHP）**：给定(q