魄 云， 朱雙寧， 張興凱， 王冠男

（1空軍電子技術(shù)研究所， 北京 100195；296610 部隊， 北京 102208 ）

基于辮群的簽名方案研究

魄 云1， 朱雙寧1， 張興凱2， 王冠男1

（1空軍電子技術(shù)研究所， 北京 100195；296610 部隊， 北京 102208 ）

辮群是構(gòu)造抗量子攻擊密碼方案的新平臺。 本文對一個基于辮群上求根問題的簽名方案進行分析，指出該方案是不安全的，得到簽名的任何人都能計算出簽名人的私鑰;利用共扼搜索問題的難解性來隱藏用戶的密鑰信息，構(gòu)造出新的簽名方案，分析表明該方案是可證明安全的。

簽名;辮群;共扼搜索問題;求根問題;隨機預(yù)言模型

0 引言

量子計算[1-2］的快速發(fā)展使得安全性假設(shè)為整數(shù)分解和離散對數(shù)難解性的公鑰密碼體制面臨嚴重威脅。為了抵抗已知量子算法的攻擊，大量學(xué)者開始設(shè)計非基于數(shù)論的、基于非交換代數(shù)的公鑰密碼體制。 1947年，Artin[3］首次提出辮群這一代數(shù)結(jié)構(gòu)，辮指數(shù)大于 2 的辮群具有復(fù)雜的非交換結(jié)構(gòu)，為構(gòu)造抗量子攻擊密碼體制提供了新的平臺。 2000年，Ko 等[4］提出了第一個辮群上的公鑰密碼體制。 此后，眾多學(xué)者相繼提出了辮群上的密鑰交換協(xié)議[5-6］、認 證 協(xié) 議[7-8］和簽名方案[9-18］。 目前大多數(shù)基于辮群的簽名方案安全性都是基于共扼類問題，屬于共扼簽名方案，不具有可證明安全性。

2010年，文獻[19］首次基于辮群上的求根問題構(gòu)造了具有可證明安全性的簽名方案。本文對該方案的安全性進行分析，得出：任何人都能根據(jù)簽名計算出簽名人的私鑰，因此該方案是不安全的。 本文對該方案進行改進，通過共扼作用實現(xiàn)對簽名人私鑰的保護，得到的簽名方案仍然是可證明安全的。

本文第1節(jié)主要介紹辮群的相關(guān)概念及簽名的安全模型;第2 節(jié)介紹文獻[19］中的簽名方案(簡稱為 WXBZ 方案） 并分析其安全性;第 3 節(jié)給出新的簽名方案及其安全性分析;第 4 節(jié)總結(jié)全文。

1 相關(guān)知識

1.1 辮群及辮群上的難解問題

定義 1[4］辮群 Bn(n≥2 為 自然數(shù)）是由生成元 σ1，σ2，…，σn-1生成的有限表示的無限群。 其生成元滿足：

σ1，σ2，…，σn-1稱為辮群的生成子或 Artin 生成子，還稱為初等辮子。 n稱為辮指數(shù)，辮群中的元素稱為一個 n辮子或辮元。B2是無限階的循環(huán)群，本文不予考慮，當 n＞2 時 Bn是無限非交換群。
雖然辮群 Bn是無限非交換群，但它包含一些很大的子群，滿足：來自不同子群的元素是交換的。 例如對于正整數(shù) n1＜n，令LBn1，RBn-n1分 別 為 σ1，σ2，… ， σn1-1和 σn1+1，σn1+2， … ，σn-1生成的子群，稱為 Bn的 n1-左子群和(n-n1）-右子 群。顯然，對任意 α∈有 αβ = βα。 當 n1= ? n/2」 時，將 Bn的 n1-左子群11和(n-n1）-右子群分別簡稱為左、右子群，記為 LBn和 RBn。 任意辮子 w∈Bn都可以唯一表示 成左規(guī) 范型 w= Δrα1… αq，q 稱為 w的正規(guī)長度，r稱為 w 的下確界，記作 inf(w），r+q 稱為 w 的上確界，記作 sup(w）。

定義 2(共扼）對辮子 α，β∈Bn，如果存在辮子 s使得 β = s-1αs，則稱 α，β 是共扼的，記作 α ～ β，s稱為 α，β 的共扼子。

定義 3[4］共扼判斷問題(Conjugacy Decision Problem）

問題實例：給定(α，β）∈Bn×Bn。

求解目標：判斷 α～β 是否成立。

定義 4[4］共扼搜索問題(Conjugacy Search Problem）

問題實例：給定(α，β）∈Bn×Bn，滿足 α～ β。

求解目標：找到一個 s∈Bn，使得 β =s-1αs。

定義 5[4］求根問題(Root Extraction Problem）

問題實例：給定整數(shù) c(c＞1）及 β∈Bn，存在 α∈Bn使 β =αc。

求解目標：找到一個 γ∈Bn，使得 β = γc。

1.2 安全模型

對簽名方案而言，適應(yīng)性選擇消息攻擊下的存在性不可偽造是一種較強的安全性質(zhì)。本文在隨機預(yù)言模型下考慮適應(yīng)性選擇消息 攻 擊 下 的 存 在 性 偽 造 (Existential Forgery under Adaptive Chosen Message Attack） ，通過挑戰(zhàn)算法 C 和攻擊算法 A 之間的游戲 Came來定義。 在該游戲中，C 和 A 進行如下交互：

1）C 生成系統(tǒng)參數(shù)及公鑰 y，并發(fā)送給 A;

2）A 向 C 詢問某些消息的雜湊值(C 模擬隨機預(yù)言機 Oh）;

3）A 向 C 詢問關(guān)于某些消息的簽名(C 模擬簽名預(yù)言機 Os）;

4）A 輸出一個消息簽名對(m，σ），滿足條件：

(a）ver(m，σ，y）=1;

(b）m?｛m＇｝，其中 ｛m＇｝ 表示出現(xiàn)在簽名詢問中的消息組成的集合。

如果某一多項式時間攻擊算法 A能在時間 t內(nèi)以不小于 ε的概率贏得游戲 Came，且滿足：向 Oh提出詢問的次數(shù)不超過 qh，向 Os詢問的次數(shù)不超過 qs，稱 A(t，ε，qh，qs） -攻擊了簽名方案。

定義 6[20］(不可偽造性） 如果不存在能(t，ε，qh，qs） -攻擊某簽名方案的多項式時間攻擊算法，則稱該簽名方案對于適應(yīng)性選擇消息攻擊下的存在性偽造是(t，ε，qh，qs） -不可偽造的。

2 WXBZ 方案分析

初始化：選擇正整數(shù) n、辮群 Bn、大素數(shù) p 及 l。 令

Bn(l）= ｛ b∈Bn|0≤inf(b） ≤sup(b） ≤l｝

LBn(l）= ｛ b∈LBn|0≤inf(b） ≤sup(b） ≤l｝

RBn(l）= ｛ b∈RBn|0≤inf(b） ≤sup(b） ≤l｝

則 |Bn(l） |≤l(n!）l，Bn(l），LBn(l） 和 RBn(l） 都是有限集合。是抗碰撞的單向雜湊函數(shù)，其中p-1｝。

密鑰生成：簽名人隨機選擇 x∈LBn(l）作為私鑰，計算 y=xp作為公鑰。

簽名：給定消息 m，簽名人隨機選擇 t∈RBn(l），計算 T=tp，c =H(m||T），s=tx-c，

其中辮元 T在作為雜湊函數(shù)的輸入時為二進制表示，關(guān)于消息 m 的簽名為 σ =(c，s）。

簽名驗證：給定消息 m 的簽名 σ=(c，s），驗證者驗證等式 c= H(m||spyc）是否成立，若成立，接受簽名;否則，拒絕簽名。

文獻[21］有如下結(jié)論：對于給定的辮元 αβ，其中 α∈LBn，β∈RBn，存在一種能有效求解 α 和 β 的算法。 在上述簽名方案中，s=tx-c，而 x∈LBn(l） ，t∈RBn(l） 。 因此，當簽名 公布后，任何人可以求出(t，xc） 。 又因為(c，p） =1，當求出滿足a1c+a2p=1 的(a1，a2） 后，任何人可計算 xa1cya2=xa1cxa2p=x， 即求出了簽名人的私鑰。

3 新的簽名體制方案

3.1 簽名方案

初始化及密鑰生成過程同第3節(jié)。

簽名：給定消息 m，簽名人隨機選擇 t∈RBn(l）及 b∈Bn(l），計算 T=b-1tpb，Y=b-1yb，c=H(m||T），s=b-1tx-cb，關(guān)于消息 m 的簽名為 σ=(c，s，Y）。

簽名驗證：給定消息 m 的簽名 σ=(c，s，Y），驗證者驗證等式c=H(m||spYc）及 Y ～ y 是否成立，若都成立，接受簽名;否則，拒絕簽名。

3.2 方案分析

(1)完備性

由 x∈LBn，t∈RBn知 xt=tx，

故 c=H(m||T）=H(m||spYc）。

由 Y=b-1yb 可知 Y～ y 成立，因此簽名方案是完備的。

(2)不可偽造性

下面先給出證明不可偽造性所需的引理。

引理 1[22］對簽名方案 REP-SS 考慮適應(yīng)性選擇消息攻擊，設(shè)A是輸入為公開參數(shù)的多項式時間算法，可以分別向隨機預(yù)言機、簽名預(yù)言機詢問 qh和 qs次。 如果 A 能在時間 tA內(nèi)，以概率 ε≥qsqh/N+2q2s/N+7qh/(p-1）成功地產(chǎn)生關(guān)于消息 m 的有效簽名σ=(c，s，Y），且未向簽名預(yù)言機詢問過 m 的簽名，則通過該算法可以在時間 t＇≤84480qhtA/(ε-qsqh/N-2q2s/N）內(nèi)得到關(guān)于消息 m的兩個有效簽名 σ =(c，s，Y）和 σ＇=(c＇，s＇，Y） 滿 足 c≠c＇，其中 N =|LBn(l） |· |Bn(l） |。

定理1在隨機預(yù)言模型下，如果存在一個多項式時間攻擊算法 A 能(tA，ε，qh，qs） -攻擊該簽名方案，其中 ε≥qsqh/N+2q2s/N+ 7qh/(p-1），則存在一個多項式時間挑戰(zhàn)算法 C，能通過調(diào)用算法A 在時間 t＇≤84480qhtA/( ε-qsqh/N-2q2s/N）內(nèi)解辮群上求根問題的一個實例，其中 N=|LBn(l） |· |Bn(l） |。

證明在求解過程中，C 必須對算法 A可詢問的隨機預(yù)言機和簽名預(yù)言機進行模擬，模擬過程中分別為各預(yù)言機建立一個詢問、回答相對應(yīng)的關(guān)系列表 Lh和 Ls。 在與 A 交互之前，C 令 Lh= Φ，Ls=Φ。

當 A 向隨機預(yù)言機 H 提出詢問 m||T 時，C 執(zhí)行：

1）檢查詢問 m||T 是否已經(jīng)存在于列表 Lh中，若是，則返回對應(yīng)的值;否則執(zhí)行下一步;

2）隨機選擇 c∈｛1，…，p-1｝返回給 A 作為回答;

3）將該次詢問及回答(m||T，c）添加到關(guān)系列表 Lh中，即令Lh=LhU｛(m||T，c）｝。

對簽名預(yù)言機的模擬：當 A 向簽名預(yù)言機詢問關(guān)于消息 mi(1≤i≤qs） 的簽名時，C 按如下方式執(zhí)行：

1）隨機選擇 ci∈｛1，…，p-1｝;

2）隨機選擇 ti∈Bn(l），驗證是否成立，若不是，重新選擇 ti;否則，繼續(xù)下一步;

3）隨機選擇 bi∈Bn(l），計算

4） 檢查 mi||Ti是否已經(jīng)存在于關(guān)系列表 Lh中，若 mi||Ti存在于 Lh中，且對應(yīng)回答為 ci，則輸出簽名 σi=(ci，si，Yi），并令 Ls=LsU｛ (mi，σi） ｝;若 mi||Ti存在于 Lh中，而對應(yīng)回答不為 ci，返回至第(1）步重新選擇 ci并繼續(xù)執(zhí)行;若 mi||Ti不存在于 Lh中，則將 ci作為與詢問 mi||Ti對應(yīng)的回答保存到關(guān)系列表 Lh中，即令 Lh=LhU｛(mi||Ti，ci）｝ ，并輸出簽名 σi=(ci，si，Yi） ，令 Ls=LsU｛(mi，σi）｝ 。

由引理 1 可知，若 A 在時間 tA內(nèi)以概率 ε≥qsqh/N+2q2s/N+ 7qh/(p-1）成功偽造出消息 m 的簽名 σ =(c，s，Y），則 C 可以在時間內(nèi)得到兩個有效的簽名 σ = (c，s，Y）和 σ＇=(c＇，s＇，Y）滿足

不妨設(shè) Y=b-1yb，即有

由簽名方案中的 t∈RBn(l） ，x∈LBn(l）及 s=b-1tx-cb 可知，對于兩個有效簽名 σ =(c，s，Y） 和 σ＇=(c＇，s＇，Y），s 和 s＇由同樣的 t和不同的 c得到，則應(yīng)有

由 c，c＇∈｛1，…，p-1｝，c≠c＇可知 0＜ |c-c＇|＜p。 p 是素數(shù)，則存在整數(shù) a1，a2滿足 a1(c-c＇）+a2p=1。 C 通過計算

可得到 b-1xb，即 C 求得了 Y 的 p 次根。

由定理1可知，該方案在適應(yīng)性選擇消息攻擊下是存在性不可偽造的。

4 結(jié)語

辮群作為構(gòu)造密碼協(xié)議的新平臺，一經(jīng)提出就成為研究熱點。本文對基于辮群上求根問題的簽名方案進行了分析和改進，構(gòu)造了一個可證明安全的簽名方案。 與共扼盲簽名體制相比，新的簽名體制在計算效率和簽名長度上都有優(yōu)勢。

[1］Shor PW.Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer[J］ .SIAM Journal on Computing， 1997， 26(5） ： 1484-1509.

[2 ］Kitaev A.Quantum measurements and the abelian stabilizer problem[EB/OL］.http： //arxiv.org/quant-ph/9511026.

[3］Artin E.Theory of braids[J］ .Annals of Mathematics Studies，1947， 48(2）： 101-126.

[4］Ko KH， Lee SJ， Cheon JH， et al.New public key cryptosystem using braid groups[C］ //Proceedings of Crypto-2000， Lecture Notes in Computer Science， Benlin： Springer-Verlag， 2000，1880： 166-183.

[5］Anshel I， Anshel M， Fisher B， et al.New key agreement protocol in braid group cryptography[C］ //Topics in Cryptology-CT-RSA 2001， Lectures Notes in Computer Science， Benlin：Springer-Verlag， 2001， 2020： 1-15.

[6］Cha JC， Ko KH， Lee SJ， et al.An efficient implementation of braid groups[C］ //In： Advances in Cryptology： Proceedings of ASIACRYPT 2001， Lecture Notes in Computer Science，Benlin： Springer-Verlag， 2001， 2248： 144-156.

[7 ］Sibert H， Dehornoy P， Girault M.Entity authentication schemes using braid word reduction[EB/OL］ .http： //eprint. iacr.Org/2002/187.

[8］Lal S and Chaturvedi A.Authentication schemes using braid groups[EB/OL］.http： //arXiv.org/cs.CR/0507066.

[9］Ko KH， Choi DH， Cho MS， et al.New signature scheme using conjugacy problem[EB/OL ］ .http： //eprint.iacr.org/ 2002/168.

[10］丁勇， 田海博， 王育民.一種改進的基于辮群的簽名體制[J］.西安電子科技大學(xué)學(xué)報， 2006， 33(1）： 50-52.

[11］Thomas T， Lal AK.Group signature scheme using braid groups[EB/OL］ .http： //arXiv.org/cs.CR/0602063.

[12］Verma GK.Blind signature schemes over braid groups[EB/ OL］.http： //eprint.iacr.org/2008/027.

[13］Verma GK.A proxy signature scheme over braid groups[EB/ OL］.http： //eprint.iacr.org/2008/160.

[14］Zhang LL， Zeng JW.Proxy signature based on braid group [J］ .Journal of Mathematical Study， 2008， 41(1） ： 56-64.

[15］Lal S and Verma V.Some proxy signature and designated verifier signature schemes over braid groups[EB/OL］ .http： // arXiv.org/cs.CR/09043422.

[16 ］Verma GK.A proxy blind signature scheme over braid groups[J ］ .International Journal of Network Security，2009， 9(3） ： 214-217.

[17］魄云， 張興凱， 熊國華等.辮群上代理簽名體制的分析與設(shè)計[J］.計算機應(yīng)用研究， 2011， 28(9）： 3522-3524.

[18］魄云， 熊國華， 張興凱等.辮群上的強盲簽名體制[J］.中國科學(xué)院研究生院學(xué)報， 2011， 28(6）： 826-831.

[19］魄云， 熊國華， 鮑皖蘇等.辮群上新的簽名體制[J］.電子與信息學(xué)報， 2010， 32(12）： 2930-2934.

[20］Pointcheval D and Stern J.Security Arguments for Digital Signatures and Blind Signatures[J］ .Journal of Cryptology，2000， 13(3）： 361-396.

[21］Tsaban B.On an Authentication Scheme Based on the Root Problem in the Braid Group[EB/OL］ .http： //arxiv.org/abs/ math.GR/0509059.

[22］魄云.辮群上的數(shù)字簽名研究[D］.鄭州：信息工程大學(xué)，2011.

《通信技術(shù)》征稿啟示

《通信技術(shù)》 是國內(nèi)創(chuàng)辦時間長、影響大的 IT 專業(yè)媒體，由中國電子科技集團公司主管、中國電子科技集團公司第三十研究所主辦，主要報道信源處理、傳輸、業(yè)務(wù)與系統(tǒng)、網(wǎng)絡(luò)、移動通信、信息安全等方面的先進技術(shù)、理論研究成果和最新動態(tài)。

自 1967年創(chuàng)刊以來，《 通信技術(shù)》一直以促進民族通信事業(yè)的發(fā)展為已任，搭建了一個聯(lián)系編讀交流、展示通信技術(shù)發(fā)展的良好平臺。 在強化品質(zhì)、不斷創(chuàng)新的基礎(chǔ)上，《通信技術(shù)》將以嶄新的面貌出現(xiàn)在您的面前——更新穎的內(nèi)容、更美觀的版面、更精美的印刷。為擴大學(xué)術(shù)交流的渠道，本刊特向社會征集優(yōu)秀稿件。

熱誠歡迎通信技術(shù)領(lǐng)域從事科學(xué)、教學(xué)、技術(shù)開發(fā)、維護管理等方面的專家、學(xué)者、在校師生和相關(guān)技術(shù)人員踴躍投稿。

征稿內(nèi)容：信源處理;傳輸;業(yè)務(wù)和系統(tǒng);網(wǎng)絡(luò);移動通信; 通信保密

在線投稿：www.txjszz.com/jwk-xxaq/ht-login.jsp

電 話：028-85169918/85151528 傳 真：028-85151528

《通信技術(shù)》編輯部

二O一四年一月一日

Signature Scheme based on Braid Groups

WEI Yun1， ZHU Shuang-ning1， ZHANG Xing-kai2， WANG Guan-nan1
(1AF 1Institute of Electronic Technology，Beijing 100195，China;2PLA 2Unit 96610， Beijing 102208， China）

Braid group is a new platform for constructing quantum attack-resistant cryptographic scheme.A signature scheme based on of root-extraction problem of braid groups is analyzed ， and its security vunerability is pointed out that the private key of the signer can be figured out once the signature is known.For this reason， the intractability of conjugacy search problem is used to hide the user's private key and build new signature scheme.Analysis indicates that this proposed scheme is provable secure.

signature;braid group;conjugacy search problem;root-extraction problem;random oracle model

TP309

A

1009-8054(2015)03-0085-04

魄 云(1982—），女，博士，工程師，主要研究方向為公鑰密碼學(xué);

朱雙寧(1978—），男，碩士，工程師，主要研究方向為信息安全;

張興凱(1981—），男，碩士，工程師，主要研究方向為信息安全;

王冠男(1981—），女，碩士，工程師，主要研究方向為計算機應(yīng)用。■

2014-12-11