實(shí)用的前向安全群簽名方案.doc

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