基于NTRU格的異構(gòu)簽密

楊潤(rùn)東 李子臣

(北京印刷學(xué)院 北京 102600)

0 引 言

1976年，文獻(xiàn)[1]中首次提出了現(xiàn)代密碼學(xué)的思想，開(kāi)啟了密碼學(xué)的新的方向。在此之后公鑰密碼體制迅速發(fā)展，在我們生活的很多地方都有應(yīng)用，主要應(yīng)用在互聯(lián)網(wǎng)、金融、銀行等領(lǐng)域。公鑰密碼體制主要有三大類：傳統(tǒng)PKI的公鑰密碼體制TPKI(Traditional Public Key Infrastructure)；身份公鑰密碼體制IDPKC(Identity-based Public Key Cryptography)；無(wú)證書(shū)公鑰密碼體制CLTPKC(Certificateless Public Key Cryptogtaphy)。

在1997年Zheng[2]首次提出密碼學(xué)原語(yǔ)簽密旨在可以同一時(shí)間實(shí)現(xiàn)加密與簽名，大大提高了通信效率。文獻(xiàn)[3-8]提出了多種簽密方案。

隨著計(jì)算機(jī)和密碼學(xué)的發(fā)展，公鑰密碼體制種類多樣，如何在不同的密碼系統(tǒng)之間進(jìn)行數(shù)據(jù)的安全通信一直都是研究者們關(guān)注的重點(diǎn)。異構(gòu)簽密的概念是2010年Sun[9]提出的，旨在解決不同密碼系統(tǒng)之間數(shù)據(jù)安全傳輸問(wèn)題。

異構(gòu)簽密主要是指TPKI、IDPKC、CLPKC之間的進(jìn)行異構(gòu)簽密。本文研究TPKI與IDPKC之間的異構(gòu)簽密方案，這兩類公鑰密碼體制的異構(gòu)簽密方案可以分成兩類：第一類，從TPKI到IDPKC[9]；第二類，從IDPKC到TPKI[10]。

目前設(shè)計(jì)的大多異構(gòu)簽密方案都是不能抗量子攻擊的，因?yàn)榉桨傅陌踩源蠖喽际腔趥鹘y(tǒng)數(shù)論問(wèn)題設(shè)計(jì)的。然而傳統(tǒng)的公鑰密碼體制在量子計(jì)算機(jī)的快速發(fā)展下已經(jīng)變得不再安全了，設(shè)計(jì)出抗量子攻擊的公鑰密碼體制已經(jīng)成為密碼研究的熱點(diǎn)和重點(diǎn)。格密碼是最有效的抗量子密碼的候選方案之一，因?yàn)楦衩艽a具有加解密速度快、計(jì)算簡(jiǎn)單、安全性高等特點(diǎn)。

文獻(xiàn)[11]構(gòu)造了第一個(gè)抗量子攻擊的基于格的PCK-to-IDPKC異構(gòu)簽密方案，其私鑰和公鑰的空間大小為O(n2)。本方案是在NTRU格上TPKI-to-IDPKC的異構(gòu)簽密方案，密鑰的空間大小是O(nlog(n))，與文獻(xiàn)[11]相比，密鑰更小，效率更高。

1 背景知識(shí)

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

設(shè)n、m、q都是整數(shù)，[n]={0,1,2,…，n-1}，poly(n)是n的任意多項(xiàng)式，[q/2]=mmodq∈(-q/2,q/2)。x←X是通配符，根據(jù)上下文的含義，若X是一個(gè)集合中的元素，則x←X表示把X賦值給x；若是X是一個(gè)集合，則x←X表示x是從X中均勻分布隨機(jī)抽取；若X為隨機(jī)變量的概率分布，則x←X表示x是以概率分布X進(jìn)行抽取的；若X是一個(gè)多項(xiàng)式時(shí)間算法，則x←X表示x是算法X的輸出。環(huán)R=Z[x]/(xn+1)，Rq=R/qR，q是素?cái)?shù)。

Extract(B，id)[12]算法：輸入是KeyGen生成的格基和一個(gè)唯一的身份id。然后算法執(zhí)行(s1,s2)←Guass-Sample(B,(t,0),σ)輸出的是私鑰skid=(s1,s2)，且滿足關(guān)系s1×h+s2=t=H1(id)。

1.2 困難問(wèn)題假設(shè)

R-LWE環(huán)上帶錯(cuò)學(xué)習(xí)問(wèn)題[14]：已知R=Z[x]/(xN+1)，a=2k，k≥1，q=1 mod 2n，a∈R隨機(jī)均勻分布，其中e∈R是服從某一正態(tài)分布Ψa的差錯(cuò)向量，已知b∈R，且b=a×s+e，則由a、b求解s的問(wèn)題就是R-LWE問(wèn)題。

2 TPKI-to-IDPKC異構(gòu)簽密的模型[16]

(1) 系統(tǒng)設(shè)置：算法由PKG(private key generator)執(zhí)行。選取n作為輸入的安全參數(shù)，輸出公開(kāi)的系統(tǒng)參數(shù)params和保密的主密鑰msk。

(2) TPKI密鑰生成算法：PKI系統(tǒng)為運(yùn)行算法為用戶生成公/私鑰對(duì)pks和sks。

(3) IDPKC密鑰提取算法：PKG運(yùn)行該算法，算法的輸入是接收者的身份id，輸出是接收者的私鑰skid。

(4) 簽密算法：輸入系統(tǒng)參數(shù)params，待發(fā)送的消息m，接收者身份id和公鑰pkid，發(fā)送者私鑰sks，輸出密文C。

(5) 解簽密算法：輸入密文C，系統(tǒng)參數(shù)params，接受者的私鑰skid，發(fā)送者的公鑰pks，運(yùn)行該算法輸出消息m或者錯(cuò)誤標(biāo)志符號(hào)“⊥”。

以上算法需要滿足：如果C=Signcrypt(sks,id,m)，則m=Unsigncrypt(skid,pks,C)，這樣可以保證異構(gòu)簽密方案的正確性。

3 安全性定義[16]

機(jī)密性和不可偽造性是保證設(shè)計(jì)的異構(gòu)簽密方案的必要條件，即要求設(shè)計(jì)的方案在適應(yīng)性選擇密文攻擊下具有不可區(qū)分性和在適應(yīng)性選擇消息攻擊下是不可偽造[16]。以下進(jìn)行證明。

定義：在由多項(xiàng)式有界的敵手A和挑戰(zhàn)者F進(jìn)行的如下游戲中，若不存在敵手A可以以一個(gè)不可忽略的優(yōu)勢(shì)在游戲中獲勝，則說(shuō)明TPKI-to-IDPKC異構(gòu)簽密方案在適應(yīng)性選擇密文攻擊下的不可區(qū)分(IND-HSC-CCA2安全)。

1) 初始階段：F運(yùn)行“系統(tǒng)設(shè)置算法”和“TPKI密鑰生成算法”生成系統(tǒng)參數(shù)params及發(fā)送者的公鑰pks/私鑰sks對(duì)，將生成的系統(tǒng)參數(shù)params和公/私鑰對(duì)(pks/sks)一起發(fā)送給敵手A。

2) 階段1：F與A進(jìn)行如下的交互：A可以進(jìn)行多項(xiàng)式有界次數(shù)的密鑰提取查詢和解簽密查詢，F(xiàn)負(fù)責(zé)應(yīng)答。

(1) IDPKC的密鑰查詢：

A將身份id發(fā)送給F，F(xiàn)通過(guò)IDPKC密鑰提取算法生成一個(gè)與身份id相對(duì)應(yīng)的私鑰skid，將其返回給敵手A。

(2) 解簽密查詢：

A首先提交一個(gè)接收者的身份id、一個(gè)密文C給F，F(xiàn)將身份id和密文C作為輸入運(yùn)行IDPKC密鑰提取算法得到接收者的私鑰skid，然后執(zhí)行解簽密算法Unsigncrypt(skid,pks,C)，將其結(jié)果返回給A。

3) 挑戰(zhàn)階段：階段1是否終止何時(shí)進(jìn)入挑戰(zhàn)階段都是由A來(lái)決定的，A選擇兩個(gè)明文且l(m1)=l(m2)、接受者的身份id0并將其發(fā)送給F。其中的身份沒(méi)有被執(zhí)行過(guò)IDPKC密鑰提取算法查詢。F隨機(jī)選擇一個(gè)比特b∈{0,1}，計(jì)算C0=Signcrypt(sks,id0,mb)。并把C0發(fā)送給A作為挑戰(zhàn)密文。

4) 階段2：在此階段A除了不能查詢id0的私鑰和對(duì)(id0,C0)執(zhí)行對(duì)id0的解簽密查詢之外可以執(zhí)行階段1中其他多項(xiàng)式有界查詢。

5) 猜測(cè)階段：A輸出一個(gè)對(duì)b的猜測(cè)b′，若二者相等則說(shuō)明敵手A贏得了游戲。

A在游戲中的優(yōu)勢(shì)可以定義為Adv(A)=|2Pr[b′=b]-1|，其中Pr[b′=b]表示b′=b的概率。

定義：多項(xiàng)式敵手A和挑戰(zhàn)者F進(jìn)行游戲，在游戲中沒(méi)有任何一個(gè)敵手A可以以一個(gè)不可忽略的優(yōu)勢(shì)贏得比賽，則說(shuō)明TPKI-to-IDPKC異構(gòu)簽密方案具有適應(yīng)性選擇消息攻擊下的不可偽造性(EUF-HSC-CMA安全)。

1) 初始階段：F運(yùn)行系統(tǒng)設(shè)置算法，將生成主密鑰msk和系統(tǒng)參數(shù)params發(fā)送給敵手A。F運(yùn)行TPKI得到發(fā)送者的公/私鑰對(duì)pks/sks并將公/私鑰對(duì)pks/sks發(fā)送給A。

2) 攻擊階段：A執(zhí)行簽密查詢，詢問(wèn)是多項(xiàng)式有界次數(shù)的，A提交給挑戰(zhàn)者F一個(gè)接收者身份id和一個(gè)消息m，接收后F運(yùn)行簽密算法C=Signcrypt(sks,id,m)，并將得到的密文C發(fā)送給A。

3) 偽造階段：A生成一個(gè)身份為id0和一個(gè)新的簽密密文C0，如果新的id0和密文C0對(duì)以下兩個(gè)條件都是滿足的，則說(shuō)明A贏得了游戲：

(1) Unsigncrypt(sk0,pks,C0)，返回的是消息m0。

(2)A沒(méi)有詢問(wèn)過(guò)關(guān)于id0和m0的簽密查詢。則稱A贏得了游戲。

F的優(yōu)勢(shì)被定義為：F贏得了游戲的概率。

4 方案構(gòu)造

3) IDPKC密鑰提取算法：接收者R提交身份id∈{0,1}*，通過(guò)PKG計(jì)算得到t=H1(id)和主私鑰msk，然后在運(yùn)行密鑰提取算法Extract(B,id)，輸出skid=(s1,s2)，滿足s1+s2×h=t=H1(id)。

4) 簽密算法：輸入發(fā)送者S的消息m∈{0,1}l、私鑰sks和公鑰pks，接收者R提交的身份id和公鑰pkid。運(yùn)行以下算法:

(1) 運(yùn)行算法Gauss-Sample(B,H2(m,ξ),σ)得到(e,d)∈Rn×Rn。

(2) 隨機(jī)選擇r，e1,e2∈DZN,s，t=H1(id)，作如下計(jì)算:

(3) 計(jì)算c4=m⊕H3(e,d)，輸出密文C=(c1，c2，c3，c4，ξ)。

5) 解簽密算法：輸入接收者的身份id，簽密密文C=(c1，c2，c3，c4，ξ)，以及接受者的私鑰skid，運(yùn)行如下算法。

(2) 計(jì)算m=c⊕H3(e,d)得到m。

5 方案分析

5.1 正確性分析

可知skid=(s1,s2)，且H1(id)=t=s2×h+s1，計(jì)算：

又因?yàn)閏4=m⊕H3(e,d),所以m=c⊕H3(e,d)。

綜上所述，算法的正確性得到證明。

5.2 安全性分析

定理1在隨機(jī)預(yù)言機(jī)模型下，假設(shè)R-LWE困難問(wèn)題，TPKI-to-IDPKC方案在適應(yīng)性選擇密文攻擊下存在不可偽造性，即異構(gòu)簽密體制是IND-HSC-CCA2安全的。

證明：F是R-LWE問(wèn)題的挑戰(zhàn)者，A是攻擊者，F(xiàn)給定了一個(gè)R-LWE問(wèn)題的實(shí)例：(h，c1=r×h+e1)。F的目標(biāo)就是能使用敵手A以概率ε′≥1/Q1ε-Q2Qu/2n+l求得R-LWE的解，其中ε是攻擊方案作為T(mén)PKI-to-IDPKC異構(gòu)簽密體制的IND-HSC-CCA2安全性不可忽略的概率。Q1表示進(jìn)行H1查詢的次數(shù)，Q2表示進(jìn)行H2查詢的次數(shù)，Qu表示解簽密的查詢次數(shù)。挑戰(zhàn)者F和敵手A間的交互如下：

1) 初始階段：F運(yùn)行系統(tǒng)設(shè)置算法，將生成系統(tǒng)參數(shù)parmas發(fā)送給敵手A；并運(yùn)行TPKI密鑰生成算法獲得發(fā)送者的公鑰pks和私鑰sks對(duì)，將其發(fā)送給敵手A。

2) 階段1：在F與A的模擬過(guò)程中，A可以對(duì)簽密隨機(jī)預(yù)言機(jī)執(zhí)行多項(xiàng)式有界次數(shù)的適應(yīng)性查詢，規(guī)定優(yōu)先進(jìn)行hash查詢，F(xiàn)負(fù)責(zé)應(yīng)答。

①H1(id)查詢：

F將(id0，B0，t0，⊥)保存在列表H1，A進(jìn)行H1查詢，若列表中存在返回t0，否則運(yùn)算KeyGenBwithExtract(B,id)得到sksi和ti，并將新的(idi，Bi，ti=H1(idi)，hi)存在列表H1中，并返回ti。

②H2(mi，ζi)查詢：

③H3(ei，di)查詢：

隨機(jī)選取h3i∈{0,1}l,把(ei，di，h3i)存放在H3列表中，返回h3i。

④ 接收者密鑰查詢(idi)。

⑤ 遍歷H1列表，查找(idi，Bi，ti，hi)，返回Bi。

⑥ 解簽密查詢(idi,Ci=(c1,c2,c3,c4,ζ))。

4) 階段2：A可以執(zhí)行階段1中查詢id0私鑰和對(duì)(id0,C*)進(jìn)行解簽密查詢以外的所有操作。

5) 猜測(cè)階段：A輸出猜測(cè)。

定義E為A查詢H3(ei,di)的事件，使用事件E對(duì)真實(shí)的攻擊進(jìn)行模擬，這樣就可以獲取真實(shí)攻擊的分析。

在真實(shí)的攻擊中，Pr[b′=b]≤

Pr[b′=b]EPr[E]+Pr[E]=

Pr[b′=b|E](1-Pr[E])+Pr[E]=

1/2+1/2·Pr[E]

因此，ε=|2Pr[b′=b-1]|≤Pr[E]。

若在實(shí)際的攻擊中合法的密文在進(jìn)行解簽密查詢過(guò)程中被拒絕，那么在H3列表中(ei，di，h3i)、(mi,ζi,h2i)是唯一可以與之對(duì)應(yīng)的，那么在實(shí)際中拒絕合法密文的概率小于等于Q2/2n+l。

此外，id*=id0的概率是1/Q1。所以ε′≥1/Q1·ε-(Q2Qu)/2n+l，如果ε′也是不可忽略的。這與RLWE問(wèn)題的難解性相矛盾。若R-LWE問(wèn)題的困難性是存在的，則可以稱不存在敵手A能夠以不可忽略的概率攻擊方案TPKI-to-IDPKC類型異構(gòu)簽密體制。在R-LWE困難問(wèn)題下，TPKI-to-IDPKC類型異構(gòu)簽密方案是IND-HSC-CCA2安全的。

定理2EUF-HSC-CMA安全性。

假設(shè)R-SIS問(wèn)題是難解的，則說(shuō)明方案作為T(mén)PKI-to-IDPKC類型異構(gòu)簽密體制是EUF-HSC-CMA安全的。

證明：假設(shè)存在敵手F以不可忽略的優(yōu)勢(shì)攻擊方案的EUF-HSC-CMA安全性，就會(huì)存在挑戰(zhàn)者A，它能夠借助F的攻擊能力來(lái)攻擊GPV全面方案的EUF-HSC-CMA安全性。F和A的交互如下：

1) 初始階段：A獲得簽密方案的驗(yàn)證公鑰pks，運(yùn)行KeyGen算法生成mpk和msk。其中mpk和msk是主公鑰和主私鑰。A將pks、mpk、msk發(fā)送給F。

C做如下操作得到一個(gè)新的簽名。

(1) 計(jì)算t*=H1(id*)，運(yùn)行算法Extract(B*，id*)。得到pkid和skid。

從上述的證明過(guò)程可以得出，若F偽造合法密文的概率ε是不可忽略的，則說(shuō)明A偽造的簽名的的概率是不可忽略的。從文獻(xiàn)可以知道在R-SIS問(wèn)題困難性的假設(shè)下，簽名是EFU-CMA安全的，所以不存在敵手F能夠以不可忽略的優(yōu)勢(shì)攻擊方案的EUD-HCS-CMA安全性。因此在ISIS的困難問(wèn)題假設(shè)下，該方案是EUF-HCS-CMA安全的。

6 結(jié) 語(yǔ)

異構(gòu)簽密是一個(gè)非常重要的研究方向，在計(jì)算機(jī)通信網(wǎng)絡(luò)中有很重要的研究?jī)r(jià)值，本文使用了理想格上的困難問(wèn)題和格上的簽密方案，設(shè)計(jì)了一個(gè)基于NTRU的TPKI-to-IDPKC異構(gòu)簽密方案。方案具有密鑰量小、效率高的優(yōu)點(diǎn)，且能抗量子攻擊，并在隨機(jī)預(yù)言機(jī)模型下證明了NTRU異構(gòu)簽密方案的安全性。下一步的工作是設(shè)計(jì)標(biāo)準(zhǔn)模型下的異構(gòu)簽密方案或者設(shè)計(jì)出各種有特殊性質(zhì)的簽密，例如：門(mén)限異構(gòu)簽密方案、代理異構(gòu)簽密方案、盲異構(gòu)簽密方案等。