閱讀此文前，誠邀您點選一下“關注”，友善您随時查閱一系列優質文章，同時便于進行讨論與分享，感謝您的支援~
文|三月十
編輯|hshdhdjehd
引言
群簽名是活躍的密碼主題，其中群成員被授予代表其群匿名簽署消息的權利。然而，在實際應用中，這種權利在大多數情況下并不是永久的，通常僅限于某些時間段。
這意味着每個組成員的簽名權需要與時間段相關聯，以便可以随時間段自動更改。但是，對于通用群簽名，簽名權是永久授予成員的，這在某種意義上是有限制的，因為某些服務的權限通常不是永久的。
目前已知的結構可以分為兩類,第一種是被撤銷的簽名者無法生成被驗證檢查接受的簽名。
另一種是被撤銷的簽名者可以生成一個被驗證檢查接受的簽名，但是該簽名不能通過撤銷檢查。前者的核心思想是定期釋出一個廣播加密，隻有非登出成員才能解密。
簽名者需要計算組成員身份證明和密文解密證明，計算成本相對較高。但驗證的成本相對較低且恒定。
後者基于VLR機制，通過使用包含已撤銷簽名者資訊的撤銷清單來檢查簽名的簽名者是否已被撤銷。
一、帶有時限密鑰的群簽名
為了解決問題，引入了帶時間綁定密鑰的群簽名（GS‑TBK），定義了兩種類型的撤銷：自然撤銷和成熟前撤銷。
自動撤銷需要為每個簽名密鑰設定一個過期時間τ，如果簽名者不能生成未超過過期時間的證據，即目前時間t < τ，簽名将不會被驗證檢查接受。
這兩類撤銷的結合導緻到期會員的自然撤銷占撤銷的大部分，過早撤銷僅占一小部分。這意味着 RL 的大小顯著減小，是以驗證的計算成本也降低了。
為了實作自然撤銷，采用構造來定期廣播到期資訊，簽名者使用該資訊來計算未達到到期時間的證明。
對于過早撤銷，仍然增加了VLR方案。由于廣播機制，這種結構的缺點是簽名者需要定期下載下傳到期資訊并更新他們的簽名密鑰。
因為隻關注到期時間，但是，對于某些簽名權僅限于幾個不連續時間段的情況是以可能不适用。組成員的簽名密鑰與任何時間段相關聯。具體地，對于設定時間跨度為一周的情況，可以在周一授予群成員的簽名權，周二撤銷，周三自動恢複。
這意味着⽆論是将簽名權限制在某個時間段還是幾個不連續的時間段，GS‑TBK 的撤銷力度都可以作為實際應用的理想解決方案。
建構一個超越與因式分解和求解離散對數相關的傳統假設的 GS‑TBK 方案是一個具有挑戰性的開放性問題。是以，我們希望從與格相關的假設中提供一個 GS‑TBK 方案，以擴充其在後量子安全中的應用。
二、預賽
描述本文中使用的符号，分别用R, Rq表示多項式環Z[X]/(Xd +1)和商環Zq [X]/(Xd +1) 。小寫字母（例如 x）表示多項式環 R 或Rq中的元素。我們還分别為 R 或Rq中的列向量和矩陣編寫粗體小寫字母（例如x）和粗體大寫字母（例如A） 。
1.困難的假設
回顧困難假設，在 SIS 和 LWE 的子產品變體提出以下定義。
2. 拒絕抽樣
對于标準偏差 σ > 0，我們定義以c ∈ Z為中心的離散ℓ，高斯分布 D，當c = 0 時。對于多項式 x ∈ R，我們将 x ← DR,σ表示為 x 服從分布Dσ的每個系數，預設情況下我們寫為 x ← Dσ 。如下圖：
引理 1：對于 σ > 0，它認為 Pr[x ← D σ √ 2dℓ] < 2 −dℓ/4 拒絕采樣，可以輸出一個向量z ，其分布獨立于一個秘密向量b.為了消除z對b的依賴性， 選擇随機幹擾向量y并設定z = cb + y以便z的分布與 y 的分布在統計上⽆法區分，其中 c 是挑戰多項式。
引理 2：設 M = O(1)，V = {v ∈ R : ||v|| < t} 是一組多項式， ρ : V → [0, 1] 是機率分布。對于秘密向量b ← ρ 和幹擾向量集z = cb + y和輸出 Rej(z, b, σ )。
其中y ← D σ ≥ 11||b||。那麼算法1 1−2 −ω(log ℓd)中傳回 1 的機率在 和M之間的統計距離内。 2 −ω(log ℓd) ℓd在z和 D 輸出 1的分布。如圖：
三、基于格的URS
在較進階别，URS 允許在不使用i=1 的情況下編輯有序消息集{mi}上的簽名 sig簽名密鑰，使其僅在{mi}i∈I 的子集上有效，其中 I ⊆ [1, n]。
然後，經過編輯的消息 I¯ ⊂ [1, n]\I。我們應該注意到mi是{mi} i∈I¯ ，僅表示消息集的第 i 個元素。
由 4 個多項式時間算法組成的 URS 方案，KeyGen(1λ , n)：密鑰生成算法取整數n，輸出輸入安全參數1λ公鑰 pk，簽名密鑰 sk。
1.安全模型
URS 方案應該滿足兩個安全要求：不可連接配接性和不可僞造性。不可連結性確定派生算法生成的派生簽名不會連結到原始簽名。
不可僞造性是任何數字簽名方案都應該滿足的安全屬性。在此之前，我們介紹要使用的簽名預言機：
2.UR計劃
給出了基于i=1 的有序消息集{mi}的 URS 方案， URS簽名方案。我們的不同之處在于，n 條消息的塊和簽名密鑰被用作拒絕采樣中的秘密值以生成原始簽名。
是以，我們将要簽名的消息定義為m1,mn∈S，我們還需要将幹擾向量的見證添加到原始簽名中，以便簽名可以被編輯。
3.安全分析
我們證明我們的 URS 方案實作了不可連結性和不可僞造性，URS 方案是⽆條件不可連結的。
我們需要證明派生簽名性質 sig′ 的分布服從獨立于原始簽名 sig 和編輯消息{mi} i∈I¯的分布。
由于推導預言機沒有使用s來生成模拟器簽名，敵手A不知道是否我們知道密鑰s或s是以我們得到非零結果的機率至少為2。然後我們得到 MSIS3,β問題的解。
四、基于格的GS‑TBK
我們首先回顧GS‑TBK 的定義。主要差別是每個成員的簽名密鑰可以與授權時間段Ti相關聯，其中時間段Ti允許不連續。
也就是說，成員 i 可以在授權時間段 t ∈ Ti内生成有效簽名，隻需要知道目前時間段和授權時間段，而不是像以前那樣關注到期時間，這意味着簡化了管理流程和簽名算法。
1.證券分析
我們定義一個敵手 B，其目的是通過使用 A 的有效僞造來破壞不可僞造性實驗。對于給定的 URS 公鑰 pk，B 将其構造為組公鑰 gpk。
B向OJM (i, Ti)查詢時，選擇si,3 ，通過自己構造的陷門對si,1, si,2進行采樣，向URS實驗的OSign* (Ti)查詢原始簽名sigi 。
當向GS‑TBK的OSign(i, M, t)查詢時，B結合了(si,1, si,2, si,3)的知識證明和ODerive(i, t)的派生簽名sig。
五、實施
為了說明性能和安全性之間的平衡，我們給出了兩組參數來實作我們的方案。首先，我們将對手的空間複雜度視為我們方案安全性的下限，因為當成功的挑戰者猜出僞造者的身份時，他的運行時間需要乘以 q，但空間複雜度不受影響。
根據枚舉估計，埃爾米特根因子 δ = 1.0036 意味着 242 位後量子時間複雜度和 93 位後量子空間複雜度。已經驗證，這樣的複雜性可以達到美國國家标準與技術研究院（NIST）對後量子方案的第一類定義。
為了達到這個安全級别，≈ 2 60)，σ = 2 我們設定 (d, q, Q) = (4096, ≈ 2 andκ = 26 以達到埃爾米特根因子 δ ≈ 1.0036。
1.GS‑TBK 的性能
我們的 GS‑TBK 方案的實驗評估。首先，為了評估我們的方案在不同系統中的性能，我們給出了一組時間跨度參數（n = 7，n = 24，n = 30，n = 60），它們對應于實際應用的一般時間跨度。
例如分别為周、小時、月和分鐘。當然時間跨度也可以根據實際需要由組權限設定，這里隻是示範幾個通用的設定。其他參數由兩個後量子設定安全級别。
結語
我們提出了一個URS方案和一個GS‑TBK方案。前者允許派生可編輯簽名以釋出有效的簽名子集，後者基于URS，在不更新成員簽名密鑰的情況下，實作精确限制每個群組成員在任意時間段的簽名權限。
更适用于非永久授予會員服務權的實際應用。URS方案實作了不可連結性和不可僞造性，GS‑TBK方案實作了匿名性、可追溯性和不可成幀性。我們的方案的性能經過實驗評估以達到可行的水準，這對于資源有限的裝置是通用的。
不可忽略的是，如果時間跨度 n 設定過大，時間和存儲成本将線性增加，盡管這種情況很少見。我們期望進一步優化 GS‑TBK 方案的性能，以實作獨立于時間跨度 n 的恒定小。
此外，盡管基于格的結構迄今為止仍然不受量子攻擊的影響，但人們普遍認為，隻有量子随機預言機模型中的證明才能顯示出針對量子對手的安全保證。
參考文獻：
1.D. Chaum 和 E. van Heyst，“團體簽名”，Proc。 EUROCRYPT，1991 年。
2.S. Ling、K. Nguyen、A. Roux‑Langlois 和 H. Wang，“具有驗證者本地撤銷的基于格的組簽名方案”，Theor，2018年。
3.J. Camenisch、M. Dubovitskaya、K. Haralambiev 和 M. Kohlweiss，“可組合和子產品化匿名憑證：定義和實用結構”，Proc，2015年。
4.M. Bellare 和 G. Neven，“普通公鑰模型中的多重簽名和一般分叉引理”，Proc，2006 年 。
5.C. Baum、I. Damgård、V. Lyubashevsky、S. Oechsner 和 C. Peikert，“來自結構化格假設的更有效承諾”，Proc，2018 年。