實用的前向安全群簽名方案.doc

前向安全的群簽名 -By Song前向安全性：當群公鑰保持不變，一個群成員的群簽名密鑰evolves over time使得當前時間段的群簽名密鑰泄露不能使攻擊者偽造過去時間段的群簽名。前向安全性對于減少密鑰泄露引起的損害是非常重要的，并且特別的是，對群簽名是非?？扇〉模╠esirable）因為簽名密鑰泄露的危害隨著群規(guī)模大小的增加而增加。我們拓展前向安全的群簽名方案提供群成員撤銷問題的解決方法（不需要re-key所有其他群成員）。我們提供第一個解決方法，該方法支持回溯公開的撤銷和后向無關性以及簽名長度獨立于撤銷成員數(shù)量。在先前的群簽名方案，一個群成員簽名密鑰的暴露不僅僅需要改變?nèi)汗€和簽名密鑰，而且使所有先前得到的群簽名失效，因為GM不能分辨一個簽名是產(chǎn)生自攻擊者所獲得群簽名之后還是被攻擊者獲得群簽名之前的合法群成員。前向安全的群簽名如何減少群簽名密鑰泄露的損害。攻擊者在時間段j破壞一個群成員的系統(tǒng)，得到該成員的群簽名密鑰SKj。因為單向性（one-way），攻擊者不能計算相應的先前時間段的群簽名密鑰。假設用戶B得到一個時間段j之前文件m的群簽名。B希望能使用簽署過的文件m在相當長的時間（長到過了時間段j后）。當發(fā)現(xiàn)SKj已經(jīng)被泄露，群公鑰被撤銷。如果群簽名方案不具有前向安全性，顯然，B在文件m上獲得的群簽名就會變得無效并且B需要得到一個新的在文件m的簽名。但是，當群簽名被構(gòu)建成前向安全的方案，攻擊者不能計算關于先前時間段的群簽名密鑰，因此群只能撤銷在任何時間段j后面的群公鑰。如此任何關于時間段j之前的正確的簽名仍可接受。因為在B獲得在簽名的,tj。如此在m的簽名仍然是正確的簽名并且B不需要獲得一個新的在m的簽名。我們擴展由Ateniese等人提出的群簽名方案，采用兩種不同的方法構(gòu)建兩個不同的前向安全的群簽名方案。第一個方案利用6中的技術(shù)而第二個方案采用一個新的技術(shù)24實現(xiàn)前向安全性。另外，我們指出前向安全性群簽名方案確保其他想要的安全特性在一個很小的額外開銷。例如，當新成員C加入，具有前向安全性的群簽名方案，我們能限制新成員產(chǎn)生簽名只在將來的時間段有效而不是在加入時間段之前沒有額外的開銷。更一般的，我們支持時限的群成員身份特性在一個額外的開銷，也就是群成員值被允許在限定的時間段里代表群，簽名。公開撤銷特性：攻擊者在時間段i竊取了A的群簽名密鑰。A的群簽名密鑰的泄露在時間段j被發(fā)現(xiàn)。GM撤消了A的群簽名密鑰在時間段j。所以沒有人能在時間段j之后使用A的群簽名密鑰來產(chǎn)生正確的簽名。這就叫做：公共撤銷性?；厮莨_撤銷性：因為攻擊者本來會在時間段i之后的任何時間，代表群使用A的群簽名密鑰簽署文件，使用其他成員的簽名密鑰簽署的簽名應該仍舊保持有效、匿名和無關性?；厮莨_撤銷性包含公開撤銷性，反之不然。后向無關性:在時間段i之前，使用A的群簽名密鑰產(chǎn)生的簽名仍該保持有效，匿名和無關性，因為這些簽名是A產(chǎn)生的，而不是攻擊者。我們擴展的群簽名方案提出支持回溯公開撤銷性和后向無關性的前向安全的群簽名方案，并且簽名長度獨立于撤銷成員數(shù)量。弱前向安全性：假設一組群簽名密鑰=ki，ti1iL，ki，ti表示成員i在時間段ti的群簽名密鑰，并且t=min（t1，tL）。我們稱（）是的弱跨距（weak-span），（）表示該組群簽名密鑰ki，wi1iL，twiT。我們認為如果攻擊者給定一組群簽名密鑰不能產(chǎn)生一個在（）中正確的群簽名密鑰，那么群簽名方案滿足弱前向安全性。強前向安全性：給定一組群簽名密鑰=ki，ti1iL，ki，ti表示成員i在時間段ti的群簽名密鑰，我們稱（）是的跨度（span），（）代表該組群簽名ki，wi1uL，tiwiT。然后，如果攻擊者給定一組群簽名密鑰，不能產(chǎn)生一個在（）里的正確的群簽名，我們說，該群簽名方案滿足強前向安全性。時限的成員身份：GM能限制一個成員的群成員身份通過簽發(fā)給他群成員密鑰，該密鑰只能在某些時間段產(chǎn)生正確的群簽名?；厮莨_撤銷性：在時間段i，GM能從時間段j開始撤銷一個群簽名密鑰，使得任何使用這個群簽名密鑰在時間段j之后產(chǎn)生的簽名變得無效。而且，所有在時間段j之前使用這個群簽名密鑰產(chǎn)生的簽名應該對任何除了GM的人仍保持匿名性和無關性。3. 預備知識我們的方案依靠強RSA假設和DDH假設。讓n=pq成為RSA-Like模數(shù)并讓G成為Zn*的循環(huán)子群。SRSA假設是：給定n和zG，難以找到vG和eZ1，使得zve（mod n）。DDH假設是：給定g，gx，gy和gz，難以確定gxygz（是否相等）。我們使用現(xiàn)有的零知識證明協(xié)議作為我們方案里的building blocks。這些零知識證明協(xié)議可以使用一個理想的哈希函數(shù)（也成為Fiat-Shamir啟發(fā)式算法）實現(xiàn)。并且我們提到由此生成的知識簽名。因為篇幅限制，我們不回顧這些協(xié)議的細節(jié)。我們使用PK來表示謝意是一個知識簽名協(xié)議，希臘字母來表示被證明的秘密知識，所有其他的參數(shù)對于示證者（還沒有成為群成員的用戶）和驗證方。離散對數(shù)的知識簽名：讓G=表示階為q的一群素數(shù)，且yG。我們使用PK()：y=g（m）來表示在群G里，loggy的知識簽名。這個協(xié)議由29,15設計并在輔助字符串模型指出零知識19。在QRn中的離散對數(shù)的知識簽名：讓n=pq，p=2p+1，q=2q+1，并且p、q、p和q都是素數(shù)。G是QRn的生成元，并且yQRn。我們使用PK（）：y=g（m）表示在群QRn中l(wèi)oggy的知識簽名。一般的，示證者不容易證明y是一個二次剩余。所以我們使用協(xié)議PK（）：y2=(g2)代替，因為logg2y2=loggy,假如y是二次剩余。知識簽名的表示法：讓PK（1，v）：y=g11gvv（m）表示一個元素yG關于根（bases） g1，gvG的知識簽名的表示法。離散對數(shù)相等性知識簽名：PK（）：y1=gy2=h（m）表示對于根（bases）gG和hG，兩個群元素y1，y2G的離散對數(shù)相等性的知識簽名。知識簽名的范圍：PK（）：y=ga，b（m）表示yG關于gG離散對數(shù)的知識簽名，使得loggy映射（lies）進整數(shù)區(qū)間a，b。如果示證者沒有被提供分解的模數(shù)，這個協(xié)議能在SRSA假設下有效的完成。4.1 方案ISetup 步驟:GM選擇兩個 （ln/2）-bit 素數(shù)p=2p+1和q=2q+1，p和q也是素數(shù)。讓n：=pq。GM也隨機選擇元素a，d，g，g1RQRn，一個秘密數(shù)(元素)xRZpq*,并使y：=gx mod n。它存儲(p, q, x)作為他的密鑰并且公開(n, a, d, g, g1, y)作為群公鑰。GM同時也在群公鑰是正確的時候分割時間成T個時間段，并讓時間間隔公開。本文的剩余部分，我們使用下面概念。讓和表示整數(shù)區(qū)間：=（-2l，2l），=（2l，2l+1），lT+l+2.直觀.方案的直觀如下：當用戶U加入群，他和GM一起隨機選擇xuR，使得U知道xu和GM只知道yu：=axu。GM之后隨機選擇一個素數(shù)eu，計算cu，0：=（yud）1/（eu2T） mod n，并發(fā)送U（cu，0，eu）。如此，（xu, cu,0, eu）是U的群簽名密鑰。在強RSA假設下，除了GM沒人能產(chǎn)生正確的群簽名密鑰。GM然后使用平方（squaring）作為一個公共單向函數(shù)來evolve群簽名密鑰。特別的，U在時間段i的群簽名密鑰是（xu，cu，i，eu），cu，i=c2u，i-1 mod n。為了在時間段i簽署消息m，U產(chǎn)生非交互的知識證明，用戶知道（xu，cu，i，eu）使得，xu，并且eu，在非交互式證明的挑戰(zhàn)是依靠m作為在標準Fiat-Shamir 啟發(fā)式算法。為了啟用Open步驟，簽名者也使用GM的公鑰加密cu，i并產(chǎn)生加密是正確形式的非交互式證明。萬一發(fā)生爭議，GM可以簡單地解密cu，i的值來確定實際的簽名者。Join步驟:Evolve 步驟：假如U有在時間段j的群簽名密鑰(cu,j, eu, xu)。然后，在時間段j+1，他的群簽名密鑰變成(cu,j+1, eu, xu), cu,j+1：=c2u，j mod n.Sign和Verify 步驟:假設U在時間段j有群簽名密鑰(cu,j, eu, xu)。為了在時間段j簽署消息m，他首先選擇r1R0，12ln，計算A=cu，jyr1,B=gr1，并且產(chǎn)生：一個驗證方簡單的檢查以上知識簽名的正確性。Open步驟：DAA不需要。4.2 安全性分析在這個小部分，我們指出方案I是一個安全的群簽名方案并滿足弱前向安全性。我們在這兒陳述我們的定理并想提供給讀者附錄A為細節(jié)證明。4.3 時限的群成員身份當群成員U在時間段i加入，如果他只在時間段i得到群簽名密鑰(cu,i, eu, xu)，然后他只能在接下來的時間段i產(chǎn)生正確的群簽名并而不會在i之前產(chǎn)生。如此，他的群成員身份只能在他加入的時間段有效。我們可以很容易的拓展方案I來支持一個時限群成員身份更普通的形式，也就是一個群成員只被允許在限定的時間期間代表群簽名?；舅枷胧莾涉溔汉灻荑€。一鏈evolve 前向 over time（正如方案I）而另一鏈是后向的。注意到，前后兩鏈共享同一個xu。簽名者需要知道在時間段i前鏈和后鏈的簽名密鑰產(chǎn)生一個在時間段i的正確的簽名。知道在前向鏈時間段i的簽名密鑰可以讓簽名者計算所有時間段i之后在前向鏈的所有簽名，知道后向鏈在時間段i的所有簽名密鑰能使簽名者計算出時間段i之前后向鏈內(nèi)的所有簽名。所以知道i的簽名密鑰在前鏈和j的簽名密鑰在后鏈允許成員簽署i和j間的文件，給定ij。兩鏈的費用是不多的，也就是簽名長度少于一個單鏈簽名長度的兩倍。4.4 撤銷我們拓展方案I來支持具有后向無關的追溯的撤銷。讓h成為一個序列n循環(huán)群的生成元，DDH問題是困難的。當群成員U在i使用它的群簽名密鑰(cu,j, eu, xu)簽署消息，除了基本的Sign步驟外，U也作如下：他隨機性選擇rZn并計算g2=hr，C=g2cu，j，并顯示（reveals）（g2，C），我們稱他為撤銷token。U通過知識簽名證明g2和C是正確的構(gòu)成。當用戶V從時間段i開始被從群剔除時，cv，i和i將被顯示在撤銷列表中。假設驗證方有時間段j的簽名，ji并且撤銷token在簽名中是（g2，C）。為了看是否簽名密鑰已經(jīng)被剔除，驗證方簡單地計算cv,j并檢查是否。如果他們相等，意思是簽名被撤銷。更細一步，對于U在j簽署消息m，協(xié)議將如下：第一個協(xié)議PK是與我們原來的前向安全性群簽名方案相同的。第二個PK2是一個新的零知識證明協(xié)議，我們在附錄B構(gòu)建并解釋其細節(jié)。這個方案清楚的支持公共地撤銷群成員資格。然而，后向無關性依靠一個新的加密假設，我們叫做log-square假設：n是兩個安全素數(shù)產(chǎn)生的，如方案I。G是一個序列n的循環(huán)群，DDH問題是困難的，并且g2是G的生成元。給定隨機的vRQRn，并且w=g2uRG，對攻擊者，在沒有知道n的情況下決定v=u2 mod n是很難的。在這個假設下，很容易看出我們的方案支持后向無關性。密碼學假設減少到不是因子分解就是離散對數(shù)問題。我們猜測這個問題是難以解決的，盡管研究這個問題仍需要完成很多研究。5. 前向安全群簽名IISetup 步驟:Setup步驟幾乎與方案I一樣。除了方案I的Setup之外，讓i表示整數(shù)間隔。GM也詳述一個確定性單向方法使得給定一個隨機的素數(shù)eu，ii，一個可以產(chǎn)生一序列素數(shù)eu，i，eu，T，eu，jj，for ijT。給定只有eu，i對于某個ijT，后向計算是很難的，也就是eu，k，for kj。直觀.這個前向安全群簽名與方案I的在section 4是相似的，除了它使用不同的單向函數(shù)來evolve群簽名密鑰。當用戶U加入群，與方案I相似，他和GM一起隨機選擇xu使得U知道xu并且GM只知道。GM之后隨機選擇一個素數(shù)eu，0i，0iT。Join步驟:加入步驟與方案I相似出咯額第三步。在第三步，GM隨機地選擇一個素數(shù)eu，00，然后產(chǎn)生一個序列的素數(shù)eu，ii，0iT。Evolve步驟:Sign和Verify步驟:假設U在j有群簽名密鑰(cu,j, eu,j, xu)。為了在j簽署消息m，他首先選擇r1R0,12ln, 一個驗證方簡單的檢查上面知識簽名的正確性。5.2 安全性分析我們show方案II是一個安全的群簽名方案并滿足強前向安全性。我們陳述我們的定理并給讀者附錄A用于細節(jié)證明。5.3 時限群成員身份使用方案II，我們實際上能正確的支持群成員身份for 時間段的子群with幾乎沒有開支。例如，當用戶U加入群，如果GM只想在時間段t1，tm簽發(fā)U群成員身份正確，之后在第三部，代替計算bu作為整個序列eu，0，eu，T，GM計算mod n。如此U可以只在時間段t1，tm代表群簽名，沒有額外的開支在秘密存儲和計算時間相比于方案II的基礎。5.4 撤銷 方案II的撤銷很簡單。當用戶U使用自己的群成員身份(xu, eu,i, cu,i)簽名，除了在方案II基本的Sign步驟，他也做下面的：隨機產(chǎn)生一個元素g3QRn并展示g3和，并用零知識證明D是正確構(gòu)成的。我們叫（g3，D）簽名的撤銷token。更細一點Sign步驟如下：現(xiàn)在如果GM想從時間段i撤銷U的簽名，他簡單地顯示eu，i和i。如果用戶V在ji獲得簽名并且簽名的撤銷token是（g，D），為檢查是否簽名被撤銷，（也就是他是U簽署的）V從eu，i計算eu，j并簡單的檢查是否D=(g)eu，j。如果他們相等，它意味著簽名被撤銷，因為他是在時間段i由U簽署的。這個撤銷方案支持回溯公開的撤銷。很容易看到所有由其他成員簽署的簽名保持匿名性和無關性。這個方案對于撤銷的成員也支持后向無關性在DDH假設是困難的，因為不知道這個指數(shù)，給定在兩個簽名里的（g,D）和（g,D）兩個撤銷的token，如果一個能tell是否之后他能解決DDH問題。而且，withO（logT）存儲開支，我們拓展方案II來允許時限撤銷，也就是只在某些時間段撤銷群成員的簽名?；舅枷胧谴娈a(chǎn)生序列eu，0，eu，T使用一個單向樹。序列eu，0，eu，T構(gòu)成自上而下的單向樹的葉子節(jié)點。知道根，one能產(chǎn)生整個樹；并且知道一個間隔節(jié)點，one能產(chǎn)生整個子樹，但不是任何其他在這個書上的節(jié)點。如此，當GM只想在時間段t1撤銷群成員U的簽名，他reveals間隔節(jié)點作為子樹的根that覆蓋時間段從t1到t2.如此，任何用戶可以計算eu，i，for t1it2并且之后能檢查是否簽名被撤銷。6. 討論我們的兩個安全群簽名方案都是基于3提出的群簽名方案并且使用單向函數(shù)用作演變?nèi)汉灻荑€來實現(xiàn)前向安全性。這兩個方案有不同的性能和安全權(quán)衡策略。方案I由有效的Evolve步驟（僅僅需要一個平方），盡管簽名和驗證效率較低（需要O（T）平方）。方案II由高效的簽名和驗證步驟并且沒有額外的管理費用相比3中的非前向安全群簽名方案。但是方案II在Evolve步驟中效率很低（需要O（T）exponentiations 取冪），盡管相似的技術(shù)在24能被用來減少開銷with 存儲空間權(quán)衡。方案II也能比方案I實現(xiàn)更靈活的時限的群成員身份。方案II支持強