新的基于格的可驗(yàn)證加密簽名方案

張彥華 胡予濮

(綜合業(yè)務(wù)網(wǎng)理論與關(guān)鍵技術(shù)國家重點(diǎn)實(shí)驗(yàn)室(西安電子科技大學(xué)) 西安 710071) (yhzhangxidian@163.com)

新的基于格的可驗(yàn)證加密簽名方案

張彥華 胡予濮

(綜合業(yè)務(wù)網(wǎng)理論與關(guān)鍵技術(shù)國家重點(diǎn)實(shí)驗(yàn)室(西安電子科技大學(xué)) 西安 710071) (yhzhangxidian@163.com)

可驗(yàn)證加密簽名(verifiably encrypted signature, VES)能夠有效地保證互聯(lián)網(wǎng)上交易過程的公平性.VES的核心思想是：簽名者利用仲裁者的公鑰對(duì)自己所簽發(fā)的一個(gè)普通數(shù)字簽名進(jìn)行加密，隨后證明密文中確實(shí)包含一個(gè)普通簽名，任何驗(yàn)證者都可以利用仲裁者的公鑰來驗(yàn)證其真實(shí)性，但在沒有簽名者或仲裁者的幫助下無法從中提取出普通簽名；當(dāng)爭議發(fā)生時(shí)，驗(yàn)證者可以要求仲裁者從可驗(yàn)證加密簽名中恢復(fù)出簽名者的普通簽名.利用Agrawal等人在美密2010上給出的固定維數(shù)的格基委派技術(shù)、格上原像抽樣算法和差錯(cuò)學(xué)習(xí)問題的非交互零知識(shí)證明，該文構(gòu)造出一個(gè)新的格上可驗(yàn)證加密簽名方案，并在隨機(jī)預(yù)言機(jī)模型下嚴(yán)格證明了其安全性.與已有的可驗(yàn)證加密簽名方案相比，該方案要求簽名者根據(jù)仲裁者公鑰生成簽名者公私鑰對(duì)，構(gòu)造簡單，公私鑰和簽名尺寸更短，效率更高，并且能夠抵抗量子攻擊.

可驗(yàn)證加密簽名(VES)；固定維數(shù)；格；隨機(jī)預(yù)言機(jī)模型; 差錯(cuò)學(xué)習(xí)問題

互聯(lián)網(wǎng)在線交易已逐漸成為日常生活中比較重要的商品交換方式，如何在分布式網(wǎng)絡(luò)中保證交換過程的公平性是電子商務(wù)安全亟待解決的關(guān)鍵問題之一.1997年，Asokan等人[1]首次提出可驗(yàn)證加密簽名(verifiably encrypted signature, VES)的概念.可驗(yàn)證加密簽名能夠有效地保證互聯(lián)網(wǎng)上交易過程的公平性.一個(gè)可驗(yàn)證加密簽名方案包含3個(gè)參與者：簽名者(又稱用戶)、驗(yàn)證者和可信第三方(又稱仲裁者).VES的核心思想是：簽名者利用仲裁者的公鑰對(duì)自己所簽發(fā)的一個(gè)普通數(shù)字簽名進(jìn)行加密，隨后證明密文中確實(shí)包含一個(gè)普通簽名，任何驗(yàn)證者都可以利用仲裁者的公鑰來驗(yàn)證其真實(shí)性，但在沒有簽名者或仲裁者的幫助下無法從中提取出普通簽名；當(dāng)爭議發(fā)生時(shí)，驗(yàn)證者可以要求仲裁者從可驗(yàn)證加密簽名中恢復(fù)出簽名者的普通簽名.

基于雙線性Diffie-Hellman假設(shè)，Boneh等人[2]于2003年給出了第1個(gè)有效的非交互的VES方案.簽名驗(yàn)證過程不需要零知識(shí)證明，而且方案在隨機(jī)預(yù)言機(jī)模型下是可證明安全的.自此以后，VES引起了眾多學(xué)者的廣泛關(guān)注，很多基于標(biāo)準(zhǔn)數(shù)論假設(shè)的VES方案相繼被提出[3-7].

近年來，基于格構(gòu)造新型密碼系統(tǒng)因具有較高的漸進(jìn)效率、運(yùn)算簡單和抗量子攻擊等特點(diǎn)，成為后量子時(shí)代密碼領(lǐng)域的研究熱點(diǎn)，并取得了一系列研究成果[8-11].2010年，Rückert等人[12]構(gòu)造出第1個(gè)基于格的標(biāo)準(zhǔn)模型下的VES方案，然而該方案是靜態(tài)化的.2011年，Wang等人[13]構(gòu)造出第1個(gè)基于格的隨機(jī)預(yù)言機(jī)模型下非靜態(tài)化的VES方案，然而該方案不滿足強(qiáng)不可偽造性.2014年，Kim等人[14]構(gòu)造出一個(gè)高效的基于格的VES方案，該方案不再額外需要梅克爾樹(Merkle trees)，但是簽名者的公私鑰尺寸和可驗(yàn)證加密簽名的尺寸都明顯較大.

本文增添仲裁者密鑰生成階段來生成仲裁者公私鑰，并利用Agrawal等人[15]提出的固定維數(shù)的格基委派技術(shù)來生成簽名者密鑰，從而有效地減小簽名者的公私鑰尺寸；然后運(yùn)用原像抽樣算法和差錯(cuò)學(xué)習(xí)問題(learning with errors, LWE) 的非交互零知識(shí)證明構(gòu)造出一個(gè)新的格上可驗(yàn)證加密簽名方案，并在隨機(jī)預(yù)言機(jī)模型下嚴(yán)格證明了其安全性.與已有的基于格的可驗(yàn)證加密簽名方案相比，該方案構(gòu)造簡單，公私鑰和簽名尺寸更短，效率更高.

1 基礎(chǔ)知識(shí)

1.1 格

定義1. 設(shè)b1,b2,…,bm是n上m個(gè)線性無關(guān)的向量，格Λ定義為所有這些向量的整數(shù)線性組合構(gòu)成的集合，即}，其中向量組b1,b2,…,bm構(gòu)成格Λ的一組基B.

定義2. 設(shè)q是一個(gè)素?cái)?shù)，A∈n×mq，u∈nq，則：

(1)

(2)

定義3. 對(duì)任意s>0，定義以向量c為中心，s為參數(shù)的格Λ上的離散高斯分布為：

(3)

其中x∈Λ，ρs,c(x)=exp(-π‖x-c‖2s2).

1.2 重要算法

引理1[8]. 設(shè)n是正整數(shù)，q≥2,m≥2nlbq,對(duì)于除了至多2q-n的部分之外所有的A∈n×mq以及任意，向量u=Aemodq的分布統(tǒng)計(jì)接近nq上的均勻分布，其中e∈D.

格上陷門抽樣算法(TrapGen)、離散高斯抽樣算法(SampGau)和原像抽樣算法(SampPre)由如下2個(gè)引理給出.

引理2[9]. 設(shè)n是正整數(shù)，q≥2，m>5nlbq,存在概率多項(xiàng)式時(shí)間(probabilistic polynomial time, PPT)算法TrapGen(q,n)，輸出A∈n×mq和TA∈m×mq，其中A在n×mq上是統(tǒng)計(jì)均勻的，TA是格的陷門基，且滿足

引理3[8]. 設(shè)n是正整數(shù)，素?cái)?shù)q≥2，m>n，矩陣A∈n×mq.TA∈m×mq是格的陷門基，高斯參數(shù)s≥‖‖).對(duì)于c∈m和u∈nq，有：

Gordon等人[10]提出了一個(gè)變形的格基陷門抽樣算法(OrthoSamp)，由如下引理給出.

引理4[10]. 設(shè)n是正整數(shù)，素?cái)?shù)q≥2，正整數(shù)m≥n+8nlbq，矩陣B∈n×mq的列向量的子集合構(gòu)成nq.存在PPT算法OrthoSamp(q,B)，輸出矩陣A∈n×mq和TA∈m×mq，使得：

1)ABT=0 modq，其中A的秩為n，且在n×mq上是統(tǒng)計(jì)均勻的.

3)TA的任一列向量ti∈mq統(tǒng)計(jì)接近，其中).

定義4. 對(duì)于矩陣A∈m×m，如果Amodq作為中的矩陣是可逆的，則稱A是q可逆的.

Agrawal等人[15]提出的格基委派技術(shù)(BasisDel)能夠生成固定維數(shù)的格基陷門，由如下引理給出.

引理5[15]. 設(shè)n是正整數(shù)，q>2，m>2nlbq，TA∈是格的陷門基，可逆矩陣R∈Dm×m，高斯參數(shù)s≥‖‖m)3.存在PPT算法BasisDel(A,R,TA,s),輸出B∈n×mq和TB∈m×mq，其中B=AR-1modq，TB是格的陷門基，且對(duì)于參數(shù)s的最小值滿足‖‖≤‖‖.

引理6[15]. 設(shè)n是正整數(shù)，q>2，m>2nlbq，矩陣A∈n×mq的列向量的子集合構(gòu)成nq.存在PPT算法SampRwith(A)，輸出矩陣B∈n×mq，R∈m×mq和TB∈m×mq，其中B=AR-1modq，其分布統(tǒng)計(jì)接近于Dm×m，矩陣TB∈m×mq是格的陷門基，且滿足‖‖).

1.3 格上困難問題

定義6. 小整數(shù)解問題(small integer solution, SIS).設(shè)n是正整數(shù)，q為素?cái)?shù)，給定隨機(jī)矩陣A∈n×mq和實(shí)數(shù)β=poly(n)，找到非零向量e，使得Ae=0 modq且‖e‖≤β.

定義7. 非齊次小整數(shù)解問題(inhomogeneous small integer solution, ISIS).設(shè)n是正整數(shù)，q為素?cái)?shù)，給定矩陣A∈n×mq和向量y∈nq，實(shí)數(shù)β=poly(n)，找到非零向量e，使得Ae=ymodq且‖e‖≤β.

定義8. 差錯(cuò)學(xué)習(xí)問題(learning with errors, LWE).設(shè)n是正整數(shù)，q為素?cái)?shù)，對(duì)任意0<α<1，定義ψα為期望值為0、標(biāo)準(zhǔn)差為α的[0,1)上的正態(tài)分布，對(duì)應(yīng)的q上的離散分布為.定義為nq×q上的分布，其中s，ui∈nq是隨機(jī)選取的向量，xi∈q依分布獨(dú)立隨機(jī)選取.LWE問題是指給定As,χ上多項(xiàng)式個(gè)樣本量，找到向量s∈nq.

1.4 格上非交互零知識(shí)證明

2013年，Laguillaumie等人[17]給出了一個(gè)滿足如下ISIS關(guān)系的非交互零知識(shí)證明協(xié)議，即

RISIS={(A,y,β;x)∈n×mq×nq××m;
Ax=ymodq,‖x‖≤β}.

(4)

利用LWE困難問題與ISIS困難問題的對(duì)偶性，Laguillaumie等人同時(shí)給出了滿足如下LWE關(guān)系的一個(gè)有效的零知識(shí)證明協(xié)議，即

(5)

2 可驗(yàn)證加密簽名

2.1 定 義

可驗(yàn)證加密簽名由如下8個(gè)PPT算法構(gòu)成.

1) 系統(tǒng)建立(Setup).給定安全參數(shù)λ，輸出系統(tǒng)公開參數(shù)PP.

2) 仲裁者密鑰生成(Adj-KeyGen).給定公開參數(shù)PP，輸出仲裁者公私鑰對(duì)(APK,ASK).

3) 簽名者密鑰生成(KeyGen).給定公開參數(shù)PP、仲裁者公鑰APK，輸出簽名者公私鑰對(duì)(PK,SK).

4) 普通簽名生成(Sign).給定公開參數(shù)PP、私鑰SK和消息M，輸出普通簽名σ.

5) 普通簽名驗(yàn)證(Verify).給定公開參數(shù)PP、公鑰PK、簽名σ和消息M，輸出接受或拒絕.

6) 可驗(yàn)證加密簽名生成(VES-Sign).給定私鑰SK、消息M和仲裁者公鑰APK，輸出可驗(yàn)證加密簽名ω.

7) 可驗(yàn)證加密簽名驗(yàn)證(VES-Verify).給定公鑰PK、APK、簽名ω和消息M，輸出接受或拒絕.

8) 仲裁(Adj).給定公鑰PK、APK、仲裁者私鑰ASK、可驗(yàn)證加密簽名ω和消息M，輸出普通簽名σ.

可驗(yàn)證加密簽名方案的正確性需滿足如下2點(diǎn)：

1) 運(yùn)用VES-Sign算法生成的可驗(yàn)證加密簽名ω必須能通過VES-Verify算法的驗(yàn)證；

2) 仲裁者運(yùn)用Adj算法可以有效地從可驗(yàn)證加密簽名ω中恢復(fù)出原始普通簽名σ，且σ必能通過Verify算法的驗(yàn)證.

2.2 安全模型

可驗(yàn)證加密簽名方案應(yīng)滿足強(qiáng)不可偽造性、強(qiáng)不透明性和可提取性3個(gè)安全屬性.可通過攻擊者與挑戰(zhàn)者的交互游戲來定義其安全性.

定義9. 強(qiáng)不可偽造性.若不存在多項(xiàng)式有界的敵手A1能以不可忽略的優(yōu)勢贏得以下游戲，則稱一個(gè)VES方案是強(qiáng)不可偽造的.

1) 系統(tǒng)建立.挑戰(zhàn)者C1輸入安全參數(shù)λ，運(yùn)行Setup，Adj-KeyGen和KeyGen算法生成VES方案的公開參數(shù)PP和所有公私鑰對(duì)(APK，ASK)，(PK，SK)，并將(PP,APK,ASK,PK)發(fā)送給敵手A1.

2) 詢問階段.A1適應(yīng)性地進(jìn)行多項(xiàng)式次如下詢問.

① 普通簽名生成詢問.C1運(yùn)行Sign算法可獲得任何消息M的普通簽名σ，并返回給A1.

② 可驗(yàn)證加密簽名生成詢問.C1運(yùn)行VES-Sign算法獲得任何消息M的VES簽名ω，并返回給A1.

3) 偽造階段.最后，敵手A1輸出一個(gè)消息M*及其VES簽名ω*.

敵手A1贏得上述游戲當(dāng)且僅當(dāng)：

1)ω*是消息M*的一個(gè)合法VES；

2) (M*,ω*)不是一個(gè)可驗(yàn)證加密簽名生成的詢問結(jié)果.

定義10. 強(qiáng)不透明性.若不存在多項(xiàng)式有界的敵手A2能以不可忽略的優(yōu)勢贏得以下游戲，則稱一個(gè)VES方案是強(qiáng)不透明的.

1) 系統(tǒng)建立.挑戰(zhàn)者C2輸入安全參數(shù)λ，運(yùn)行Setup，Adj-KeyGen和KeyGen算法生成VES方案的公開參數(shù)PP和所有公私鑰對(duì)(APK，ASK)，(PK，SK)，并將(PP,APK,PK)發(fā)送給敵手A2.

2) 詢問階段.A2適應(yīng)性地進(jìn)行多項(xiàng)式次如下詢問.

① 普通簽名生成詢問.C2運(yùn)行Sign算法可獲得任何消息M的普通簽名σ，并返回給A2.

② 可驗(yàn)證加密簽名生成詢問.C2運(yùn)行VES-Sign算法可獲得任何消息M的VES簽名ω，并返回給A2.

③ 仲裁詢問.C2運(yùn)行Adj算法可獲得消息M及其VES簽名ω對(duì)應(yīng)的普通簽名σ，并返回給A2.

3) 偽造階段.最后，敵手A2輸出一個(gè)消息M*及其普通簽名σ*.

敵手A2贏得上述游戲當(dāng)且僅當(dāng)：

1)σ*是消息M*的一個(gè)合法普通簽名；

2) (M*,σ*)不是一個(gè)仲裁詢問結(jié)果.

定義11. 可提取性.若不存在多項(xiàng)式有界的敵手A3能以不可忽略的優(yōu)勢贏得以下游戲，則稱一個(gè)VES方案是可提取的.

1) 系統(tǒng)建立.挑戰(zhàn)者C3輸入安全參數(shù)λ，運(yùn)行Setup和Adj-KeyGen算法生成VES方案的公開參數(shù)PP和所有仲裁者公私鑰對(duì)(APK，ASK)，并將(PP，APK)發(fā)送給敵手A3.

2) 詢問階段.A3適應(yīng)性地進(jìn)行多項(xiàng)式次如下詢問.

仲裁詢問：C3運(yùn)行Adj算法可獲得消息M及其VES簽名ω對(duì)應(yīng)的普通簽名σ，并返回給A3.

3) 偽造階段.最后，敵手A3輸出一個(gè)消息M*及其VES簽名ω*，對(duì)應(yīng)的簽名者的公鑰為PK*.

敵手A3贏得上述游戲當(dāng)且僅當(dāng)：

1)ω*是消息M*的一個(gè)合法VES；

2)σ*=Adj(PP,ASK,APK,PK*,ω*,M*)不是消息M*的一個(gè)合法普通簽名.

3 新的基于格的VES方案

3.1 方案構(gòu)造

1) 系統(tǒng)建立.輸入安全參數(shù)n，具體參數(shù)設(shè)置見3.2節(jié).選取2個(gè)安全的抗碰撞Hash函數(shù)H1:{0,1}*→Dm×m，H2:{0,1}*×mq→nq；輸出系統(tǒng)公開參數(shù)PP=(n,m,q,s1,s2,s3,α,H1,H2).

2) 仲裁者密鑰生成.輸入公開參數(shù)PP，運(yùn)行算法TrapGen(q,n)生成隨機(jī)矩陣B∈n×mq和格的陷門基TB∈m×mq，且‖‖；輸出仲裁者公私鑰對(duì)(APK,ASK)=(B,TB).

3) 簽名者密鑰生成.輸入公開參數(shù)PP和仲裁者公鑰APK=B；運(yùn)行算法OrthoSamp(q,B)生成隨機(jī)矩陣A∈和格的陷門基TA∈，滿足ABT=0 modq；輸出公私鑰對(duì)(PK,SK)=(A,TA).

4) 普通簽名.輸入公開參數(shù)PP、私鑰SK=TA和消息M，簽名者進(jìn)行如下操作.

① 隨機(jī)選取比特串r←{0,1}n和向量v∈mq.

② 運(yùn)行算法SampPre(A,TA,H2(M‖r‖v),s1)，生成向量d∈m.

③ 輸出普通簽名σ=(M,r,v,d).

6) 可驗(yàn)證加密簽名生成.輸入公開參數(shù)PP、私鑰SK=TA、仲裁者公鑰APK=B∈n×mq和消息M，簽名者進(jìn)行如下操作.

② 令R=H1(M‖r)，B′=BR-1∈n×mq.

③ 計(jì)算v=B′Ts+xmodq，并構(gòu)造對(duì)v的一個(gè)有效非交互零知識(shí)證明π.

④ 運(yùn)行SampPre(A,TA,H2(M‖r‖v)-ARTx,s2)生成向量e∈m.

⑤ 輸出可驗(yàn)證加密簽名ω=(M,r,v,π,e).

7) 可驗(yàn)證加密簽名驗(yàn)證.輸入簽名者公鑰PK=A、仲裁者公鑰APK=B∈n×mq和簽名ω=(M,r,v,π,e)；首先驗(yàn)證非交互零知識(shí)證明π的有效性，計(jì)算R=H1(M‖r)，如果π是有效的，ABT=0 modq，‖e‖‖r‖v) modq，則接受ω為簽名者對(duì)消息M的一個(gè)有效的可驗(yàn)證加密簽名；否則,拒絕.

8) 仲裁.輸入簽名者公鑰PK=A，仲裁者私鑰ASK=TB和簽名ω=(M,r,v,π,e)，仲裁者進(jìn)行如下操作.

① 計(jì)算R=H1(M‖r).

② 運(yùn)行算法BasisDel(B,R,TB,s3)生成隨機(jī)矩陣B′=BR-1∈n×mq和的陷門基TB′∈m×mq.

③ 利用TB′從v=B′Ts+xmodq中解出(s,x).

④ 計(jì)算d=e+RTx∈mq.

⑤ 輸出普通簽名σ=(M,r,v,d).

3.2 參數(shù)設(shè)置

為保證仲裁過程中可以從v中有效解出(s,x)和系統(tǒng)的安全運(yùn)行，給定安全參數(shù)為n，設(shè)置其他參數(shù)如下：

m=n+8n1+δ,

(6)

(7)

(8)

(9)

(10)

(11)

(12)

3.3 安全性證明

3.3.1 正確性

令ω=(M,r,v,π,e)是可驗(yàn)證加密簽名生成算法的一個(gè)輸出，方案的正確性分析如下：

1) 由于簽名者選取隨機(jī)向量s，從而簽名者可以構(gòu)造出一個(gè)有效的非交互零知識(shí)證明π.

3) 容易計(jì)算Aσ=A(e+RTx)=Ae+ARTx=H2(M‖r‖v) modq.

4) 在可驗(yàn)證加密簽名驗(yàn)證算法中，我們有：

A(e+RTv)=Ae+ARTv=Ae+ART(B′Ts+x)=
Ae+A(B′R)Ts+ARTx=Ae+ABTs+ARTx=
A(e+RTx)=H2(M‖r‖v) modq.

3.3.2 強(qiáng)不可偽造性

定理1. 如果存在敵手A1以不可忽略的優(yōu)勢ε1攻破方案的強(qiáng)不可偽造性，則可構(gòu)造算法B1以概率ε1qH2求解ISIS問題，其中qH2表示敵手可進(jìn)行H2詢問的最大次數(shù).

證明. 假設(shè)B1獲得了一個(gè)ISIS問題實(shí)例(A∈n×mq,y∈nq,n,m,q,s)，要求B1通過模擬游戲利用A1求解出一個(gè)非零向量e，使得Ae=ymodq且.

模擬過程如下：

①H1(M‖r‖)詢問.B1首先檢查列表l1中是否存在對(duì)該詢問的應(yīng)答，若存在，直接返回；否則，B1隨機(jī)選取矩陣R∈Dm×m并將(M,r,R)存儲(chǔ)在列表l1中，然后將R返回給A1.

②H2(M‖r‖v)詢問.B1首先進(jìn)行H1(M‖r)詢問并獲得矩陣R.如果此次詢問恰好是第i*次詢問，B1計(jì)算h2=ARTv+ymodq，并將(M,r,v,h2,⊥)存儲(chǔ)在列表l2中，然后將h2返回給A1;如果不是第i*詢問，B1計(jì)算h2=A(RTv+e) modq，其中e∈D，并將(M,r,v,h2,e)存儲(chǔ)在列表l2中，然后將h2返回給A1.

③ 可驗(yàn)證加密簽名詢問.不失一般性，假設(shè)A1在進(jìn)行可驗(yàn)證加密簽名詢問之前已進(jìn)行過H1和H2詢問.B1在列表l2中找到(M,r,v,h2,e)，如果e=⊥，則B1直接放棄模擬，否則，返回e作為簽名應(yīng)答.

3) 最終，A1輸出一個(gè)偽造的可驗(yàn)證加密簽名ω*=(M*,r*,v*,π*,e*).不失一般性，假設(shè)A1在輸出偽造的可驗(yàn)證加密簽名之前已經(jīng)進(jìn)行過H1和H2詢問.B1在列表l2中找到(M*,r*,v*,h,e)，如果e≠⊥，則B1直接放棄，否則，B1直接返回e*作為ISIS實(shí)例的應(yīng)答.

證畢.

3.3.3 強(qiáng)不透明性

定理2. 如果存在敵手A2以不可忽略的優(yōu)勢ε2攻破方案的強(qiáng)不透明性，則可構(gòu)造算法B2以概率ε2qH1求解LWE問題，其中qH1表示敵手可進(jìn)行H1詢問的最大次數(shù).

模擬過程如下：

1) B2首先構(gòu)造矩陣B′∈n×mq，其中第i列恰好是向量ui；構(gòu)造向量v′∈mq，其中第i個(gè)分量元素恰好是vi；B2選取隨機(jī)矩陣R′∈Dm×m，然后運(yùn)行算法OrthoSamp(q,B′R′)生成隨機(jī)矩陣A∈n×mq和的陷門基TA∈m×mq，B′R′AT=0 modq；令仲裁者公鑰APK=B′R′，簽名者公私鑰對(duì)(PK,SK)=(A,TA)，并將APK，PK發(fā)送給敵手A2，同時(shí)B2隨機(jī)選取i*∈{1,2,…,qH1}.B維護(hù)3個(gè)列表l1，l2，l3分別存儲(chǔ)對(duì)H1詢問、H2詢問和可驗(yàn)證加密簽名詢問的應(yīng)答.

①H1(M‖r‖)詢問.如果此次詢問恰好是第i*次詢問，B2將(M,r,⊥,R′)存儲(chǔ)在列表l1中并將R′返回給A2；如果此次詢問不是第i*次詢問，B2運(yùn)行算法SampRwith(B)生成可逆矩陣R∈m×mq，BR-1∈n×mq和TBR-1∈m×mq，B2將(M,r,TBR-1,R)存儲(chǔ)在列表l1中并將R返回給A2.

②H2(M‖r‖v)詢問.B2首先檢查列表l2中是否存在對(duì)該詢問的應(yīng)答，若存在，直接返回；否則，B2隨機(jī)選取向量h2∈nq并將(M,r,v,h2)存儲(chǔ)在列表l2中，然后將h2返回給A2.

③ 可驗(yàn)證加密簽名詢問.不失一般性，假設(shè)敵手A2在進(jìn)行可驗(yàn)證加密簽名詢問之前已經(jīng)進(jìn)行過H1和H2詢問.B2在列表l1中找到(M,r,TBR-1,R)，如果TBR-1≠⊥，則B2按照算法步驟進(jìn)行可驗(yàn)證加密簽名生成，否則，令v=v′，B2利用陷門基TA運(yùn)行算法SampPre(A,TA,H2(M‖r‖v)-AR′Tx,s2)生成向量e,并構(gòu)造對(duì)v的一個(gè)有效非交互零知識(shí)證明π.B2將(M,r,v,π,e)存儲(chǔ)在列表l3中，返回e作為簽名應(yīng)答.

④ 仲裁詢問.不失一般性，假設(shè)A2在進(jìn)行仲裁詢問之前已經(jīng)進(jìn)行過H1詢問，當(dāng)收到A2對(duì)可驗(yàn)證加密簽名ω=(M,r,v,π,e)的仲裁詢問，B2在列表l1中找到(M,r,TBR-1,R)，如果TBR-1=⊥，則B2直接放棄;否則，B2利用TBR-1對(duì)v=(BR-1)Ts+xmodq進(jìn)行求解得x，并返回普通簽名σ=(M,r,v,d=e+RTx)給A2，其中R=H1(M‖r‖).

3) 最終，敵手A2輸出一個(gè)有效的普通數(shù)字簽名σ*=(M*,r*,v*,d*).在這里，假設(shè)σ*是A2從可驗(yàn)證加密簽名詢問結(jié)果中提取出來的.不失一般性，假設(shè)敵手A2在輸出偽造的可驗(yàn)證加密簽名之前已經(jīng)進(jìn)行過H1詢問、H2詢問和可驗(yàn)證加密簽名詢問.B2首先在列表l1中找到(M*,r*,TBR-1,R)，在列表l3中找到(M*,r*,v,π,e);如果TBR-1≠⊥，則B2直接放棄，否則，我們易知v=v′，R=R′，B2利用R和e可以由向量d*=e+R′Tx求得x，從而可以由v′=B′Ts*+xmodq求解出s*.

因而只要A2成功攻破上述方案的強(qiáng)不透明性，算法B2就可以有效求解LWE問題，從而我們易知算法B2成功求解LWE問題的概率為ε2qH1.

證畢.

3.3.4 可提取性

定理3. 上述可驗(yàn)證加密簽名方案滿足可提取性.

證明. 對(duì)于消息M的VESω=(M,r,v,π,e)，我們證明如果該簽名是有效的，那么總可以由ω提取出一個(gè)普通簽名σ=(M,r,v,d=e+RTx).非交互零知識(shí)證明π可以有效確保v=(BR-1)Ts+xmodq中的x是一個(gè)短向量.由仲裁過程可知，可以以極大概率從v中提取出x，從而可以構(gòu)造出短向量d=e+RTx.

由可驗(yàn)證加密簽名驗(yàn)證過程可知，

H2(M‖r‖v)=A(e+RTv)=
A[e+RT(BR-1)Ts+RTx]=
A[e+BTs+RTx]=A(e+RTx).

因而只要可驗(yàn)證加密簽名ω是有效的，那么v中肯定含有短向量x,使得

A(e+RTx)=H2(M‖r‖v).

證畢.

3.4 效率比較

表1給出了該文方案與已有的基于格的可驗(yàn)證加密簽名方案的比較結(jié)果.文獻(xiàn)[13]的方案僅滿足存在性不可偽造性，文獻(xiàn)[14]的方案雖滿足強(qiáng)不可偽造性(strong unfrogeability)，但簽名者的公私鑰和可驗(yàn)證加密簽名尺寸都明顯較大.該文方案雖然要求簽名者公私鑰對(duì)需根據(jù)仲裁者公鑰生成，但是其構(gòu)造簡單，不僅滿足強(qiáng)不可偽造性和強(qiáng)不透明性，而且簽名者公私鑰和可驗(yàn)證加密簽名更短，效率更高，實(shí)用性更強(qiáng).

Table 1 Efficiency Comparison of Schemes表1 方案的效率對(duì)比

4 結(jié)束語

本文利用Agrawal等人提出的固定維數(shù)的格基委派技術(shù)，構(gòu)造出一個(gè)新的格上可驗(yàn)證加密簽名方案.在隨機(jī)預(yù)言機(jī)模型下證明了方案的安全性是基于格上ISIS和LWE問題，保證了其在量子環(huán)境下的安全性.與已有的基于格的可驗(yàn)證加密簽名方案相比，該方案構(gòu)造簡單，公私鑰和簽名尺寸更短，效率更高.

[1]Asokan N, Schunter M, Waidner M. Optimistic protocols for fair exchange[C] //Proc of the 4th ACM Conf on Information Security and Privacy. New York: ACM, 1997: 7-17

[2]Boneh D, Gentry C, Lynn B, et al.. Aggregate and verifiably encrypted signatures from bilinear maps[G] //LNCS 2656: Proc of Eurocrypt 2003. Berlin: Springer, 2003: 416-432

[3]Zhou Yousheng, Sun Yanbin, Qing Sihan, et al. An efficient id-based verifiably encrypted signature scheme[J]. Journal of Computer Research and Development, 2011, 48(8): 1350-1356 (in Chinese)(周由勝, 孫艷賓, 卿斯?jié)h, 等. 一種高效的基于身份的可驗(yàn)證加密簽名方案[J]. 計(jì)算機(jī)研究與發(fā)展, 2011, 48(8): 1350-1356)

[4]Shen Jian, Wang Jin, Zheng Yuhui, et al. A novel verifiably encrypted signature from weil pairing[C] //Proc of HumanCom and EMC 2013. Berlin: Springer, 2014: 603-607

[5]Calderon T, Meiklejohn S, Shacham H, et al. Rethinking verifiably encrypted signatures: A gap in functionality and potential solutions[G] //LNCS 8366: Proc of CT-RSA 2014. Berlin: Springer, 2014: 349-366

[6]Shim K A. On the security of verifiably encrypted signature schemes in a multi-user setting[J]. Annals of Telecommuni-cations, 2014, 69(11): 585-591

[7]Nishimaki R, Xagawa K. Verifiably encrypted signatures with short keys based on the decisional linear problem and obfuscation for encrypted VES[J]. Designs, Codes and Cryptography, 2015, 77(1): 61-98

[8]Gentry C, Peikert C, Vaikuntanathan V. How to use a short basis: Trapdoors for hard lattice and new cryptographic constructions[C] //Proc of the 40th Annual Symp on Theory of Computing. New York: ACM, 2008: 197-206

[9]Alwen J, Peikert C. Generating shorter bases for hard random lattices[J]. Theory of Computing Systems, 2011, 48(3): 535-553

[10]Gordon S D, Katz J, Vaikuntanathan V. A group signature scheme from lattice assumptions[G] //LNCS 6477: Proc of Asiacrypt 2010, Berlin: Springer, 2010: 395-412

[11]Nguyen P Q, Zhang J, Zhang Z F. Simpler efficient group signatures from lattices[G] //LNCS 9020: Proc of PKC 2015. Berlin: Springer, 2015: 401-426

[12]Rückert M, Schneider M, Schr?oder D. Generic constructions for verifiably encrypted signatures without random oracles or NIZKs[G] //LNCS 6123: Proc of ACNS 2010. Berlin: Springer, 2010: 22-25

[13]Wang Fenghe, Hu Yupu, Wang Chunxiao. A verifiably encrypted signature scheme from lattice assumption[J]. Journal of Information and Computational Science, 2011, 8(8): 1431-1438

[14]Kim K S, Jeong I R. Efficient verifiably encrypted signatures from lattices[J]. International Journal of Information Security, 2014, 13(4): 305-314

[15]Agrawal S, Boneh D, Boyen X. Lattice basis delegation in fixed dimension and shorter-ciphertext hierarchical IBE[G] //LNCS 6223: Proc of Crypto 2010. Berlin: Springer, 2010: 98-115

[16]Regev O. On lattices, learning with errors, random linear codes, and cryptography[C] //Proc of the 37th Annual Symp on Theory of Computing. New York: ACM, 2005: 84-93

[17]Laguillaumie F, Langois A, Libert B, et al. Lattice-based group signature scheme with logarithmic signature size[G] //LNCS 6477: Proc of Asiacrypt 2013. Berlin: Springer, 2013: 41-61

Zhang Yanhua, born in 1989. PhD candidate in Xidian University. His research interests include public key cryptography based on lattice and provable security.

Hu Yupu, born in 1955. Professor and PhD supervisor. His main research interests include multilinear map, public key cryptography based on lattice, witness encryption and fully homomorphic encryption.

A New Verifiably Encrypted Signature Scheme from Lattices

Zhang Yanhua and Hu Yupu

(StateKeyLaboratoryofIntegratedServiceNetworks(XidianUniversity),Xi’an710071)

Verifiably encrypted signatures (VES) can ensure the fairness of the Internet exchange process effectively. In a VES system, a signer can generate an ordinary signature on a given message using the secret key of the signer and then encrypt it under the public key of the adjudicator. A verifier should be able to verify that this encrypted signature is indeed an encryption of the ordinary signature of the signer, but the verifier cannot be able to extract the ordinary signature. The ordinary signature can only be recovered by the adjudicator from this encrypted signature. Using the technique of basis delegation in fixed dimension suggested by Agrawal et al in CPYPTO 2010, the lattice-based preimage sampling algorithm and a non-interactive zero-knowledge proof for the learning with errors (LWE) problem, this paper constructs a new verifiably encrypted signature scheme from lattices, and based on the hardness of the short integer solution (SIS) problem and the LWE problem, this proposed construction is provably strong unforgeable in the random oracle model. Compared with current verifiably encrypted signature schemes, this scheme needs that the public-private key pair of the signer should be generated according to the public key of the adjudicator, and this scheme can resist quantum attacks and enjoy simpler constructions, shorter public-private keys, smaller signature size and higher efficiency.

verifiably encrypted signature (VES); fixed dimension; lattice; random oracle model; the learning with errors

2015-09-30；

2016-05-16

國家自然科學(xué)基金項(xiàng)目(61472309) This work was supported by the National Natural Science Foundation of China (61472309).

TP309