论文笔记：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轉(zhuǎn)換為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的概念：擴(kuò)大t-out-of-n門限環(huán)簽名的環(huán)規(guī)模
動(dòng)機(jī)
目標(biāo)：為了實(shí)現(xiàn)匿名性，希望門限簽名生成過程中簽名者之間是非交互的。
現(xiàn)狀：存在非交互式簽名的閾值環(huán)簽名，簽名者在本地產(chǎn)生部分簽名，然后聚合這些簽名。
缺陷：所有簽名者必須同意他們所代表的組，這隱含地假設(shè)了他們之間的某種協(xié)調(diào)。
解決：非交互可擴(kuò)展環(huán)的規(guī)模，擴(kuò)展過程不需要簽名者參與。
貢獻(xiàn)
Preliminaries
Threshold Ring Signatures
- 非交互TRS：
輸出對簽名者的部分簽名；的輸入中加入門限；將個(gè)部分簽名合并成一個(gè)TRS?，這個(gè)算法可以被第三方運(yùn)行，因?yàn)樗恍枰灻叩拿孛苄畔ⅰ?/p>
- 另一種稍弱的解決：
簽名在簽名者之間傳遞，每個(gè)簽名者接收簽名，連接自己的簽名，傳遞簽名（只進(jìn)行一次）；
?
Signatures of Knowledge
通過用實(shí)例或聲明（statement）替換公鑰來泛化數(shù)字簽名，在NP語言中。只有當(dāng)簽名者擁有聲明的有效證人時(shí)，她才能為消息生成有效簽名。
一個(gè)二元關(guān)系的SOK定義為PPT算法的元組:
- : (message?, statement?, witness )
- : trapdoor?
提前看一下下面用到的關(guān)系初始化參數(shù)和簽名：
SoK方案應(yīng)該滿足correctness, simulatability, extractability
Extendable Ring Signatures(ERS)
Syntax
一個(gè)附加的算法Extend，允許任何第三方擴(kuò)大給定簽名的潛在簽名者的環(huán)
：輸入原簽名的環(huán)公鑰集合，和另一組環(huán)公鑰，輸出環(huán)為的新簽名
按某種順序擴(kuò)展簽名:（簽名者的身份+rings of簽名者標(biāo)識(shí)符集合）
算法:用在環(huán)上產(chǎn)生消息的簽名，并按順序擴(kuò)展這個(gè)簽名（使用存儲(chǔ)在中的密鑰）
Security Model
Unforgeability
?排除兩種普通攻擊：
Oracles:
如果查詢者沒有指定公鑰，正常生成身份-公私鑰對并存儲(chǔ)在列表中；否則將指定的身份-公鑰存儲(chǔ)在列表中，因?yàn)闊o法獲得私鑰，所以缺省；由于認(rèn)為查詢者知道對應(yīng)的，所以視為腐化密鑰對加入中
??
代表視為已被腐化的密鑰對，包括通過查詢獲得的，和敵手通過將已知公鑰登記給。
查詢方需要是未被腐化的，所以O(shè)racle可以通過查找到生成簽名，加入.
?Unforgeability for ERS
?一個(gè)可擴(kuò)展的環(huán)簽名方案ERS被認(rèn)為是不可偽造的，如果任意的PPT敵手都參加（以上的cmEUF）不可偽造實(shí)驗(yàn)，而成功的概率可以忽略不計(jì)。
Anonymous Extendability
我們定義了一個(gè)通用的實(shí)驗(yàn)，以支持2種不同的匿名可擴(kuò)展性:
- 標(biāo)準(zhǔn)匿名概念，其中不發(fā)生擴(kuò)展;
- 強(qiáng)匿名可擴(kuò)展性，不可能知道一個(gè)簽名經(jīng)歷了什么擴(kuò)展序列。
?可擴(kuò)展環(huán)簽名的匿名性和匿名可擴(kuò)展性
Oracles:OSign, OKeyGen，OCorrupt同上
（line 6）生成兩個(gè)不同的擴(kuò)展序列，如果敵手能夠區(qū)分簽名是從哪個(gè)序列擴(kuò)展來的，敵手勝利
生成挑戰(zhàn)簽名的過程：排除身份被腐化的可能（line?3）；分別對同一消息以不同的序列擴(kuò)展簽名。
注意以不同的序列生成的兩個(gè)擴(kuò)張簽名，所使用的簽名集合最終相同（即，是同一個(gè)消息在同一個(gè)環(huán)中的簽名）。
Anonymity for ERS（標(biāo)準(zhǔn)匿名性）
可擴(kuò)展環(huán)簽名方案被稱為匿名的，如果所有的PPT敵手都參與了匿名可擴(kuò)展性實(shí)驗(yàn)（如上），并向挑戰(zhàn)者提交種類為的梯子，認(rèn)為的成功概率近似于隨機(jī)猜測，可以忽略不計(jì)。
- 對于標(biāo)準(zhǔn)匿名性來說，不發(fā)生擴(kuò)展，所以輸出的和都只包含一個(gè)相同的環(huán)，只有簽名者身份不同。敵手猜對的概率等同于擲硬幣。
Strong Anonymous Extendability for ERS
可擴(kuò)展環(huán)簽名方案被認(rèn)為是強(qiáng)匿名可擴(kuò)展的，如果所有的PPT對手A都參與匿名可擴(kuò)展實(shí)驗(yàn)（如上），并且成功的概率可以忽略不計(jì)。
- 注意，強(qiáng)可擴(kuò)展性意味著擴(kuò)展環(huán)簽名的行為是無縫的，也就是說，攻擊者無法區(qū)分新環(huán)簽名(由Sign返回)和它的擴(kuò)展(由Extend返回)。這表示的強(qiáng)可擴(kuò)展性情況。
ERS from Signatures of Knowledge and Discrete Log
這個(gè)關(guān)系要求witness是或者對應(yīng)的離散對數(shù)（即）。
?
?
line 2表示：
line 4-5:?statement?, witness ?
?
擴(kuò)展過程與簽名大致相同，但使用了另一種witness.
（這個(gè)簽名好長，而且規(guī)模與擴(kuò)展的次數(shù)有關(guān)）
???
驗(yàn)證過程
定理1假設(shè)SoK是安全的方案，群上的離散對數(shù)問題困難，則以上ERS方案滿足正確性、不可偽造性、強(qiáng)匿名可擴(kuò)展性
Same-Message Linkable Extendable Ring Signatures?
Syntax
同消息可鏈接環(huán)簽名方案(SMLRS)是一種環(huán)簽名方案，它還允許任何第三方公開識(shí)別(鏈接)同一簽署人是否為同一消息生成了兩個(gè)簽名。這意味著，如果同一方在同一消息上簽名兩次，即使是不同的環(huán)，兩個(gè)簽名也可以被任何第三方鏈接。
前五種算法同上，Link算法允許任何驗(yàn)證者確定特定消息上的兩個(gè)簽名是否由同一個(gè)簽名者產(chǎn)生
注意，如果簽名被鏈接，鏈接不一定會(huì)揭示共同簽名者的身份。
SMLERS方案的正確性，它包含兩個(gè)語句:
Security Model
增加的性質(zhì)：
Same-Message One-More Linkability
沒有一組(t?1)腐化的簽名者可以為相同的消息產(chǎn)生t個(gè)簽名，而這些消息是成對不鏈接的
?signing, key generation and corruption oracles同上，除了算法ERS換成SMLERS
line 4:敵手輸出一組t對消息的簽名-環(huán)對；
line 5: 如果是已經(jīng)被查詢過的簽名的擴(kuò)展環(huán)，lose
line 6：如果輸出的t個(gè)簽名的所有環(huán)中被腐壞的成員大于等于t個(gè)，lose（因?yàn)槟菢涌隙苌?#xff09;
line 7: 生成的簽名不合法，lose
line 8: 如果這些生成的簽名兩兩不可鏈接，win；否則lose
Cross-Message Unlinkability
任何敵手都無法確定不同消息的兩個(gè)簽名是否由同一簽名者產(chǎn)生。
?line 5：對于敵手指定的兩個(gè)身份-消息生成的簽名，敵手無法分辨。
line 9：如果簽名者任意查詢過的簽名，lose
（誤，line 8 應(yīng)是）
?對于敵手指定的兩組消息，產(chǎn)生簽名的過程
Secure SMLERS
定理：同消息可鏈接可擴(kuò)展環(huán)簽名方案(SMLERS)在滿足正確性、Same-Message One-More Linkability和Cross-Message Unlinkability的前提下是安全的
SMLERS from Signatures of Knowledge and Discrete Log
將ERS轉(zhuǎn)換為SMLERS的方法
- 首先采用一種稍微不同的關(guān)系
值得注意的是，最后一個(gè)AND不僅要求簽名者證明秘密密鑰的知識(shí)，而且它還強(qiáng)制使用相同的秘密密鑰來生成鏈接性標(biāo)記。SMLERS的SoK是關(guān)于新關(guān)系的
- ?其次，修改了原ERS構(gòu)造中的Sign算法，它額外計(jì)算，并將加入作為簽名的一部分。（可注意到，標(biāo)記僅與消息和簽名方私鑰有關(guān)，且不泄露它們的信息）
- 最后，算法Link簡單地比較兩個(gè)簽名中的可鏈接性標(biāo)記。如果它們相等，則返回鏈接，否則返回不鏈接。
該方案只需對ERS的不可偽造性（分別地，匿名可擴(kuò)展性）的證明進(jìn)行少量修改，就可以證明該方案是Same-Message One-More Linkability（分別地，Cross-Message Unlinkability）的。
Extendable Threshold Ring Signatures
可擴(kuò)展門限環(huán)簽名方案還具有以下特性:
給定任意兩個(gè)門限簽名，對相同的信息和相同的環(huán)進(jìn)行驗(yàn)證，任何人都可以將簽名非交互組合得到。新簽名也是一個(gè)門限環(huán)簽名，它的門限等于對兩個(gè)簽名中至少一個(gè)作出貢獻(xiàn)的唯一簽名者的總數(shù)。這個(gè)功能由提供
對于門限為t的環(huán)，給定消息上的簽名，任何人都可以將非交互地轉(zhuǎn)換為具有相同閾值的同一消息上的簽名，但使用更大的環(huán)。此功能由提供。
Syntex
ETRS由6個(gè)算法組成
- . 其中，分別是兩個(gè)簽名中隱含的簽名者的集合
對于更具互動(dòng)性的語法，我們可以用操作替換執(zhí)行。
對于下面的定義，使用梯子lad的方式與在ERS上下文中使用的方式略有不同。lad將包含表單的元組序列。第一個(gè)組件可以取的值.
- ，其中是同一個(gè)環(huán)中兩個(gè)簽名的索引
- ，其中是我們將擴(kuò)展到的一個(gè)現(xiàn)有簽名的索引
定義了算法。
Security Model
Secure ETRS
在滿足正確性，不可偽造性、匿名性和一些匿名可擴(kuò)展性概念的前提下，可擴(kuò)展門限環(huán)簽名方案是安全的
Unforgeability for ETRS
敵手生成一組偽造，有q組同一消息在其子環(huán)上的簽名被查詢過（line 5）
如果環(huán)中被腐化的個(gè)數(shù)+q大于等于t個(gè)，lose
如果偽造的簽名能通過驗(yàn)證，敵手勝利。
?(可擴(kuò)展)閾值環(huán)簽名選擇消息攻擊下的存在不可偽造性。Keygen、corrupt和sign oracle同上，不同之處在于ERS算法被ETRS變體替換，簽名oracle現(xiàn)在返回部分簽名。
Anonymity for ETRS
?簽名者不能被腐化，某簽名者的消息不能被查詢過
sr表示里面所有的成員集合成的總環(huán)super-ring
?簽名者不能被腐化，所有成員都被有效地生成
line11-12：根據(jù)lad擴(kuò)展簽名，但最后生成的簽名的環(huán)和門限值都要相同（line 13）
對于匿名性，由敵手提交給挑戰(zhàn)者的ladders有以下結(jié)構(gòu)(這里t表示方案的門限值):前t條指令的類型為，其中對兩個(gè)ladders中的所有指令都是相同的，并且在同一ladder中簽名者索引i都是不同的;最后(t?1)指令的類型為，其中對兩個(gè)ladders（和）中的所有指令都是相同的
?Strong Anonymous Extendability for ETRS
對于強(qiáng)匿名可擴(kuò)展性，對手提交的ladders具有以下結(jié)構(gòu):前t指令的類型為，其中簽名者身份在ladders中是兩兩不同的，環(huán)在ladder中是相同的(但可能每個(gè)ladder都不同);隨后的t?1指令的形式是或，其中表示索引。值得注意的是，在強(qiáng)匿名可擴(kuò)展性中，每個(gè)ladder可能包含任意數(shù)量(多項(xiàng)式，并且每個(gè)ladder可能不同)的后續(xù)Extend指令，只要每個(gè)ladder的最后一個(gè)指令在同一環(huán)中結(jié)束
?通用編譯方案
Combine的前提是被結(jié)合的兩個(gè)簽名不能來自同一個(gè)簽名者
Verify包括驗(yàn)證簽名-門限合法、其中的任意簽名合法，任意簽名兩兩不可鏈接
定理。假設(shè)一個(gè)安全的same-message linkable extendable ring signature(SMLERS)方案，那么上圖中的ETRS方案滿足正確性、不可偽造性、匿名性。
ETRS from Signatures of Knowledge and Discrete Log
一個(gè)更具有交互性的可擴(kuò)展門限環(huán)簽名方案，它支持Join操作并具有更緊湊的簽名:ETRS的大小與閾值t無關(guān)，相反，它與n(環(huán)大小的上限)線性增長。如果使用前文Discrete Log和SMLERS的SoK實(shí)例化，則返回大小為的線性簽名。
?
?
利用多項(xiàng)式的特征，以類似于Shamir秘密共享的方式實(shí)現(xiàn)閾值功能。簽名者采樣對（line 1,4,5），這些對值定義一個(gè)階為的唯一多項(xiàng)式，滿足對于每個(gè)，。因?yàn)槭俏粗?#xff0c;簽署人不知道這個(gè)多項(xiàng)式的系數(shù)，然而，由于多項(xiàng)式插值(補(bǔ)充知識(shí)https://zhuanlan.zhihu.com/p/337586165)只涉及線性操作(當(dāng)x坐標(biāo)是固定的和已知的)，簽字者可以在指數(shù)中插值這個(gè)多項(xiàng)式，以學(xué)習(xí)任何給定的的附加點(diǎn)。
為了簽名，以及之后背書一個(gè)陳述(Join一個(gè)簽名)，簽名者被要求在多項(xiàng)式上生成一個(gè)的SoK為一個(gè)多項(xiàng)式上的隨機(jī)點(diǎn)滿足（line 7,8）。
?
至關(guān)重要的是，簽名者不知道的離散對數(shù)(即不在“陷門”值中)，因此必須滿足關(guān)系的第二句(證明他們的密鑰的知識(shí))。
另一方面，要擴(kuò)展簽名，任何人都可以選擇(剩余的)一個(gè)“陷門”點(diǎn)，并通過滿足第一個(gè)子句(證明的知識(shí))為生成一個(gè)證明，以在環(huán)中包含任何。
然后從陷門列表中刪除pair 。(如果的擁有者以后想加入簽名，Extend算法加密到;之后，的所有者可以恢復(fù)并在使用她的秘密密鑰生成一個(gè)新的SoK之前將其返回到陷門列表中。)
對于任意的域（隱含），和，定義階為的拉格朗日多項(xiàng)式
?
?
?
請注意，惡意擴(kuò)展程序可以通過不加密新成員公鑰下的正確陷門來阻止新添加的環(huán)成員后來加入簽名。安全定義沒有捕捉到這一點(diǎn)，但排除此類攻擊將是一個(gè)有趣而有價(jià)值的擴(kuò)展。可以修改原文的構(gòu)造，通過添加一個(gè)零知識(shí)證明，證明加密的值實(shí)際上是h的離散對數(shù)，來禁止這種情況。
總結(jié)
以上是生活随笔為你收集整理的论文笔记：Extendability for Threshold Ring Signatures的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 图像像素灰度处理代码
- 下一篇： [转]解构推荐系统：“猜你喜欢”是怎么猜