Threshold Signatures with Private Accountability

Abstract

现有的门限签名方案有两种形式：（i）完全私有，其中签名不透露生成签名的签名者集合的任何信息；和（ii）可问责，其中签名完全标识签名者集合

在本文中，我们提出了一种新的阈值签名，称为TAPS，它是隐私和责任的混合，从公众的角度来看，TAPS签名是完全私有的，但是，具有秘密跟踪密钥的实体可以将签名跟踪到生成签名的签名者的阈值

TAPS使一个组织能够保持其内部工作的隐私，同时确保签名者对其行为负责。我们构造了许多TAPS方案

首先，我们提出了一个通用构造，它从任何可问责的阈值签名构建TAPS，这种通用构造不是有效的，我们接下来将重点讨论基于标准假设的有效方案，我们基于Schnorr签名方案构建了两个有效的TAPS方案（在随机预言模型中），我们总结了一些与有效抽头相关的开放问题

1 Introduction

门限签名方案（原文参考文献$[30]$）仅当t个或更多方参与签名过程时，才允许由n个方组成的组对消息进行签名，有两种类型的门限签名方案

• Private Threshold Signature（PTS）：消息$m$上的签名值$\sigma$不会揭示阈值$t$，也不揭示生成签名的这$t$个签名方

此类方案中，即便敌手在其选择的消息上看到了一系列的签名，上述要求也成立

• Accountable Threshold Signaure（ATS）：消息$m$上的签名值$\sigma$会揭示参与生成签名的所有$t$个参与方的身份（意味着揭示了$t$）

此外，$t$个参与方不可能构成另一个集合，ARS方案于责任子群多重签名（ASM）的概念相关，但是本文采用ATS这个属于来比较两种类型的阈值签名

ATS又被称为可追踪秘密共享（Traceable Secret Sharing，TSS）

当需要隐藏组织的内部工作时，使用私有阈值签名（PTS）方案，比如Web Server可以在$n$台终端之间拆分Server的TLS密钥，使得至少需要$t$个终端才可以生成签名并完成握手，此时Server可以隐藏阈值$t$，以避免向敌手泄露攻击的终端数量和具体的终端，达到防止签名伪造的目的

可问责阈值签名（ATS）方案通常用于需要问责的金融应用中，比如银行的五位高管有三位需要授权一次转账行为，则若欺诈转账批准发生时，这三位授权者会被追责

简单的$(n,t)-ATS$方案时每个签名方在本地生成一个公私钥对，完整公钥为所有$n$个参与方的公钥的串联，当$t$个参与方需要签名时，各自使用自己的私钥签名，最终的签名值为所有$t$个签名值的串联，当$t$个签名均合法时，Verifier接受签名值

上述方案有优点，也有缺点，签名大小和验证时间在$t\lambda$中至少是线性的，且不能同时提供隐私和可追责两种功能

A New Type of Threshold Signature

本文引入了新的阈值签名方案，称为TAPS，在签名者数量保密的情况下提供可追责的功能

Threshold, Accountable, and Private Signature scheme（TAPS）具体如下

• 密钥生成算法生成一个公钥和$n$个私钥
• 签名算法生成包含$t$个参与方的关于消息$m$的签名值$\sigma$
• 验证算法利用公钥验证签名值，输出接受或拒绝

此外还有一个额外的密钥，称为追踪密钥$sk_t$，有该密钥的人可以可靠地将签名跟踪到生成其的参与方，为了安全起见，我们要求一组签名者不能通过欺骗跟踪过程来框架其他签名者

若追踪密钥公开，则TAPS和ATS方案没区别，若该密钥被破坏，则TAPS和PTS无区别，若受信任的追踪放（或多方共享的秘密）知道该密钥，则追踪方可以在欺诈交易的情况下追踪责任，同时将有关组织内部运作的所有其他信息保密

Applications

考虑一个用用公共分类帐上管理数字资产的组织，为了转移资产，必须在分类账上记录签名值，该组织可以通过要求$(n,t)$委托人签名来保护资产，此时可以用TAS方案，但是阈值$t$会暴露，或者用PTS方案，但是无法追责

TAPS方案可以给出更好的解决方案，此时组织可以保留追踪密钥，阈值和签名者可以保持私有，但是受托人需要为欺诈转账负责（$n,t$的值通常也较小，比如20）

Web Server也可以用TAPS，比如TLS密钥可以用$(n,t)$方式分散到$n$个终端，之后$t$个终端联合起来完成TLS的握手，此时追踪密钥必须离线保存，如果某一终端的密钥泄露，且被敌手利用，此时可以将追踪密钥应用于敌手的签名来识别被攻击终端所在的那一组终端

Constructing TAPS

利用一般零知识，可以从任意ATS方案构造TAPS，但是效率较低

虽然获得安全构造需要几个重要细节，但生成TAPS签名的高级方法如下

• 签名方生成消息$m$的ATS签名$\sigma$
• 使用公钥方案加密$\sigma$，得到密文$ct$
• 生成一个NIZK证明$\pi$，表示$ct$解密后是关于消息$m$的正确签名值
• 组合得到TAPS签名$\sigma'=(ct,\pi)$

若需要验证签名有效，则必须验证$\pi$是合法的，此时追踪密钥是用于解密$ct$的密钥，并对解密得到的$\sigma$运用ATS方案的追踪算法

完整结构看第四节

第五节介绍了从Schnorr签名中建立两个有效的TAPS方案，本文修改了泛型结构，使得零知识证明语句更为简单，然后利用Sigma协议或Bulletproof来证明该statement

对于较小的$n$，两种方案都具有合理的性能，随着$n$增大，Bulletproof产生的签名大约缩短了40倍

我们注意到，由于可追溯性和隐私要求，TAPS签名必须在隐藏阈值$t$的同时对签名仲裁进行编码，因此必须至少有$n$位长，第六节讨论了使用较弱的跟踪属性来放宽完全跟踪要求，我们称之为仲裁确认，其中追踪算法将追踪密钥和可疑仲裁集$C\subset[n]$作为输入，并确认$C$是否确实是生成给定签名的集合

如果上述较弱的确认性质足够，则Bulletproof可以获得对数大小的TAPS签名（当$n$很小时，确认可以通过测试所有可能的仲裁集，直到有一个通过确认，从而实现完全追踪）

A Different Perspective

TAPS系统可以描述为一个群签名方案，其中需要$t$个签名者代表该群签名，群签名方案中，群管理器为群中每个成员提供一个秘密签名密钥，任何群成员都可以代表群完成签名，而无需暴露签名者的身份，此外其还有一个追踪密钥，允许吃有该密钥的实体将给定的群签名追踪到发出该签名的单个成员

TAPS可以被视为该方案的广义化，TAPS方案中，至少需要群中的$t$个成员来生成群签名，签名不像公众暴露签名者的身份或$t$值，但利用追踪密钥可以将签名追踪到生成该签名值的$t$个成员

2 Preliminaries

Notation

• $\lambda \in \Z$：安全参数
• $x\larr y$：赋值
• $x\larr S$：从集合$S$中随机选一个值赋给$x$
• $y\larr \mathcal A(x)$
• $[n]$：表示集合$\{1,...,n\}$
• $\mathbb G$：阶位素数$q$的循环群，生成元为$g$
• $\Z_q$：表示环$\Z/q\Z$
• $\boldsymbol u\in \Z^m_q$：粗体表示长度为$m$的向量
• $\boldsymbol g^{\boldsymbol a}=\prod _i g_i^{a_i}$

Definition

• 公钥加密方案$PKE$：包含三个算法$(KeyGen,Enc,Dec)$，满足语义安全
• 承诺方案$COM$：包含两个算法$(Com,Vfy)$，满足无条件隐藏性和计算绑定性
• 签名方案$SIG$：包含三个算法$(KeyGen,Sign,Vfy)$，满足强不可伪造性
• 证明系统$(P,V)$：关于关系$\mathcal R$的证明系统，包含两个图灵机$(P,V)$，statement $x$和witness $w$，证明系统满足完美完备性，诚实Verifier零知识性，知识论证，非交互性

3 Threshold, Accountable, and Private Signatures

本节正式定义TAPS的概念，$n$表示允许的签名者的总数，$t$表示阈值，$\mathcal M$表示消息空间

The Combiner

$t$方希望在某一消息$m$上生成签名时，需要将其签名份额发送给组合方，组合方用$t$个份额生成完整签名，但是这里Combiner会知道$t$

由于Combiner必须信任该私有信息，因此我们允许组合其持有一个密钥$sk_c$，该密钥的保密学仅用于签名仲裁的保密性，方案的安全性不依赖于该密钥（若$sk_c$公开，则敌手无法用该密钥攻破方案的不可伪造性或可追责性）

该密钥会隐藏在安全游戏中

The Tracer

追踪实体拥有追踪密钥$sk_t$，允许其追踪一个合法的，以获得生成该签名的参与方，在不知道$sk_t$的情况下，恢复签名的参与方应当是困难的

根据上述定义，引入隐私可追责门限签名的定义，包含五个算法$(KeyGen,Sign,Combine,Vfy,Trace)$，其中

• $KeyGen(1^\lambda,n,t)\rarr (pk,(sk_1,...,sk_n),sk_c,sk_t)$：密钥生成算法
• $Sign(sk_i,m,C)\rarr \delta_i$：第$i$个签名方用其私钥$sk_i$对消息$m$进行签名，得到其签名值为$\delta_i$，这里签名集合$C$作为可选输入（部分构造中允许签名者知道签名人数$C\subseteq [n]$
• $Combine(sk_c,m,C,\{\delta_i\}_{i\in C})\rarr \sigma$：利用组合密钥，将$t$个签名者的签名值组合在一起，得到TAPS签名$\sigma$，算法需要验证$|C|=t$
• $Vfy(pk,m,\sigma)\rarr 0/1$：确定性算法，验证TAPS签名是否合法
• $Trace（sk_t,m,\sigma)\rarr C/fail$：利用$sk_t$、消息和签名值，输出签名者集合$C\subseteq [n]$，满足$|C|\geq t$，或者输出失败，若算法输出了集合$C$，则表明则该集合是一组签名者，其密钥必须用于生成$\sigma$

下文将Trace算法称为Tracer，此外对正确性而言，要求对于任意的$1\leq t\leq n$，和大小为$t$的集合$C\subseteq [n]$，消息$m\in \mathcal M$，和$KeyGen$算法生成的密钥，有下列等式成立

$$ \begin{aligned} &Pr[Vfy\big (pk,m,Combine(sk_c,m,C,\{Sign(sk_i,m,C)\}_{i\in C}\big)=1]=1\\ &Pr[Trace\big (sk_t,m,Combine(sk_c,m,C,\{Sign(sk_i,m,C)\}_{i\in C})\big)=C]=1 \end{aligned} $$

这里还有几个点需要注意

• 本文将$Sign$视为一个签名方本地运行的算法，而不是签名协议
• 本文的方案假设密钥生成算法$KeyGen$集中生成密钥，当然也可以分布式的生成，协议结束时，每个签名者都知道其密钥，只有Combiner知道$sk_c$，Tracer知道$sk_t$，$pk$为公开的，其余的任何信息任何一方都不知道
• 为何使用Tracer：Combiner知道哪些参与方贡献了签名份额来创建门限签名，如果一个系统有缺陷，可能会存在下列问题

当Combiner构造签名时，其会在数据库中记录用于生成该签名的参与方，在之后需要跟踪签名时，Combiner可以在其数据库中查找签名，同时显示生成该签名的参与方

若签名是强不可伪造的，则人们希望存在的唯一有效的签名是由诚实Combiner生成的，以便在Combiner的帮助下追踪各个生成签名的参与方

但是问题在于，恶意的签名者群体可能与Combiner勾结，从而生成无法追踪的签名（勾结后Combiner不将签名者记录到数据库中，或者需要追踪时先删库并阻止追踪）

我们的方案要求么个有效的签名都可以使用追踪密钥追踪到生成其的参与方，$sk_t$可以保存在安全的地方，只有在需要追踪时才可访问

TAPS的Combiner是无状态的

接下来定义TAPS的安全性、隐私和责任，方案必须满足选择消息攻击下的存在性不可伪造（EUF-CMA），此外方案还必须是隐私和可追责的

3.1 Unforgeability and Accountability

简单来说，TAPS方案必须满足EUF-CMA和可追责，这意味着对于给定的消息和签名对，具有$sk_t$的Tracer应当可以输出正确的签名集$C\subseteq[n]$

本文将此类同时满足不可伪造性和追责性的概念称为具有可追溯性的选择消息攻击下的存在性不可伪造，具体如下

• 不可伪造性（Unforgeability）：敌手控制小于$t$个参与方时不能构造一个合法的消息-签名对
• 可追责性（Accountability）：任意敌手控制大于等于$t$个腐败的参与方时无法生成一个合法的消息签名对，使其追踪到至少一个诚实的参与方

具体的安全游戏如下

这里预言机$O(C_j,m_j)$返回所有集合$C_j$内的参与方的签名份额$Sign\{(sk_i,m_j,C_j)\}_{i\in C_j}$

安全游戏第三步中敌手$\mathcal A_1$可以获取系统中所有的密钥，包括所有参与方的签名私钥、Combiner和Tracer的私钥，此外还可以通过请求预言机的方式获取到签名集合$C_j$中所有的签名者的签名份额

敌手首先向预言机请求一系列的$(C_i,m_i)$，然后敌手请求$O(C_j,m')$，收集对消息$m'$的签名份额，令集合$C'\larr \cup C_j$（如果没有对消息$m'$的预言机请求，则令$C'$为空集）

接下来敌手需要伪造一个消息签名对$(m',\sigma')$，且追踪算法会将该签名追踪到一个集合，记为$C_t$，如果$(m',\sigma')$可以通过验证算法的验证，且下列两个条件中的任意一个成立，则意味着敌手赢得了安全游戏

1. $C_t\nsubseteq (C\cup C')$
2. 追踪算法返回$fail$

这里条件1表示消息签名对追踪到了$C\cup C'$以外的签名者，条件2表示追踪算法失败（失败意味着签名验证不通过，或者集合$C_t\notin [n]$）

如果敌手赢得上述安全游戏的概率可忽略，则方案满足可追责性和不可伪造性

3.2 Privacy

定义TAPS的隐私，阈值签名方案的隐私通常通过要求消息$m$上的阈值签名与由某些标准的签名方案上生成的签名不可区分来定义

上述要求确保了阈值签名不会显示任何有关阈值和生成签名的参与方的信息

TAPS可能不是从非阈值方案导出的，因此上述安全定义不好使，不过本文将隐私定义为TAPS的固有属性，且本文的定义同样适用于PTS方案，具体如下

• Privacy against the public：针对公众的隐私性，任何只知道$pk$的参与方，在获得一系列的消息-签名对后，不能知道任何关于门限$t$和签名者集合的信息
• Privacy against signers：针对来自签名者内部的隐私性，所有集合中的签名者合作（同时拥有$pk$），并获得一系列的消息-签名对后，不能确定哪些签名者参与了这些签名的创建（此类情况下阈值$t$不在保密，但是仍然无法知道具体参与贡献的签名者）

上述两个安全性定义分别对应于图2和图3的安全游戏

上述安全游戏表示针对针对公众的隐私性，安全游戏首先选择一个随机比特$b$，由$\mathcal A_0$生成两个门限值$t_0,t_1\in [n]$，然后为门限值$t_b$生成各个签名方的公私钥对

接下来敌手$\mathcal A_1$可以请求两个预言机，$\mathcal O_1(C_1,C_2,m)$返回集合$C_b$的组合签名，$\mathcal O_2(m,\sigma)$返回$(m,\sigma)$的追踪结果，这里对敌手$\mathcal A_1$有一个限制：如果$\mathcal A_1$通过$\mathcal O_1$请求了消息$m$的组合签名，则其不能通过$\mathcal O_2$追踪该签名值

敌手的目的是通过公私钥对和两个预言机，输出比特$b'$，若有$b=b'$则表示敌手赢得了安全游戏

若敌手在安全参数$\lambda$下赢得上述安全游戏的概率可忽略，则表示方案满足针对公众的隐私性

针对签名者的隐私性和上一个安全游戏类似，不过第四步中允许敌手$\mathcal A_1$获取所有签名方的签名私钥$\{sk_1,...,sk_n\}$，其余条件和图2中的安全游戏相同

若此时敌手在安全参数$\lambda$下赢得上述安全游戏的概率可忽略，则表示方案满足针对签名者的隐私性

这里有一点需要注意，就是随机化签名，上述图2和图3的安全游戏要求签名生成过程是一个随机化的过程，也即对于相同的消息$m$和签名集合$C$，若调用两次$Combine$算法时，其应当以极高的概率产生不同的签名值，否则敌手可以赢得安全游戏

3.3 Accountable Threshold Schemes (ATS)

对于完整性而言，PTS方案和ATS方案的标准概念时TAPS的特殊情况，接下来为了获得ATS，我们对TAPS的方案提出了两个语法要求

• 在ATS中，追踪密钥是公开的，这意味着任何人都可以将有效的消息签名对追踪到生成其的参与方，我们要求TAPS的追踪密钥$sk_t$等于公钥$pk$来达成这一点
• ATS中，Combiner不为可信方，且不保存秘密，因此我们要求$sk_c$同样等于公钥$pk$

为了清楚期间，无论何时使用ATS，我们都将$sk_t,sk_c$作为TAPS算法的显式输入和输出

引出下列定义

• Def 8：一个可追责的门限签名方案（ATS）为一种特殊的TAPS方案，其中$sk_t,sk_c$均等于公钥$pk$

该方案若满足Def 6的的安全游戏，则其为可追责且不可伪造的

接下来定义私有门限签名（PTS），引出下列定义

• Def 9：私有门限签名方案（PTS）为TAPS的一个特例，其中$Trace$算法总是返回$fail$，且修改Def 5中队TAPS的正确性要求（删除等式(2)）

该方案若满足Def 7的隐私性和Def 6的一次修改不可伪造性，则其为安全的

4 A Generic Construction via an Encrypted ATS

本节介绍TAPS方案的通用构造，具体使用了下列五个构建块

• 安全ATS方案（Def 8）：记为$ATS=(KeyGen,Sign,Combine,Vfy,Trace)$
• 语义安全的公钥加密方案（Def 1）：记为$PKE=(KeyGen,Enc,Dec)$，其消息空间为ATS签名算法输出的签名空间
• 满足绑定性和隐藏性的承诺方案：记为$COM=(Commit,Vfy)$，其中$Commit$算法的随机性记为$r$
• 强不可伪造性签名方案：记为$Sig=(KeyGen,Sign,Vfy)$
• 非交互式零知识知识论证：记为$(P,V)$，利用FS变换在RO模型下转化为非交互的

The Generic TAPS Scheme

通用TAPS方案如下图所示

本文的构造中，消息$m$的TAPS签名为一个三元组$\sigma=(ct,\pi,tg)$，其中

• $ct$：表示利用公钥加密方案加密ATS方案的签名值$\sigma_m$后得到的结果，加密密钥为$pk_t$
• $\pi$：零知识证明串，表明$ct$解密后确实是$m$的ATS签名值
• $tg$：Combiner关于三元组$(m,ct,\pi)$的签名

由于ATS公钥可以揭示阈值$t$，从而违反TAPS的隐私要求，因此TAPS的公钥不能包含ATS的公钥，取而代之的做法是包含ATS公钥的隐藏承诺

接下来有三个点

• 正确性：上述方案的而正确性在ATS、承诺方案、加密方案、签名方案和证明系统均正确时正确
• 效率：采用简洁承诺方案时，公钥很短，而采用zk-SNARK作为证明系统时，ATS的签名开销也很短，这两个参数的长度均取决于安全参数

此外，签名验证时间主要由SNARK验证时间决定（为参与签名的所有人$n$的对数阶），但是Combiner的工作比较复杂，因为需要生成复杂的zk-SNARK证明，此外，zk-SNARK证明系统依赖于强复杂性假设，本文通过引入RO模型下的DDH假设来改善Combiner的效率

• 安全性、隐私和可追责性：假设ATS方案为安全的可追责门限签名方案，PKE为语义安全的，证明系统$(P,V)$为HVZK且为知识论证，承诺方案COM满足隐藏性和绑定性，SIG满足强不可伪造性，则TAPS方案为不可伪造、可追责且满足隐私性

这里有一点需要注意，注意图2和图3的安全游戏，敌手可以访问一个任意消息签名对的追踪预言机，本文的构造中允许敌手可以对加密方案PKE发起选择密文攻击，但是Thm 1只要求PKE为语义安全的，而不要求是CCA安全的，这在下文中构建更有效地TAPS方案是，队PKE的弱安全性需求变得很重要，为了防止CCA攻击，我们依赖于每个TAPS签名中包含的Combiner签名，该签名确保了敌手不能用Combiner输出TAPS签名以外的任何东西来调用追踪预言机

5 An Efficient TAPS from Schnorr Signatures

本阶级与Schnorr签名方案在随机预言机模型中构造一个安全的TAPS，该构造比直接将上一节中的通用构造应用到Schnorr ATS中有效得多

通过利用Schnorr的代数特性，可以极大简化Combiner在签名时需要证明的零知识statement，从而优化方案

方案基于一个阶为素数$q$的群$\mathbb G$，其中DH问题时困难的，令$g,h$为$\mathbb G$中不同的两个生成元，并记Hash函数$H: PK\times \mathbb G\times \mathcal M\rarr \Z_q$，并将该Hash函数视为Random Oracle

5.1 A Review of the Schnorr ATS Schemes

先回顾一下Schnorr方案

• $KeyGen(\lambda)$：返回私钥$sk\larr \Z_q$，公钥$pk\larr g^{sk}$
• $Sign(sk,m)$：随机选择$r\larr \Z_q$，计算$R\larr g^r,c\larr H(pk,R,m)\in \Z_q$，然后计算$z\larr r+sk\cdot c\in \Z_q$，输出签名值$\sigma\larr (R,z)$
• $Vfy(pk,m,\sigma)$：计算$c\larr H(pk,R,m)\in \Z_q$，当且仅当$g^z=pk^c\cdot R$时接受签名

本文提出的TAPS方案基于现有的Schnorr可追责门限签名（原文参考文献$[49,50,53]$），利用本文的方案，改进的ATS方案如下

• $KeyGen(\lambda,n,t)$：随机选择$sk_1,...,sk_n\larr \Z_q$，计算对应各个参与方的公钥$\forall i\in [n],pk_i\larr g^{sk_i}$，输出公钥$pk=(pk_1,...,pk_n),sk=(sk_1,...,sk_n)$

ATS方案中，Combiner密钥$sk_c$和追踪密钥$sk_t$均为$pk$

• $Sign(sk_i,m,C)$：该算法在Combiner和第$i$个签名方之间完成，算法结束后Combiner从第$i$个参与方处获得$\delta_i=(R_1,z_i)$，满足$g^{z_i}=pk_i^c\cdot R_i$，其中$c\larr H(pk,R,m)\in \Z_q$

这里$R=\prod_{i\in C}R_i$

• $Combine(pk,m,C,\{\delta_i\}_{i\in C})$：若$|C|\neq t$，直接终止算法，然后解析所有的$\delta_i$，计算$z\larr \sum_{i\in C}z_i,R=\prod_{i\in C}R_i$，算法输出签名值$\sigma\larr (R,z,C)$

利用公钥，可以验证$(R,z)$为一个合法的关于消息$m$的签名，因为$pk_C\larr\prod_{i\in C}pk_i$

• $Vfy(pk,m,\sigma)$：解析公$pk$和签名$\sigma$，若$|C|\neq t$则拒绝签名，然后当且仅当$g^z=pk^c_C\cdot R$时接受签名
• $Trace(pk,m,\sigma)$：解析$\sigma$，运行$Vfy(pk,m,\sigma)$，若验证通过则输出$C$，否则输出$fail$

Schnorr ATS论文$[49,50,53]$描述了实例化签名协议的不同方法，他们使用不同的安全模型证明了结果Schnorr ATS方案的安全性，这里，我们将签名协议视为一个黑盒，并依赖于以下假设

• Assumption 1：如Def 8所示，上述Schnorr ATS是一种安全的ATS方案

5.2 An Efficient Schnorr TAPS

接下来的构造基于Schnorr的TAPS方案，若遵循第四节的一般构造，则Combiner需要加密整个Schnorr签名$(R,z)$，且需要为复杂的关系生成零知识证明，尤其是需要证明加密的Schnorr签名是有效的， 这样会使得在零知识下很难有效的完成证明

但是注意到，从公众看来，$R$是群中随机元素的乘积，因此$R$与签名者集合$C$相互独立，从而TAPS方案中$R$可以揭示，而不影响$C$的隐私性，即便拥有所有签名密钥的敌手也无法从$R$中了解$C$，我们只需要加密$z$即可

此时问题转变为了用零知识证明来证明明文$R$和密文$z$是关于秘密签名者集合$C$的合法的Schnorr签名

The Scheme

本文的Schnorr TAPS方案基于5.1节描述的Schnorr ATS方案，并依赖于Assumption 1，

完整的TAPS方案如图5所示，步骤4中的组合算法为图6中的关系$R_S$生成了零知识证明，两个有效的证明系统用于该关系（5.3和5.4节给出了两个关于该关系的高效的证明系统）

注意到跟踪算法的第四步，需要找到大小为$t$的集合$C\in [n]$，且该集合满足某一性质，若$n$与安全参数呈对数关系，则可以通过对$n$的所有大小为$t$的子集穷举搜索来找到集合$C$，对于较大的$n$，第5.3和5.4节介绍了如何找到$C$

假设ATS Schnorr方案、签名方案和关于$R_S$的证明系统是正确的，则上述方案是正确的

5.3 A Sigma Protocol Proof for $R_S$

对于上述图6，仍然需要构造一个有效的非交互式零知识论证，本节构造了一个Sigma协议，下一节使用Bulletproof技术构造一个交互式的协议，可以用FS变换转变成非交互式的

设$g,h,h_1,...,h_n\in\mathbb G$为群中不同的个生成元，为了证明如图6中的关系$R_S$的一个witness，构造下列协议

• Protocol 1

1. Prover选择$\gamma \larr \Z_q$，对$\gamma$及其比特表示$(b_1,...b_n)$进行承诺，得到如下

$$ v_0\larr g^\gamma\\ v_1\larr g^{b_1}h_1^\gamma\\ ...\\ v_n\larr g^{b_n}h_n^\gamma $$

Prover将$(v_0,...,v_n)$发送给Verifier

注意到对于任意的$i\in [n]$，可以将$(v_0,v_i)$视为以$h_i$为密钥的对$b_i$的ElGamal加密，其中$v_0$会被用于后续的追踪

1. Verifier选择随即挑战$\alpha\larr \Z_q$并发送给Prover
2. Prover对于所有的$i\in[n]$，计算$\phi_i\larr \alpha_i\gamma(1-b_i)$
3. Prover利用Sigma协议证明图7中关于关系$R_S$的witness$(z,\rho,\psi,\gamma,b_1,...,b_n,\phi_1,...,\phi_n)$

若DDH假设在群$\mathbb G$上困难，且$n/q$可忽略，则Protocol 1为HVZK关于关系$R_S$的知识论证

这里有一点需要注意，如何完成高效追踪，回顾图5，追踪的目的是找到一个集合大小为$t$的$C\subseteq[n]$，满足$g^{z'}=(\prod _{i\in C}pk_i)^c\cdot R$，利用Protocol 1，追踪算法可以直接解密Combiner的ElGamal承诺，得到$b_1,...,b_n$，从而完成高效追踪（$b_1,...,b_n$表示了集合$C$），扩展图5的算法，可以得到下列步骤

1. 对于所有的$i\in [n]$，选择$\tau_i\larr \Z_q$，令$h_i\larr g^{\tau_i}$
2. 计算论证追踪密钥$aug-sk_t\larr (sk_t,\tau_1,...,\tau_n)$
3. 计算论证组合密钥$aug-sk_c\larr (sk_c,h_1,...,h_n)$
4. 计算论证公钥$aug-pk\larr(pk,h_1,...,h_n)$

此时Combiner和Verifier在其论证密钥中使用$h_1,...,h_n$，并利用Protocol 1产生和验证关系$R_S$的证明，证明中包含ElGamal承诺$(v_0,v_1,...,v_n)$，追踪算法可以利用密钥$\tau_1,...,\tau_n$，通过解密ElGamal密文来得到$b_1,...,b_n$

Protocol 1的合理性确保了得到的结果正确表示了集合$C$，注意到$aug-pk$包含了$2n+4$个群元素

5.4 A Bulletproofs Protocol Proof for $R_S$

图6中的关系$R_S$的Sigma协议对现实世界中数量较少的签名者而言是可行的，但是如果签名者的数量$n$很大，会导致最后得到的证明大小也很大，我们可以用zk-SNARK来减少证明大小，但是这会带来两个问题

• 证明和验证过程会很慢，因为图6中的zk-SNARK协议需要进行指数运算
• 此外还会丢失追踪算法的高效性

不过利用Bulletproof可以解决上述问题，或者直接在$[2]$中使用压缩的Sigma协议来避免这些问题，因为指数运算实际上是可以有效处理的，其次，我们可以使用更短的TAPS签名来保持高效追踪，接下来看一下如何处理

令$\mathbb G$的阶为$q$，令$\boldsymbol a=(a_1,...,a_n)$为生成元向量，同时记$\boldsymbol w\in \Z^n_q$，满足

$$ \boldsymbol a^{\boldsymbol w}=\prod^n_{i=1}a_i^{w_i} $$

注意到Bulletproof是HVZK证明系统，因此可以证明witness $\boldsymbol w\in \Z^n_q$，满足下列关系

$$ R_{BP}=\{(P,\boldsymbol a\in \mathbb G^n,u\in\mathbb G);\boldsymbol w\in\Z^n_q\} \ \ iff\ P(w)=1\wedge\boldsymbol a^{\boldsymbol w} $$

其中$P$表示R1CS系统（也即$P$为一个矩阵三元组），本文使用R1CS而非算术电路来表示关系$R_{BP}$

Bulletproof是简洁的，仅包含$2\lceil \log_2(n+l)\rceil$个群元素和两个$\Z_q$中的元素，对于一个可令人信服的Prover $P^*$，存在一个抽取器输出一个$\boldsymbol w\in \Z^n_q$，满足

1. $\boldsymbol w$为一个合法的witness
2. $\boldsymbol w$为一个生成元向量的非平凡关系（$\boldsymbol a^{\boldsymbol w}=1$)

若离散对数在群$\mathbb G$上市困难的，且$\boldsymbol a$为随机选择的生成元向量，则一个高效的Prover不能找到一个$\boldsymbol w$，使得第二种情况成立，因此Bulletproof为知识论证

Shorter Proofs with Efficient Tracing

本文的完整版本展示了利用Bulletproof可以得到一个关于关系$R_S$的对数大小的证明（如图6所示），但是这么做会损失追踪的效率，注意到图5中，追踪需要找到一个大小为$t$的集合$C\subseteq[n]$，对于较小的$n$而言，我们可以遍历$n$中所有大小为$t$的子集，但是$n$很大的时候就不好了

此时我们可以令向量$(b_1,...,b_n)\in \{0,1\}^n$来表示集合$C$，5.3节我们对该向量进行加密，并在签名中加入$n+1$个群元素$(v_0,...,v_n)$，此时追踪算法可以将其视为ElGamal加密，利用密钥对其解密来高效找到集合C

利用Bulletproof技术，我们可以压缩向量$(b_1,...,b_n)$的承诺，然后扩展Bulletproof关系以验证每一批承诺都是正确的

举个例子，比如说压缩大小$e=40$，假设$e|n$，然后扩展图5中的$KeyGen$算法，加入下列步骤

1. 对于$i\in [n/e]$，选择$\tau_i\larr \Z_q$，并计算$h_i\larr g^{\tau_i}$
2. 论证追踪密钥$aug-sk_t\larr (sk_t,\tau_1,...,\tau_{n/e})$
3. 论证Combiner密钥$aug-sk_c\larr (sk_c,h_1,...,h_{n/e})$
4. 论证公钥$aug-pk\larr (pk,h_1,...,h_{n/e})$

接下来通过添加步骤0来扩展图6中的关系$R_S$的Prover，如下

将$n$分为$n/e$个部分，记为$0\leq B_1,...,B_{n/e}<2^e$，如下

$$ \begin{aligned} &B_1\larr b_1+2b_2+4b_3+...+2^eb_e\\ &B_2\larr b_{e+1}+2b_{e+2}+...+2^eb_{2e}\\ &...\\ &B_{n/e}\larr b_{n-e+1}+2b_{n-e+2}+..+2^eb_n \end{aligned} $$

选择$\gamma \larr \Z_q$，计算

$$ \begin{aligned} &v_0\larr g^\gamma\\ &v_1\larr g^{B_1}h_1^\gamma\\ &...\\ &v_{n/e}\larr g^{B_{n/e}}h^\gamma_{n/e} \end{aligned} $$

将$v_0,...,v_{n/e}$发送给Verifier，注意到$(v_0,v_i)$均为$g^{B_i}$的ElGamal在公钥$h_i$下的加密

最后，验证$v_0,...,v_{n/e}$构造正确即可，此方法进一步的缩小了证明大小，最终得到的TAPS签名仅需要附加$(n/e)+1$个群元素即可

此时对于给定的个签名，追踪算法利用$\tau_i$解密$(v_0,v_i)$，可以得到$(g^{B_1},...,g^{B_{n/e}})$，通过基于$g$的计算离散对数可以得到$(B_1,...,B_{n/e})$（注意这里与群上的离散对数困难问题不冲突，因为每个$B_i$的取值都是2的幂的和，因此计算离散对数的期望步骤为$2^{e/2}$次群运算）

关系$R_S$的论证系统的合理性确保了追踪算法最终得到的$(b_1,...,b_n)$确实表示了集合$C$

6 Extensions

Shorter Public Keys

虽然在我们的Schnorr构造中，公钥的大小以n线性增长，但有几种方法可以缩小公钥

首先，公钥可以由对线性大小公钥的短约束承诺代替，并且完整公钥可以包含在每个签名中，这以扩展签名为代价缩小了公钥

或者，公钥和签名都可以通过使公钥成为零知识证明声明中的证人来保持简短，如在一般构造中所做的那样（图4），然而，这样做的代价是组Combiner需要证明的语句的复杂性增加

Shorter Signatures Using Tracing Confirmation

跟踪TAPS签名到签名仲裁的需要意味着TAPS签名必须编码签名集，因此必须至少为$n,t$的组合数的对数阶，可以通过放宽这一要求来设计更短的TAPS签名

比如将跟踪算法替换为仲裁确认算法，该确认算法将签名仲裁集$C$、秘密追踪密钥$sk_t$和一对消息签名对$(m,\sigma)$作为输入，若集合$C$确实是生成$\sigma$的集合，则输出$true$，此方案的安全性适用于第三节介绍的安全性

由于签名不再需要对法定人数集进行编码，这使得我们可以构造签名大小独立于参与方数量的TAPS，比如使用图6中关于关系$R_S$的恒定大小zk-SNARK

本文介绍的Buletproof构造可以直接实现具有法定人数确认和对数大小的TAPS

Stronger Privacy Against Signers

图3中的针对签名者的隐私游戏确保签名者的私钥不能用于将TAPS签名链接到创建它的仲裁，但是可能有助于创建TAPS签名$\sigma$的仲裁集利用其签名时采用的随机性在之后对$\sigma$进行识别

许多Schnorr私有阈值签名方案（PTS）也如此，创建签名的仲裁可以识别该签名，如果有需要，可以增强本文的Schnorr TAPS结构，以便TAPS签名不能被对签名生成有贡献的签名者识别，此时Combiner只需要盲取数量$R\in \mathbb G$，并调整图6中的关系即可

A Construction from the BLS Signature Scheme

在本文中，我们重点讨论了Schnorr签名方案的一个TAPS。也可以从BLS签名方案构建TAPS

Beyond Threshold: Supporting Monotone Access Structures

虽然阈值访问结构在实践中被广泛使用，但我们的构造推广到支持更一般的单调访问结构，例如，可以要求签名者的法定人数包含来自一组签名者$t_1$和来自另一组签名器$t_2$

7 Conclusion and Future Work

在这项工作中，我们提出了TAPS，这是一种新的阈值签名原语，可确保问责制和隐私，虽然文献中存在可问责阈值方案和私有阈值方案的概念，但我们的工作朝着同时定义具有这两个属性的原语迈出了一步，我们希望未来的工作能够产生具有更短签名和公钥的TAPS方案

我们的通用构造有一个短公钥：公钥只是对ATS公钥的承诺，因此其大小与参与方数量n无关，然而，我们基于Schnorr的系统具有高效跟踪，需要线性大小的公钥，一个重要的研究方向是设计一个有效的TAPS，该抽头依赖于标准假设，其中公钥的大小独立于n

更有效TAPS的一个可能途径是pk是Merkle树的根，其叶是n个签名者的公钥，然后Combiner输出的零知识证明将是一个简洁的非交互式零知识论证（zk-SNARK），证明n个签名者中有t个参与签名

一个相关方向是采用Dodis等人（原文参考文献$[31]$）的方法，通过累加器方案定义公钥，然后，签名证明$t$个签名者知道累加器中$t$个公钥对应的秘密密钥

然而，设计这样一个符合我们问责制概念的方案仍然是一个开放的问题，未来工作的另一个方向是提高Schnorr TAPS的验证效率，在n较小的情况下，如金融交易，验证Schnorr构造的线性时间成本是可以接受的，对于较大的n，成本可能过高，未来的工作可以考虑支持完全跟踪的其他构造，但使用更快的验证器

总结

本文基于Schnorr签名方案，设计了一个同时满足可追责性和隐私性的门限签名方案，其中隐私性作为一个附加属性，可以同时满足针对公众的隐私性和针对签名者内部的隐私性

签名方案满足选择消息攻击下的不可伪造性，且在随机预言机模型中为可证明安全的

文章给出了生成签名过程中需要的零知识关系，并给出了两种实现方式，一种基于Sigma协议实现，一种基于Bulletproof协议实现，都可以转化为非交互式的协议并实现高效追踪

后记

不记得啥时候看的了，这段时间写代码写博客搞忘了，或许是上一次和boss吃饭的前几天看的，那应该是教师节中秋节那一周

前后也就看了两三天吧，看完之后本来打算发篇博的，被boss拽出去吃饭了，吃一半一时兴起和boss说了这个事儿，于是就打算拿这个方案放到一个具体的场景中，拿去报了作品赛

然后后来就是每天抓紧写方案、写代码、还和师弟每天在lab改报告，不过最后也是在极限时间内肝完了

一个感觉非常有前景的方案，毕竟门限签名确实用的很多，如果用在密钥管理，门限签名这种场景的话，追责性和隐私性都很重要

作者后续提到了可以用BLS等其他方案实现，自己想了一下可不可以在零知识那一块换成Groth16，毕竟双线性对的验证效率极高，打算后续再改改投出去，或者直接专利或者毕设

References

$[1]$ Boneh, D. and Komlo, C.:Threshold Signatures with Private Accountability CRYPTO 2022
$[2]$ Attema, T., Cramer, R.: Compressed Σ-protocol theory and practical application to plug & play secure algorithmics. In: Micciancio, D., Ristenpart, T. (eds.)CRYPTO 2020. LNCS, vol. 12172, pp. 513–543. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-56877-1 18