论文笔记：Extendability for Threshold Ring Signatures
《Count Me In! Extendability for Threshold Ring Signatures》PKC2022
作者演讲 & slices（语速很快，顺便练练听力......）
https://www.bilibili.com/video/BV1nY411G7yK/?spm_id_from=333.337.search-card.all.click&vd_source=740f82f155391112395641cab3227dc8
目录
Introduction
Preliminaries
Threshold Ring Signatures
Signatures of Knowledge
Extendable Ring Signatures(ERS)
Syntax
Security Model
Unforgeability
Anonymous Extendability
ERS from Signatures of Knowledge and Discrete Log编辑
Same-Message Linkable Extendable Ring Signatures
Syntax
Security Model
Same-Message One-More Linkability
Cross-Message Unlinkability
Secure SMLERS
SMLERS from Signatures of Knowledge and Discrete Log
将ERS转换为SMLERS的方法
Extendable Threshold Ring Signatures
Syntex
Security Model
Secure ETRS
Unforgeability for ETRS编辑
Anonymity for ETRS编辑
Strong Anonymous Extendability for ETRS
通用编译方案
ETRS from Signatures of Knowledge and Discrete Log编辑
Introduction
Extendability的概念：扩大t-out-of-n门限环签名的环规模
动机
目标：为了实现匿名性，希望门限签名生成过程中签名者之间是非交互的。
现状：存在非交互式签名的阈值环签名，签名者在本地产生部分签名，然后聚合这些签名。
缺陷：所有签名者必须同意他们所代表的组，这隐含地假设了他们之间的某种协调。
解决：非交互可扩展环的规模，扩展过程不需要签名者参与。
贡献
Preliminaries
Threshold Ring Signatures
- 非交互TRS：
输出对签名者的部分签名；的输入中加入门限；将个部分签名合并成一个TRS ，这个算法可以被第三方运行，因为它不需要签名者的秘密信息。
- 另一种稍弱的解决：
签名在签名者之间传递，每个签名者接收签名，连接自己的签名，传递签名（只进行一次）；
Signatures of Knowledge
通过用实例或声明（statement）替换公钥来泛化数字签名，在NP语言中。只有当签名者拥有声明的有效证人时，她才能为消息生成有效签名。
一个二元关系的SOK定义为PPT算法的元组:
- : (message , statement , witness )
- : trapdoor
提前看一下下面用到的关系初始化参数和签名：
SoK方案应该满足correctness, simulatability, extractability
Extendable Ring Signatures(ERS)
Syntax
一个附加的算法Extend，允许任何第三方扩大给定签名的潜在签名者的环
：输入原签名的环公钥集合，和另一组环公钥，输出环为的新签名
按某种顺序扩展签名:（签名者的身份+rings of签名者标识符集合）
算法:用在环上产生消息的签名，并按顺序扩展这个签名（使用存储在中的密钥）
Security Model
Unforgeability
排除两种普通攻击：
Oracles:
如果查询者没有指定公钥，正常生成身份-公私钥对并存储在列表中；否则将指定的身份-公钥存储在列表中，因为无法获得私钥，所以缺省；由于认为查询者知道对应的，所以视为腐化密钥对加入中
代表视为已被腐化的密钥对，包括通过查询获得的，和敌手通过将已知公钥登记给。
查询方需要是未被腐化的，所以Oracle可以通过查找到生成签名，加入.
Unforgeability for ERS
一个可扩展的环签名方案ERS被认为是不可伪造的，如果任意的PPT敌手都参加（以上的cmEUF）不可伪造实验，而成功的概率可以忽略不计。
Anonymous Extendability
我们定义了一个通用的实验，以支持2种不同的匿名可扩展性:
- 标准匿名概念，其中不发生扩展;
- 强匿名可扩展性，不可能知道一个签名经历了什么扩展序列。
可扩展环签名的匿名性和匿名可扩展性
Oracles:OSign, OKeyGen，OCorrupt同上
（line 6）生成两个不同的扩展序列，如果敌手能够区分签名是从哪个序列扩展来的，敌手胜利
生成挑战签名的过程：排除身份被腐化的可能（line 3）；分别对同一消息以不同的序列扩展签名。
注意以不同的序列生成的两个扩张签名，所使用的签名集合最终相同（即，是同一个消息在同一个环中的签名）。
Anonymity for ERS（标准匿名性）
可扩展环签名方案被称为匿名的，如果所有的PPT敌手都参与了匿名可扩展性实验（如上），并向挑战者提交种类为的梯子，认为的成功概率近似于随机猜测，可以忽略不计。
- 对于标准匿名性来说，不发生扩展，所以输出的和都只包含一个相同的环，只有签名者身份不同。敌手猜对的概率等同于掷硬币。
Strong Anonymous Extendability for ERS
可扩展环签名方案被认为是强匿名可扩展的，如果所有的PPT对手A都参与匿名可扩展实验（如上），并且成功的概率可以忽略不计。
- 注意，强可扩展性意味着扩展环签名的行为是无缝的，也就是说，攻击者无法区分新环签名(由Sign返回)和它的扩展(由Extend返回)。这表示的强可扩展性情况。
ERS from Signatures of Knowledge and Discrete Log
这个关系要求witness是或者对应的离散对数（即）。
line 2表示：
line 4-5: statement , witness
扩展过程与签名大致相同，但使用了另一种witness.
（这个签名好长，而且规模与扩展的次数有关）
验证过程
定理1假设SoK是安全的方案，群上的离散对数问题困难，则以上ERS方案满足正确性、不可伪造性、强匿名可扩展性
Same-Message Linkable Extendable Ring Signatures
Syntax
同消息可链接环签名方案(SMLRS)是一种环签名方案，它还允许任何第三方公开识别(链接)同一签署人是否为同一消息生成了两个签名。这意味着，如果同一方在同一消息上签名两次，即使是不同的环，两个签名也可以被任何第三方链接。
前五种算法同上，Link算法允许任何验证者确定特定消息上的两个签名是否由同一个签名者产生
注意，如果签名被链接，链接不一定会揭示共同签名者的身份。
SMLERS方案的正确性，它包含两个语句:
Security Model
增加的性质：
Same-Message One-More Linkability
没有一组(t−1)腐化的签名者可以为相同的消息产生t个签名，而这些消息是成对不链接的
signing, key generation and corruption oracles同上，除了算法ERS换成SMLERS
line 4:敌手输出一组t对消息的签名-环对；
line 5: 如果是已经被查询过的签名的扩展环，lose
line 6：如果输出的t个签名的所有环中被腐坏的成员大于等于t个，lose（因为那样肯定能生成）
line 7: 生成的签名不合法，lose
line 8: 如果这些生成的签名两两不可链接，win；否则lose
Cross-Message Unlinkability
任何敌手都无法确定不同消息的两个签名是否由同一签名者产生。
line 5：对于敌手指定的两个身份-消息生成的签名，敌手无法分辨。
line 9：如果签名者任意查询过的签名，lose
（误，line 8 应是）
对于敌手指定的两组消息，产生签名的过程
Secure SMLERS
定理：同消息可链接可扩展环签名方案(SMLERS)在满足正确性、Same-Message One-More Linkability和Cross-Message Unlinkability的前提下是安全的
SMLERS from Signatures of Knowledge and Discrete Log
将ERS转换为SMLERS的方法
- 首先采用一种稍微不同的关系
值得注意的是，最后一个AND不仅要求签名者证明秘密密钥的知识，而且它还强制使用相同的秘密密钥来生成链接性标记。SMLERS的SoK是关于新关系的
- 其次，修改了原ERS构造中的Sign算法，它额外计算，并将加入作为签名的一部分。（可注意到，标记仅与消息和签名方私钥有关，且不泄露它们的信息）
- 最后，算法Link简单地比较两个签名中的可链接性标记。如果它们相等，则返回链接，否则返回不链接。
该方案只需对ERS的不可伪造性（分别地，匿名可扩展性）的证明进行少量修改，就可以证明该方案是Same-Message One-More Linkability（分别地，Cross-Message Unlinkability）的。
Extendable Threshold Ring Signatures
可扩展门限环签名方案还具有以下特性:
给定任意两个门限签名，对相同的信息和相同的环进行验证，任何人都可以将签名非交互组合得到。新签名也是一个门限环签名，它的门限等于对两个签名中至少一个作出贡献的唯一签名者的总数。这个功能由提供
对于门限为t的环，给定消息上的签名，任何人都可以将非交互地转换为具有相同阈值的同一消息上的签名，但使用更大的环。此功能由提供。
Syntex
ETRS由6个算法组成
- . 其中，分别是两个签名中隐含的签名者的集合
对于更具互动性的语法，我们可以用操作替换执行。
对于下面的定义，使用梯子lad的方式与在ERS上下文中使用的方式略有不同。lad将包含表单的元组序列。第一个组件可以取的值.
- ，其中是同一个环中两个签名的索引
- ，其中是我们将扩展到的一个现有签名的索引
定义了算法。
Security Model
Secure ETRS
在满足正确性，不可伪造性、匿名性和一些匿名可扩展性概念的前提下，可扩展门限环签名方案是安全的
Unforgeability for ETRS
敌手生成一组伪造，有q组同一消息在其子环上的签名被查询过（line 5）
如果环中被腐化的个数+q大于等于t个，lose
如果伪造的签名能通过验证，敌手胜利。
(可扩展)阈值环签名选择消息攻击下的存在不可伪造性。Keygen、corrupt和sign oracle同上，不同之处在于ERS算法被ETRS变体替换，签名oracle现在返回部分签名。
Anonymity for ETRS
签名者不能被腐化，某签名者的消息不能被查询过
sr表示里面所有的成员集合成的总环super-ring
签名者不能被腐化，所有成员都被有效地生成
line11-12：根据lad扩展签名，但最后生成的签名的环和门限值都要相同（line 13）
对于匿名性，由敌手提交给挑战者的ladders有以下结构(这里t表示方案的门限值):前t条指令的类型为，其中对两个ladders中的所有指令都是相同的，并且在同一ladder中签名者索引i都是不同的;最后(t−1)指令的类型为，其中对两个ladders（和）中的所有指令都是相同的
Strong Anonymous Extendability for ETRS
对于强匿名可扩展性，对手提交的ladders具有以下结构:前t指令的类型为，其中签名者身份在ladders中是两两不同的，环在ladder中是相同的(但可能每个ladder都不同);随后的t−1指令的形式是或，其中表示索引。值得注意的是，在强匿名可扩展性中，每个ladder可能包含任意数量(多项式，并且每个ladder可能不同)的后续Extend指令，只要每个ladder的最后一个指令在同一环中结束
通用编译方案
Combine的前提是被结合的两个签名不能来自同一个签名者
Verify包括验证签名-门限合法、其中的任意签名合法，任意签名两两不可链接
定理。假设一个安全的same-message linkable extendable ring signature(SMLERS)方案，那么上图中的ETRS方案满足正确性、不可伪造性、匿名性。
ETRS from Signatures of Knowledge and Discrete Log
一个更具有交互性的可扩展门限环签名方案，它支持Join操作并具有更紧凑的签名:ETRS的大小与阈值t无关，相反，它与n(环大小的上限)线性增长。如果使用前文Discrete Log和SMLERS的SoK实例化，则返回大小为的线性签名。
利用多项式的特征，以类似于Shamir秘密共享的方式实现阈值功能。签名者采样对（line 1,4,5），这些对值定义一个阶为的唯一多项式，满足对于每个，。因为是未知的，签署人不知道这个多项式的系数，然而，由于多项式插值(补充知识https://zhuanlan.zhihu.com/p/337586165)只涉及线性操作(当x坐标是固定的和已知的)，签字者可以在指数中插值这个多项式，以学习任何给定的的附加点。
为了签名，以及之后背书一个陈述(Join一个签名)，签名者被要求在多项式上生成一个的SoK为一个多项式上的随机点满足（line 7,8）。
至关重要的是，签名者不知道的离散对数(即不在“陷门”值中)，因此必须满足关系的第二句(证明他们的密钥的知识)。
另一方面，要扩展签名，任何人都可以选择(剩余的)一个“陷门”点，并通过满足第一个子句(证明的知识)为生成一个证明，以在环中包含任何。
然后从陷门列表中删除pair 。(如果的拥有者以后想加入签名，Extend算法加密到;之后，的所有者可以恢复并在使用她的秘密密钥生成一个新的SoK之前将其返回到陷门列表中。)
对于任意的域（隐含），和，定义阶为的拉格朗日多项式
请注意，恶意扩展程序可以通过不加密新成员公钥下的正确陷门来阻止新添加的环成员后来加入签名。安全定义没有捕捉到这一点，但排除此类攻击将是一个有趣而有价值的扩展。可以修改原文的构造，通过添加一个零知识证明，证明加密的值实际上是h的离散对数，来禁止这种情况。
总结
以上是生活随笔为你收集整理的论文笔记：Extendability for Threshold Ring Signatures的全部内容，希望文章能够帮你解决所遇到的问题。
- 上一篇： 图像像素灰度处理代码
- 下一篇： 最近捣腾的-xwiki, java cp