Abstract

环签名可以使得签名者在不泄露身份的前提下，匿名代表一个组进行消息签名，门限环签名允许多个签名者代表一个群组对同一消息签名，尽管组合签名揭示了组成员中的某个阈值$t$的子集成员对消息进行了签名，但是并未泄露任何关于签名者身份的其他任何信息，得益于这个特性，匿名性作为门限环签名的一个核心特征，广泛应用于whistblowing，电子投票，隐私保护的加密货币等领域

在签名过程中，签名者与其他签名值保持匿名也很重要，如果签名生成过程需要交互时，则难以实现匿名性，不过目前也存在具有非交互式签名的门限环签名（此类方案中签名者本地生成部分签名然后进行聚合）

然而，现有的门限环签名的构造存在一定的限制，也即所有的签名者必须同意他们代表整个签名组，这一过程隐含了这些签名者之间存在某种协调关系（签名者们再签名之前需要达成某些一致），这一特性也阻止了群组之外的其他人加入这个签名群组

本文通过引入环签名，相同消息可链接环签名和门限环签名的可扩展性这三个概念来克服上述限制，其中可扩展性允许不受信任的第三方获取签名，在可扩展的门限环签名中，同一消息上的两个已扩展到同一匿名集的签名可以组合成具有更高门限的一个签名，这样可以增加签名者的匿名性，同时使得新的签名者可以匿名支持他人已发表的statement

本文形式化了上述原语，基于知识签名与离散对数给出了每个原语的具体实现

1 Introduction

匿名性是许多密码系统与隐私技术的基本需求（包括电子投票、直接匿名认证和私人加密货币），受到学术界的广泛研究

群签名可以使给定群组的任何成员都可以对消息进行签名，而不透露签名的成员，然而群签名有一个缺点，即需要对签名的群组进行可信设置，环签名是群签名的一种无管理器变体，允许单个用户代表动态选择的用户组匿名签名消息，同时隐藏签名者的确切身份

环签名不会揭示签名者使用了哪一个相应的密钥来生成它，有许多方法可以使用不同的构建块来构造环签名：经典的RSA、双线性对、复合序群、非交互式零知识，量子安全同构和格

门限环签名是该原语的一个门限变体，允许$t$个签名者代表一个大小大于$t$的环$R$进行消息签名，签名表明该环中的$t$个成员签名了消息，且不会暴露这些签名者的身份，部分门限环签名方案较为灵活，即使在为给定环$R$生成了门限环签名之后，该环的另一个签名者可以为相同环$R$生成门限环签名，并令门限值为$t+1$，现有的构造不允许环外的签名者参与此类扩展操作

但是现有的环签名和门限环签名的构造存在一个共同的限制：环的潜在签名者在签名生成时是固定的，且无法通过将初始环扩展到更大的环的方式来增加匿名集，增加潜在签名者集合的大小不仅增加了签名提供的匿名性，而且使门限系统在实践中更容易实现，标准门限环签名需要所有签名者使用相同的环$R$独立地签名相同的消息$\mu$，该环$R$必须包括所有签名者的公钥

1.1 Our Contributions

本文引入门限环签名的新的性质，称为可扩展性，若门限环签名方案允许任何人扩大给定签名的潜在签名者集合，则该方案是可扩展的

简而言之，就是通过将环$R$扩展为一个新的环$R'\supseteq R\cup \{A\}$来实现，之后根据环签名的灵活性，新的签名者可以针对新环$R'$添加自己的签名（使用$A$的私钥$sk_A$）

这里有一个问题：如果一个参与方可以同时在旧环$R$和新环$R'$下获取签名，则其可以确定$R'\backslash R$，因为该参与方总是可以通过尝试验证签名来判断签名归属于哪个环，且可以帮助该参与方缩小新的签名者$A$的范围

但是如果该参与方不能在旧环$R$中获取签名值，则无法了解$A$所在的范围

本文的主要贡献如下

  • 使用知识签名来构建可扩展的环签名和相同的消息可链接的可扩展环签名，每个签名将包含群内的若干个离散对数未知的元素
    签名者利用一个知识签名来签名消息，该签名可以证明他知道自己的密钥或其中一个元素的离散对数，对于环中其他签名者的公钥，签名者使用其中一个元素的离散对数来包含知识签名，由于所有元素的离散对数都是未知的，签名验证者可以确定至少有一个知识签名是使用密钥生成的，因此整个签名是由环中的一个成员生成的

本文构建了可扩展的门限环签名方案，可以在不揭示公共参数中挑战元素的离散对数的情况下，至少不能知道其中$t$个离散对数

  • 本文还提出了一个通用变体，部分学者希望通过串联$t$个可扩展的环签名来构建可扩展的门限环签名，但是这一过程需要向验证者证明$t$个签名是由$t$个不同的签名者生成的，此类签名的构建需要签名者之间进行交互，而且随着环的扩展，证明的维护也是一个问题
    本文提出了一个新的原语，称为同一消息可链接的可扩展环签名，给定同一消息上的两个签名可以立即确定他们是否是由同一签名者生成的

本文为该原语提供了可链接性，且无需揭示签名者身份或引入额外的零知识证明，该原语可用于通用方式构造的可扩展门限环签名

2 Background and Preliminaries

2.1 Notation

  • $N$：自然数集
  • $\lambda$：计算安全参数
  • $negl(\lambda)=\Omega(\lambda^{-c})$：其中$c>1$
  • $[a,\dots ,b]$：表示范围$a,b$内的整数构成的集合
  • $[b]$：表示整数集$[1,\dots,b]$
  • $\epsilon$：表示空串
  • $a\larr_R X$：表示从集合$X$中随机选择一个元素并赋值给$a$
  • $GroupGen(1^\lambda)$：输出三元组$(p,g,G)$，其中$p$为长度为$2\lambda$比特的素数，$g$为群$G$的生成元，群$G$的阶为$p$

此外，本文若未作说明，算法均为PPT算法，本文假设群$G$上的离散对数问题困难

2.2 Ring Signatures

群签名有个缺点，需要可信机构作为群管理器，该群管理器负责定义签名者组并为他们分发密钥，签名者的密钥可以用于代表整个群来匿名签名消息，群管理器可以随时添加和撤销签名者，而环签名无需群管理器，且允许签名者自己生成密钥对，并以特殊的方式构成签名组

环签名定义如下

环签名$RS$定义为一个PPT算法四元组$RS=(Setup,KeyGen,Sign,Verify)$

  • $Setup(1^\lambda)\rarr pp$：输入安全参数，输出公共参数$pp$
  • $KeyGen()\rarr(pk,sk)$：生成密钥对$(pk,sk)$
  • $Sign(\mu,\{pk_j\}_{j\in R},sk_i)\rarr \sigma$：输入待签名消息$\mu$，公钥集合$\{pk_j\}_{j\in R}$，第$i$个签名者的私钥$sk_i$，输出签名值$\sigma$
  • $Verify(\mu,\{pk_j\}_{j\in R},\sigma)\rarr 0/1$：验证签名值是否是关于消息$\mu$的签名，输出接受或拒绝

环签名方案应当满足正确性，也即任何合法的签名值都会通过验证，此外安全的环签名还应该满足下列两个性质

  • 不可伪造性：在不知道与环中公共验证密钥对应的至少一个签名私钥的情况下，任意敌手都无法生成可以通过验证的签名
  • 匿名性：任何敌手都无法从签名中分辨出具体是哪个环成员生成了该签名值

2.3 Threshold Signature

门限环签名与环签名类似，不过门限环签名不是让任意一个签名者在签名环中匿名，而是允许任意$t$个签名者在签名环$R$中匿名（$t\leq |R|$），验证者可以检查环中至少$t$个签名者签名了相同的消息（普通的环签名可以视为$t=1$的门限环签名）

非交互门限环签名定义如下

非交互门限环签名为一个PPT算法五元组$(Setup,KeyGen,Sign,Verify,Combisign)$，其中前四个算法与环签名中定义相同

  • $Combisign(\{\sigma_i\}_{i\in S\sube R})\rarr \sigma$：选择一个大小为$t$的子集$S$，组合集合中的签名值$\{\sigma_i\}_{i\in S}$，输出组合签名值$\sigma$

交互式门限环签名定义类似，此时$Sign$为签名者之间运行的交互时协议（协议隐式要求签名者之间互相了解身份）

交互式方案与非交互式方案之间存在一种解决方案：一个签名者生成初始签名，其余的签名者传递签名，并在传递签名之前“加入”（joins）签名，此类方式下用到的算法为$Join$而非$Combisign$，且要求每个签名者只能从另一个签名者接收至多一条消息，并向另一个签名者发送至多一条消息

  • $Join(\mu,\{pk_j\}_{j\in R},sk,\sigma)\rarr \sigma'$：输入待签名消息$\mu$，公钥集合$\{pk_j\}$，新的签名者密钥$sk$和$R$中某个子集（门限为$t'$）生成的签名值$\sigma$，输出签名值$\sigma'$，且门限值为$t'+1$

2.4 Signatures of Knowledge

知识签名（SoK）用密钥对来代替NP语言中的statement和witness实现数字签名，SoK的概念模仿了具有很强的存在不可伪造性的数字签名：敌手在任意statement下看到了任意消息上的多个签名，敌手也无法在不知道对应statement的witness的情况下创建新签名（无法构造以前从未出现过的签名）

知识的特征与可模拟提取的SNARK密切相关

考虑一个可高效判定的二元关系$\mathcal R$，其中$(\phi,w)\in \mathcal R$，令$L_\mathcal R$表示包含所有statement $\phi$的语言，SoK定义如下

一个关于二元关系$\mathcal R$的SoK为一个PPT算法五元组

  • $Setup(1^\lambda,\mathcal R)\rarr pp$：输入安全参数，输出公共参数$pp$
  • $Sign(\mu,\phi,w)\rarr \sigma$：输入待签名消息$\mu$，输出签名值$\sigma$
  • $Verify(\mu,\phi,\sigma)\rarr 0/1$：验证签名值是否是关于消息$\mu$的签名，输出接受或拒绝
  • $SimSetup(1^\lambda,\mathcal R)\rarr(pp,td)$：模拟setup除了输出公共参数外，还会输出一个陷门$td$
  • $SimSign(td,\mu,\phi)\rarr \sigma'$：模拟签名需要输入陷门，同时输出一个模拟签名值$\sigma'$

Security Model

本文要求SoK满足三个性质

  • 正确性（Correctness）：正确性要求对于拥有有效witness的签名者总可以生成一个可以通过验证的签名
  • 可模拟性（Simulatability）：该性质本质上说明了Verifier不能从签名中了解关于witness的任何信息，witness的保密性是在没有witness情况下来模拟签名而构建的

具体而言，若敌手无法区分真实的pp与签名和模拟器生成的签名，则称SoK为可模拟的

  • 模拟可扩展性（Simulation Extractability）：该性质确保了除非敌手有witness，否则无法发布新的签名，即使敌手在任意statement（包括虚假的statement）下看到任意消息的签名也无法做到这一点

在这种强攻击模型下，本文也要求每当对手输出之前未查询到的有效签名时，都可以提取该签名的witness

3 Extendable Ring Signatures

环签名可以使签名者在隐藏身份的同时完成签名，现有的构造无法使第三方在生成签名后增加环的大小，一旦生成了签名，就无法将其扩展到更大的匿名集合，也即环签名不允许在一个更大的潜在签名者集合中修改旧的签名值并获得同一消息的新的签名

本文提出了的可扩展的环签名，旨在解决这个问题，同时保留签名者的匿名性

3.1 Syntax

可扩展的环签名方案（Extendable Ring Signature，ERS）为一个包含$Extend$算法的环签名方案，该算法允许任意第三方在给定签名值时扩大潜在签名者的环

  • $Extend(\mu,\{pk_i\}_{i\in R},\sigma,\{pk_j\}_{j\in R'})\rarr \sigma'$：给定消息和公钥集合$\{pk_i\}_{i\in R}$，签名值$\sigma$，另一个环的公钥$\{pk_j\}_{j\in R'}$，输出一个修改后的签名值$\sigma'$，验证者为$R\cup R'$

Remark 1：对于ERS方案，其中$Extend$可以被重复使用以将签名扩展多项式次数，其中$Sign$总是为一个单环生成签名，仅包含签名者公钥$pk$，$Extend$也仅在单环上调用，也即$|R'|=1$，通过迭代调用$Extend$来让签名者附加单个公钥，从而将单个环的签名扩展到任意环

在接下来的定义中，本文采用环的阶梯（ladders of rings），也即$lad=(i,R^{(1)},R^{(2)},\dots ,R^{(l)})$，其中$i$为单个签名者实体，$R^{(1)}，R^{(2)},\dots,R^{(l)}$为签名者实体集合

本文采用算法$Process(\mu,L_{keys},lad)$（如图1所示），算法在给定的消息$\mu$上，以密钥序列$L_{keys}$处理阶梯$lad$，$Process$在$R^{(1)}$中以密钥$sk_i$对消息$\mu$进行签名，之后利用$L_{keys}$中的密钥将签名扩展到后续的环，$Process$算法返回一个扩展后的环的签名值$\sigma$

Process算法就是用密钥序列，依次按顺序处理阶梯上的各个环，这里有几个终止条件：

  • 第二行确保了所有的公钥都要在密钥序列中
  • 第三行确保所有签名者的密钥都在密钥序列中
  • 第四行确保这些密钥都是未被腐化的

之后就是调用签名算法，先为仅包含单个签名者的环生成签名，之后调用扩展算法，依次将签名扩展至阶梯中后续的环

为了确保正确性，本文要求$Process$输出的任何可能扩展的签名值$\sigma$都在最终环$R^{(l)}$上验证签名值

3.2 Security Model

安全的ERS方案定义如下

若一个可扩展的换签名方案满足正确性， 不可伪造性，匿名性和匿名可扩展性，则称该ERS方案为安全的

对于不可伪造性而言，可扩展环签名继承了常规环签名的不可伪造性要求：除非敌手知道至少一个属于环中一方的密钥，否则无法生成签名

注意到ERS的不可伪造性需要考虑敌手可以任意扩展与签名相关的环（如图2所示）

为了排除这种策略衍生的攻击，如果敌手通过扩展签名查询的结果可以生成一个伪造（$Exp^{cmEUF}_{A,ERS}(\lambda)$中的第五行），则敌手无法攻破不可伪造性

此外还有解决密钥复制攻击（敌手将现有公钥注册到新的身份，图2中的第七行），简单来说就是要求敌手伪造签名时必须使用一个未被腐化的签名者的公钥，使用已腐化的签名者的公钥构造的签名也算敌手失败

对于可扩展性，本文考虑与匿名性相关的安全概念，即匿名可扩展性，本文定义了可以支持三种不同类型的匿名可扩展性实验：标准匿名性概念（无扩展），弱扩展性（无法识别扩展签名的原始子集），强扩展性（无法知道签名经历了何种扩展序列）

对于标准的匿名性，本文考虑敌手输出两个阶梯（$lad^*_0,lad^*_1$，图3左侧的第五行），两个阶梯均只包含一个环，为了避免游戏获胜的概率太小，两个环必须相同（图3右侧的$Chal_b)$

此外，由于扩展算法未被调用（此时有$l_0=l_1=1$），由于敌手对挑战者的输入有限制，因此实验$ANEXT$与标准匿名性实验相同

对于弱匿名扩展性，本文要求敌手向挑战者提交一系列阶梯环，其中每个阶梯仅包含两个环，换言之，这意味着敌手需要选择两个（可能是不同的）阶梯环（$(i_0,R^{(1)}_0,R_0^{(2)}),(i_1,R^{(1)}_1,R_1^{(2)})$，其中$R^{(1)}_0\cup R_0^{(2)}=R^{(1)}_1\cup R_1^{(2)}=R$）

若给定关于超级环（super-ring）$R$的扩展签名，敌手可以识别（比随即猜测更准确）使用的是哪个阶梯，那么敌手就攻破了弱匿名可扩展性

Remark 2：弱匿名可扩展性只要满足两个条件：（a）扩展到同一个环，且（b）都只被扩展一次，则敌手无法区分两个扩展签名

本文还考虑了另一种弱可扩展的形式，其中不限制签名为单次扩展，而是允许任意次数的扩展，但是要求扩展的次数相同

对于强匿名扩展性而言，本文考虑输出任何其他类型阶梯并形成同一个环的敌手，尤其是$l_0\neq l_1$，注意到强匿名可扩展性包含弱匿名性和标准匿名性

注意到强可扩展性意味着扩展环签名的行为是无缝的（seamless），也即敌手无法区分新的环签名（由$Sign$输出）及其扩展（由$Extend$输出），此类情况中有$l_0=1,l_1>1$

这一块看的不是很明白

3.3 ERS from Signatures of Knowledge and Discrete Log

本节利用素数阶群和知识签名来实现可扩展环签名方案

Nutshell

$setup$算法生成一个素数阶群$G=<g>$，一个随机群元素$H\larr_R G$和SoK关于关系$R_G$的公共参数$pp$

$$ R_G(\phi=(h,pk),w=x)=\{g^x=h\vee g^x=pk \} $$

$R_G$可以证明签名者要么知道$pk$的离散对数（对应于$pk$的私钥），要么知道随机元素$h$的离散对数

签名过程如下图所示

签名过程为选择一个随机元素$td\larr _R \Z_p$，计算$h=H\cdot g^{-td}$（也即$h\cdot g^{td}=H$），同时利用私钥$sk$计算关于$(h,pk)$的知识签名$\pi$，签名值$\sigma$包含陷门$td$和集合$P=\{h,pk,\pi\}$

扩展方式与签名过程类似，但是扩展算法采用新的witness，具体而言，扩展器需要选择一个新的陷门$td'$，计算$h'=g^{td'}$及其对应的$\pi',pk'$，并将陷门$td'$作为新的witness，之后将三元组$\{h',pk',\pi'\}$加入$P$，并令新的陷门$td=td-td'$

扩展后的验证方法如下：对于$P$中所有的$h_i$，验证等式$H=g^{td}\cdot \prod_i h_i$是否成立，同时验证所有的$\pi_i$是否合法，这样一来可以确保至少一个$\pi_i$是使用$sk_i$作为witness生成的（否则可以计算$H$的离散对数）

对于方案的不可伪造性而言，本文给出了一个混合博弈序列，在该序列的末尾，规约可以以足够高的概率从敌手$A$的伪造中抽取离散对数的解决方案，这一规约序列涉及几个点：

  1. 将离散对数嵌入$H$​
  2. 转换为SoK的模拟Setup
  3. 将所有知识签名替换为模拟签名
  4. 使用从$\pi^*$抽取的witness来计算$H$的离散对数

具体而言，根据定义3的定义，需要证明敌手$A$可以成功伪造一个合法签名值的概率可忽略，此时假设$A$以不可忽略的概率赢得了不可伪造游戏，本文通过展示一个与$A$交互的规约$B$来扮演不可伪造游戏中的挑战者的角色，并从$A$的伪造中抽取离散对数挑战的解，本文描述了一系列的混合模型，其中$A$无法检测到$B$的行为的变化，最终混合中，$B$可以使用$A$来解决离散对数挑战

具体的混合博弈序列可以看原文，这里不展开介绍

对于方案的匿名可扩展性而言，如果敌手$A$能够成功地破坏匿名可扩展能力，则意味着敌手可以构建破坏知识签名安全性的规约$B$

假设$B$扮演挑战者，运行知识签名的模拟设置（而非真实设置），此时可以为$B$提供了一个陷门，允许它在不知道witness的情况下模拟签名，此时$B$使用此陷门模拟所有知识签名，以响应来自$A$的签名查询

之后$B$在不参考阶梯情况下生成挑战签名，$B$只需要随机选择$td$，生成$h_i$作为随机值，使得$g^{td}\cdot \prod_i h_i=H$，并使用陷门模拟所有知识签名

如果$A$可以将$B$与诚实的挑战者区分开来，则$B$可以使用$A$来攻破知识签名的可模拟性，若$A$无法将$B$与诚实的挑战者区分开来，因为$B$的行为不取决于对b的选择，$A$不可能以不可忽略的超过一半的概率赢得匿名可扩展性游戏

4 Same-Message Linkable Extendable Ring Signatures

同一消息可链接环签名方案（SMLRS）是一种环签名方案，允许任何第三方确定（链接）同一签名者是否为同一消息生成了两个签名，这意味着如果同一方对同一消息签署两次（采用的不同的环也算），这两个签名也可以由任何第三方链接

相同消息可链接环签名的可以用于构造门限环签名：门限环签名可以构建为相同消息可链接环签名的简单级联

SMLRS可用于以通用方式构建具有不同程度可链接性的其他方案，例如通过要求每个签名者在其消息中包含随机随机数，可以从SMLRS方案中实现不可链接（环）签名

对于标准可链接（环）签名，其中来自同一签名者的两个签名无论签名哪一条消息都是可链接的——可以通过SMLRS方案实例化，方法是要求签名者除了签名消息$\mu$外，还必须始终签名一个固定值（比如对$\bot$签名）

4.1 Syntax

SMLRS方案为一个算法六元组$SMLERS=(Setup,KeyGen,Sign,Verify,Extend,Link)$，其中前五个算法与ERS方案相同，链接算法允许任何Verifier确定特定消息上的两个签名是否由同一签名者生成

  • $Link(\mu,(\sigma_0,\{pk_j\}_{j\in R_0}),(\sigma_1,\{pk_j\}_{i\in R_1}))\rarr \{linked,unlinked\}$：算法以消息$\mu$为输入，两个签名值及其对应的公钥（分别来自于两个环$R_0,R_1$），若$\sigma_0,\sigma_1$来自于相同的签名者，则算法输出$linked$，否则输出$unlinked$

有一点需要注意：如果签名被链接，则链接不一定会显示共同签名者的身份

接下来本文讨论SMLERS方案的正确性，包含两个陈述：扩展签名验证（继承自ERS的正确性，定义1）和来自不同签名者的扩展签名为不可链接的，下面对这两个定义进行形式化

Remark 3：为了便于理解安全模型，可以考虑以下构建SMLERS的策略：确保（部分）签名对于每个公钥和消息对都是唯一的，换言之，签名者公钥和签名消息唯一确定了环签名的一部分，本文将这一部分称为可链接性标签，此标记不会因环扩展而修改，只需要检查两个环签名是否共享同一标记即可用于识别同意消息上的两个环签名是否由同一签名者生成

4.2 Security Model

一个相同消息可链接的可扩展环签名方案具有下列三个性质

  • Same-Message One-More Linkability：没有任意一个包含$t-1$个已攻破的签名者集合可以为同一消息生成$t$个成对未链接的签名（定义9）
  • Cross-Message Unlinkability：任何敌手都无法确定不同消息的两个签名是否由同一签名者生成（定义10）
  • Unframeability（可选）：任何敌手都无法生成链接到诚实签名者的签名
    本文不要求可扩展门限环签名方案具有此性质，因此本文并未正式定义该性质，也未证明本文的构造满足此性质，不过该性质可被认为是对交叉签名者的正确性的增强

对应的安全实验如下

4.3 SMLERS from Signatures of Knowledge and Discrete Log

本文的SMLERS结构基于图4中的ERS结构，两者的区别不大，下面描述一下将ERS转换为SMLERS需要调整的部分

首先将关系修改为$R_{SMLERS}$如下，SMLERS的知识签名与这个新的关系相关

$$ R_{SMLERS}=(\phi=(h,pk,g',\tau),w=x)=\{g^x=h\vee (g^x=pk\wedge (g')^x=\tau )\} $$

注意最后一个与条件，这里不仅要求签名者证明其拥有私钥的知识，还需要确保该私钥用于生成链接标志$\tau$

其次，修改图4的ERS中的$Sign$算法，加入额外的两个计算步骤，分别计算$g'=H(\mu),\tau=(g')^{sk}$，其中$H$为Hash函数（区别于之前的随机群元素$H$)，并将链接标志$\tau$作为签名的一部分

最后，算法$Link$比较两个签名中的链接标志，若相等则返回$linked$，否则返回$unlinked$

5 Extendable Threshold Ring Signatures

与传统的门限环签名方案一样，可扩展的门限环签名方案使各方能够在消息$\mu$上为环$R$生成签名，表明环中的$|R|$个潜在签名者中至少有$t$个参与了签名，且可以确保这些签名者的匿名性

此外，可扩展门限环签名方案还具有以下性质

  • 灵活性（Flexibility）：给定相同消息$\mu$和相同环$R$的任意两个门限签名$\sigma_0,\sigma_1$，任意参与方均可非交互的结合这两个签名并得到$\sigma$，新的签名值同样是门限环签名，新签名值的门限等于对两个签名中的至少一个签名做出贡献的的唯一签名者的总数（两个签名者集合取交集）
    该性质由$Combine$算法实现
  • 可扩展性（Extendability）：给定消息$\mu$和环$R$的签名值$\sigma$，门限为$t$，任意参与方可以非交互的将签名$\sigma$转换为$\sigma'$，其中消息和门限不变，而环扩展为$R'\supseteq R$
    该性质由$Extend$算法实现

5.1 Syntax

ETRS（Extendable Threshold Ring Signature）定义为六个PPT算法$ETRS=(Setup,KeyGen,Sign,Verity,Combine,Extend)$，如下

  • $Setup(1^\lambda)\rarr pp$：
  • $KeyGen()\rarr (pk,sk)$：
  • $Sign(\mu,\{pk_i\}_{i\in R},sk)\rarr \sigma$：签名私钥为$sk$，返回门限$t=1$时对应于公钥$pk_i$的签名
  • $Verify(t,\mu,\{pk_i\}_{i\in R},\sigma)\rarr 0/1$：验证签名，通过输出1，否则输出0
  • $Combine(\mu,\sigma_0,\sigma_1,\{pk_i\}_{i\in R} \mapsto \sigma'$：组合同一个环$R$上的两个签名值，得到新的签名值为$\sigma'$，新的门限值为$t=|S_0\cup S_1|$（$S_0,S_1$分别表示生成$\sigma_0,\sigma_1$的签名者集合）
  • $Extend(\mu,\sigma,\{pk_i\}_{i\in R},\{pk_i\}_{i\in R'} ）\mapsto \sigma'$：将环$R$上的签名$\sigma$扩展至新的环$R'\cup R$，门限不变

如2.3节所述，在交互性方案中，可以用$Join$操作替换$Sign\&Combine$执行

本文使用阶梯$lad$的方式与本文在第3节的可扩展环签名的使用的方式略有不同，之前方案中的$lad$包含一系列环，这些环会在用$Extend$操作中，这里需要将$lad$推广至得到有效门限环签名的任意操作序列，殷蹙为$lad$定义$(action,input)$序列，其中$action$可以为$(Sign,Combine,Extend)$中的任意一个，$input$表示对应$action$下算法的输入

  • 若$action=Sign$，则表示$input=(R,i)$，其中$R,i$表示对应的环以及生成签名的实体
  • 若$action=Combine$，则$input=(l_1,l_2,R)$，其中$l_1,l_2$表示在环$R$中的连个签名
  • 若$action=Extend$，则$input=(l',R)$，其中$l'$表示已存在的签名，且该签名将扩展至环$R$

此外还定义了算法$Process(\mu,L_{keys},lad)$，用于处理消息$\mu$在$lad$中的所有操作（密钥序列为$L_{keys}$），算法返回$(\sigma,t,R)$：$lad$最后一次操作返回的签名$\sigma$，对应的门限$t$和验证签名的环$R$，本文将$lad.sr$定义为$lad$中所有身份与环的联合（union）（$sr$代表超级环）

5.2 Security Model

没看，太长了

5.3 A Generic Compiler for ETRS from SMLERS

本节介绍如何从任何给定的相同消息可链接的可扩展环签名方案中得到可扩展门限环签名方案，具体的编译器如图10所示

方案有两个属性，分别为不可伪造性（Unforgeability）和匿名性（Anonymity）

对于不可伪造性而言，ETRS的不可伪造性可以归约至SMLERS方案的一个以上的可链接性（one-more linkability），由于ETRS方案的伪造对应于$t$个未链接的SMLERS签名，因此该规约简单且严密（tight）

对于匿名性而言，ETRS的匿名性可以归约至底层SMLERS的匿名性，证明通过一系列的混合游戏$\mathcal H$来证明，在$H_0$中，挑战者总是选择匿名比特$b=0$，而在最终混合$H_t$中，挑战者总是选择混合比特$b=1$

简单来说就是假设由敌手为挑战者选择的两个签名者集合相互独立（两个集合的交集为空，也即$lad_0^*.signers\cap lad^*_1.signers = \emptyset$），中间混合逐渐将挑战签名的由$lad_0^*.signers$修改为$lad^*_1.signers$，对于$H_j(j=1,\dots,t)$而言，挑战者返回签名值$\bar \sigma$，该签名值由来自$lad^*_1.signers$的前$j$个签名实体和来自$lad^*_0.signers$的后$t-j$个签名实体组合而成，令$E_j$表示事件：敌手$A$在$H_j$结束时猜测$b^*=1$，此时有

$$ |Pr\Big [ Exp^{ANEXT}_{A_{Anon,ETRS}} (\lambda)=win \Big ]-\frac{1}{2}|=|Pr[E_0]-Pr[E_t]| $$

上述概率可限制为

$$ |Pr[E_0]-Pr[E_t]|=|\sum^t_{j=1}Pr[E_{j-1]}]-Pr[E_j]|\leq t\cdot |Pr\Big [ Exp^{ANEXT}_{A_{Anon,ETRS}} (\lambda)=win \Big ]-\frac{1}{2}| $$

其中$t$为门限值

观察最后一个不等式，对于所有的$j$，定义$B$将$A$的所有查询转发给其ANEXT-ERS挑战者，当其从$A$处收到$(\mu^*,lad^*_0,lad^*_1)$时（图9第六行），规约提交签名请求（格式为$(\mu^*,R^*,i)$，其中$i$的范围在$lad^*_1.signers$的前$j-1$个实体和$lad^*_0.signers$中的后$t-j$个实体），然后令$\sigma_i$表示收到的响应

之后$B$向其ANEXT-ERS挑战者提交$(\mu^*,lad_0,lad_1)$，其中$lad_0=(i^{(0)}_j,R^*),lad_1=(i^{(1)}_j,R^*)$，这里$i^{(b)}_j$表示$lad_b$中的第$j$个签名者，令$\bar \sigma$表示挑战者返回的签名值，之后规约组合$t$个相同消息可链接可扩展签名$\{\sigma_i\}_{i\in [1,\dots,j-1,j+1,\dots,n]}\cup \{\bar \sigma\}$，得到签名值$\bar \sigma^*$，也即$A$的可扩展门限环签名挑战，规约当$b=0$时模拟$H_j$，$b=1$时模拟$H_{j+1}$，因此$B$可以利用能够区分一对连续混合的对手来破坏潜在SMLERS的匿名性

5.4 ETRS from Signatures of Knowledge and Discrete Log

本节介绍交互的可扩展门限环签名方案，方案支持$Join$操作并具有更紧凑的签名，方案得到的扩展门限签名的大小与门限$t$无关，但会随着$n'$（环大小的上限）线性增长（也即与环大小上届呈线性关系）

使用第4.3节的知识签名和离散对数中的SMLERS进行实例化，的话可以得到$t·|R|$为单位的线性大小的签名

Our Construction in a Nutshell

类似于图4的ERS构造，使用一个素数阶群$G$，利用两个公共元素$g,H\in G$生成签名，此外还需要利用关系$R_G$的知识签名，知识为$h$或$pk$的离散对数

令$n'\in N$表示环的大小的上界，通过类似于Shamir秘密共享的方式利用多项式的特征来实现门限功能：首先签名者选择$n'>0$对值对$(x_i,td_i)\in \Z_p\times G$（这些点称为陷门点），这些值对可以唯一确定一个阶为$n'$的多项式$f(x)$，满足$f(0)=dlog_g(H),f(x_i)=td_i$，其中$i\in [n']$

由于$dlog_g(H)$未知，签名者无法知道上述多项式的系数，不过插值多项式在$x$坐标固定且已知的情况下，签名者可以在指数位置进行插值来得到任意横坐标对应的点$(\hat x,y=g^{f(\hat x)})$

为了实现签名，且在后续签署statement（$Join$签名），签名者需要在该多项式上为一个随机点$(\hat x,y=g^{f(\hat x)})$构造一个关系$R_G$的知识签名，且满足$\hat x\notin \{x_i\}_{i\in [n']}$（也即这个点不能是构造上述多项式的点），关键在于：签名者不知道$y$的离散对数（也即$(\hat x,y)$不在陷门值$(x_i,g^{td_i})$中），因此知识签名必然满足关系$R_G$中的第二个子句（也即关于私钥的知识）

对于签名的扩展，任意参与方可以选择一个（剩余的）陷门点$(x_i,td_i)$并构造一个证明，通过满足第一个子句（证明$td_i$的知识）来生成关于关系$R_G$的证明，从而在环中包含任意的$pk$，然后将值对$(x_i,td_i)$从陷门列表中移除

如果$pk$的所有者稍后想要加入签名，$Extend$算法将$td_i$加密至$pk$，之后$pk$的所有者可以恢复$td_i$并将其返回到陷门列表中，然后用他自己的密钥生成新的知识签名

对于任意的域$\mathbb F$以及$\chi \sube \mathbb F,j\in \chi$，定义一个度为$|\chi|-1$拉氏多项式

$$ L_{(\chi,j)}(X)=\prod_{m\in \chi \backslash \{ j\}}\frac{X-m}{j-m}\in \mathbb F[X] $$

具体的过程图11所示（在$Sign$和$Join$中使用的$PolySign$子例，这里使用签名者的密钥作为$w$，并在随机值$\hat x$上调用，在$Extend$中使用$\hat x,w$分别作为评估点及其相应的陷门）

‍

本文的构造取代了$Combine$和$Join$，其中$Join$本质上以更高效的方式执行$Sign\&Combine$，此外还需要对5.2节中介绍的安全定义进行一些调整

首先定义如何在阶梯中处理$join$操作，若$action=Join$，则表示$input=(l',R,i)$，其中$l'$表示阶梯中已存在的签名值的索引，该签名由第$i$个签名者链接，具体而言，$ETRS.Process$检索$(R^{(l')},S^{(l')},\sigma^{(l')})$并检查$R$中所有的密钥已被初始化（密钥全部出现在了列表$L_{keys}$中），同时检查$R^{(l')}\cup \{i\}=R$，检查新签名者的索引出现在$R$但不包含在集合$S^{(l')}$中

若上述所有检查均通过，则表示签名者已加入集合$S$中，此时有$S=S^{(l')}\cup \{i\}$，然后将$join$操作处理为$\sigma \larr Join(\mu ,\{pk_j\}_{j\in R^{(l')}},sk_i,\sigma^{(l')})$，最后保存$(R,S,\sigma)$并返回$(R,t=|S|,\sigma)$

完整的签名算法如图12所示

对于方案的不可伪造性与图4（定理1）中描述的ERS方案的不可伪造性相关，但是涉及到更多的细节，具体可以看原文

Remark 4：恶意的扩展器可以通过不在新成员的公钥下加密正确的陷门来阻止新添加的环成员在后续加入签名
本文的安全性定义并未涉及到这一点，但排除此类攻击将是一个有趣且有价值的扩展
本文可以通过修改构造，通过添加零知识证明来证明加密值实际上是所讨论的$h$的离散对数，从而对其做出限制

‍

‍

‍

‍

References

$[1]$ Diego F. Aranha, Mathias Hall-Andersen, Anca Nitulescu, Elena Pagnin, Sophia Yakoubov:Count Me In! Extendability for Threshold Ring Signatures. Public Key Cryptography (2) 2022: 379-406