基于格的代理簽名方案＊

夏 峰，楊 波，馬 莎，孫微微，張明武

（1.華南農(nóng)業(yè)大學(xué)信息學(xué)院，廣東廣州 510642；2.海南師范大學(xué)信息科學(xué)技術(shù)學(xué)院，海南海口 571158）

基于格的代理簽名方案＊

夏 峰1，2，楊 波1?，馬 莎1，孫微微1，張明武1

（1.華南農(nóng)業(yè)大學(xué)信息學(xué)院，廣東廣州 510642；2.海南師范大學(xué)信息科學(xué)技術(shù)學(xué)院，海南海口 571158）

利用原像采樣單向陷門函數(shù)和盆景樹下格的擴(kuò)展及格基的隨機(jī)化方法，基于格構(gòu)造了一個(gè)代理簽名方案.在隨機(jī)預(yù)言機(jī)下，基于平均情況的小整數(shù)解問題SIS（Small Integer Solution）和非均勻小整數(shù)解問題ISIS（Inhomogeneous Small Integer Solution）的困難性假設(shè)，證明該方案在適應(yīng)性選擇消息攻擊下是安全的.與基于數(shù)論假設(shè)方案相比，該方案密鑰空間較大，但計(jì)算效率更高.

格；隨機(jī)預(yù)言機(jī)；代理簽名；原像采樣

為高效、安全地實(shí)現(xiàn)數(shù)字簽名的委托，1996年，Mambo等［1］提出了代理簽名的概念.此后，代理簽名體制得到了廣泛、深入的研究，出現(xiàn)了許多基于大整數(shù)分解和離散對(duì)數(shù)問題的代理簽名方案，并且，這種簽名機(jī)制已被廣泛地應(yīng)用到網(wǎng)格計(jì)算、電子交易、移動(dòng)通信和移動(dòng)代理等環(huán)境.然而，若量子計(jì)算機(jī)得到應(yīng)用，基于數(shù)論假設(shè)的大整數(shù)分解問題和離散對(duì)數(shù)問題都可在多項(xiàng)式時(shí)間內(nèi)得到解決［2］，大量基于數(shù)論假設(shè)的代理簽名方案將不再安全.因此，設(shè)計(jì)能抵抗量子攻擊的代理簽名方案成為該領(lǐng)域需解決的問題.近年來，基于格構(gòu)造新型密碼系統(tǒng)因具有較高的漸近效率、運(yùn)算簡(jiǎn)單（通常只需要線性運(yùn)算）、能抵抗量子攻擊和存在最壞情況下的隨機(jī)實(shí)例等特點(diǎn)，成為公鑰密碼領(lǐng)域的研究熱點(diǎn)，并取得了一系列的研究成果［3－7］.本文基于格中平均情況下SIS和ISIS問題的困難性假設(shè)，利用帶原像采樣的單向陷門函數(shù)和盆景樹下格的擴(kuò)展及格基的隨機(jī)化方法，基于格構(gòu)造了一個(gè)高效、安全的代理簽名方案.

1 預(yù)備知識(shí)

1.1 符號(hào)說明

1.2 格上的困難問題

1.3 格上的高斯分布

對(duì)于任意s＞0，定義以向量c為中心，參數(shù)為s的高斯分布為：

格上的離散高斯分布為：

式（1），式（2）中，若s，c分別是1和0，在書寫時(shí)則可省略.離散高斯分布是一個(gè)條件分布函數(shù)，是由對(duì)格中的元素按高斯分布取樣所獲得的分布.

高斯分布格點(diǎn)范圍的大小主要由s來決定，當(dāng)s的取值滿足一定條件時(shí)，則在離散高斯分布中采樣輸出格點(diǎn)的分布及長(zhǎng)度會(huì)有一些比較好的性質(zhì)，下面的定義給出與s相關(guān)的平滑參數(shù)的定義.

定義5［9］平滑參數(shù)（The smoothing parameter）.設(shè)任意一個(gè)n維格Λ和ε＞0，定義平滑參數(shù)ηε（Λ）為最小的s＞0，使得ρ1／s（Λ＊＼｛0｝）≤ε.

當(dāng)s≥ηε（Λ）時(shí)，定理2給出了對(duì)離散高斯分布中的向量進(jìn)行采樣時(shí)獲得向量概率的最大上界.

定理2［3］對(duì)于任意秩為k的n維格Λ，c∈Rn，正數(shù)ε＜exp（－4π）和s≥ηε（Λ），對(duì)每一個(gè)x∈Λ有：

特別地，DΛ，s，c（x）的最小熵為k－1.

1.4 采樣算法和原像采樣單向陷門函數(shù)

文獻(xiàn)［3］給出了運(yùn)行時(shí)間約為格基長(zhǎng)度的O（n2）的采樣算法SampleD（B，s，c），通過該采樣算法獲得的向量滿足下面的定理.和，則以壓倒性的概率，u＝Aemodq在

定理4描述若以格的離散高斯分布上采樣所得的格點(diǎn)作為輸入，則其與隨機(jī)均勻選取的矩陣向量積在該矩陣所生成的向量空間上也是均勻分布的.

定理4［3］設(shè)n和q為正整數(shù)且q為素?cái)?shù)，令m≥2nlgq，對(duì)于所有的時(shí)，基于平均情況問題SIS和I-SIS的單向陷門函數(shù)，簡(jiǎn)單描述如下［3］：

1）按定理5生成（A，S）.其中，A為公鑰，S為私鑰.

2）函數(shù)fA定義為fA（e）＝Ae（modq），定義域?yàn)樯鲜墙y(tǒng)計(jì)均勻分布的.

基于平均情況問題SIS和ISIS，文獻(xiàn)［3］構(gòu)造了一個(gè)單向陷門函數(shù)，在描述該函數(shù)之前，我們給出下面定理.

定理5［10］給定任意素?cái)?shù)q＝poly（n）和任意m≥5nlgq，存在一個(gè)概率多項(xiàng)式算法，輸入1n，輸出矩陣A∈Zn×mq和一個(gè)滿秩的集合S?Λ⊥（A，q），A在Zn×mq上是統(tǒng)計(jì)均勻分布的，并且‖S‖≤L＝m2.5.

在文獻(xiàn)［3］中，Gentry等人將L優(yōu)化到m1＋ε.，值域?yàn)镽n＝Znq.e的輸入分布滿足DZm，s.

3）單向陷門求逆算法SampleISIS（A，S，s，u）求得f－1A（u）如下：先計(jì)算t∈Zm，然后利用高斯采樣算法用私鑰S采樣出v←DΛ⊥，s，－t，輸出e＝v＋t.e即為u在給定定義域的原像.

定理6［3］算法SampleISIS（A，S，s，u）若是單向的，則平均情況是困難的.而且若fA（e）＝Ae（modq）是抗原像采樣碰撞攻擊的，則平均情況是困難的.

1.5 格的擴(kuò)展和格基的隨機(jī)化操作

在2010年的歐密會(huì)上，David Cash等［11］把盆景樹的思想引入到格中，給出了對(duì)格進(jìn)行擴(kuò)展（使其秩增加）和對(duì)基進(jìn)行隨機(jī)化操作的具體方法.下面給出本文中要用到的有關(guān)定理和定義.

定理7［12］每一個(gè)格Λ?Zm都可用埃爾米特插值標(biāo)準(zhǔn)形式（Hermite normal form）唯一地表示出來，它可用給定格的任意基B高效地計(jì)算出來，寫成HNF（B）.

定理10說明了SR和S相互獨(dú)立，即由SR得不到任何S的特定信息，通過該定理，可有效地實(shí)現(xiàn)格基的委托，即把原來的基隨機(jī)化之后，得到新的基，且從新的基無法推導(dǎo)出原來的基.該定理主要用到定理7和定理8的結(jié)果.

2 基于格的代理簽名方案

2.1 方案描述

定義6 基于格的代理簽名方案（LatticeProSig）包括系統(tǒng)密鑰生成（SigKeyGen）、代理密鑰生成（ProSigkeyGen）、代理簽名（ProSig）和簽名驗(yàn)證（Ver）4個(gè)算法，具體描述如下.

2.2 安全性證明

對(duì)該定理的證明分為3個(gè)部分：首先證明代理密鑰不泄露原始簽名者私鑰的任何信息，而且，不知道原始簽名者私鑰，任何人無法偽造代理密鑰；其次證明任何不知道代理密鑰的第3方無法偽造代理簽名；最后證明不知道代理簽名的私鑰者無法冒充該代理人偽造代理簽名.

證 先證明第1部分：在用算法RandBasis（S?，s）生成Sδ時(shí)，根據(jù)定理10，這是一個(gè)隨機(jī)化的操作，生成的Sδ與S?相互獨(dú)立，從Sδ得不到任何關(guān)于S?的特定信息，從而，無法從Sδ求出S?，進(jìn)一步，也無法求出S′.相反，因?yàn)锳′和都是均勻隨機(jī)選取的，所以A′‖也是均勻隨機(jī)的，在給定A′‖時(shí)，假設(shè)一個(gè)敵手在不知道原始簽名者的私鑰S′時(shí)，能偽造代理密鑰Sδ，則他可通過采樣算法SampleD（S，sδ，0）獲取eδ，使得（A′‖）eδ＝0（modq），這樣，他就解決了在下的平均情況SI問題，這與定理1矛盾.因此，在不知道原始簽名者的私鑰時(shí)，敵手無法偽造代理密鑰.第1部分得證.

第2部分是證明H（M）＝（A′‖）eδ的安全性，我們將基于隨機(jī)預(yù)言機(jī)模型證明它能抗擊適應(yīng)性選擇消息攻擊.證明方法與文獻(xiàn)［3］提出的證明方法類似，證明如下：

假設(shè)存在一個(gè)敵手AI能偽造代理簽名，則存在一個(gè)多項(xiàng)式時(shí)間算法SI能找到關(guān)于H（·）的一對(duì)碰撞.

H（·）詢問：對(duì)AI每一個(gè)不同的M∈｛0，1｝＊，SI先查找本地存儲(chǔ)是否有（M，eδ），若有，則返回H（M）＝（A‖）eδ，否則用采樣算法SampleD（S，sδ，0）隨機(jī)獲取eδ，計(jì)算H（M）＝（A‖Aˉ）eδ，并將其返回給AI，并保留（M，eδ）.

簽名詢問：當(dāng)AI詢問M的簽名時(shí)，SI查表（M，eδ），并將eδ做為M的簽名返回給AI.

最終，AI將偽造出一對(duì)有效的簽名（M＊，eM），因?yàn)锳I在偽造簽名時(shí)必須要對(duì)M＊進(jìn)行H（·）詢問，從而，SI在本地保留（M＊），根據(jù)定理4，eδ←SampleD（S，sδ，0）有均勻輸出的特性，根據(jù)定理2，在隨機(jī)均勻地給定H（·）的情況下，發(fā)生的概率最大值為），對(duì)于足夠大的m＋mˉ和足夠小的的概率可以忽略，所以有.從而，SI找到了，使得（A，即找到，使得，這與是困難的相矛盾.第2部分得證.

第3部分是證明u＝A″e(cuò)′的安全性.這部分證明與第2部分證明類似，在這里不做詳細(xì)描述.

證畢.

若同一個(gè)原始簽名者要選擇多個(gè)代理人，可選擇不同的Aˉ（列數(shù)相同），并分別生成不同的代理密鑰，定理12說明這并不影響代理簽名的安全性.

定理12 同一個(gè)原始簽名人的不同代理者無法從自己的代理密鑰推導(dǎo)出其他代理者的密鑰.

證畢.

由以上證明可知，完全可將代理者信息用雜湊函數(shù)計(jì)算后陷入到中而并不影響簽名的安全性.

2.3 效率分析

該代理簽名方案的效率主要取決于代理簽名和簽名驗(yàn)證部分的效率，密鑰的長(zhǎng)度約為O（n2），采樣算法所需運(yùn)行的時(shí)間約為輸入?yún)?shù)長(zhǎng)度的O（n2），驗(yàn)證eδ，e′范圍所需的時(shí)間為O（n）.此外，還需要做2個(gè)雜湊函數(shù)的運(yùn)算和2個(gè)向量的線性運(yùn)算即可.在效率上，與基于數(shù)論的代理簽名方案相比，其缺點(diǎn)是密鑰長(zhǎng)度比效大，但不需要模指數(shù)運(yùn)算，其計(jì)算效率顯然更高.

3 結(jié)束語

基于格的密碼體制在最近幾年有了較快的發(fā)展，構(gòu)造基于格的簽名體制主要依賴于平均情況SIS問題的困難性假設(shè)，而盆景樹下格的擴(kuò)展和格基的隨機(jī)化方法在構(gòu)造具有某些特殊屬性的簽名體制方面有著重要的應(yīng)用.本文利用帶原像采樣的單向陷門函數(shù)和盆景樹下格的擴(kuò)展和格基的隨機(jī)化方法，構(gòu)建了一個(gè)基于格的代理簽名方案，并基于隨機(jī)預(yù)言模型，證明該方案在選擇消息攻擊下是可證安全的.與傳統(tǒng)的基于數(shù)論的代理簽名方案相比，該方案的密鑰空間較大，但運(yùn)算簡(jiǎn)單（只需線性運(yùn)算），能抵抗量子攻擊.

［1］ MAMBO M，USUDA K，OKAMOTO E.Proxy signatures for delegating signing operation［C］／／Proc 3rd ACM Conference on Computer and Communications Security.New York：ACM，1996：48－57.

［2］ SHOR P W.Polynomial-time algorithm for prime factorization and discrete logarithm on a quantum computer［J］.SIAM Journal on Computing，1997，26（5）：1484－1509.

［3］ GENTRY C，PEIKERT C，VAIKUNTANATHAN V.Trapdoors for hard lattices and new cryptographic constructions［C］／／Proc 40th ACM Symp on Theory of Computing（STOC）.New York：ACM，2008：197－206.

［4］ REGEV O.On lattices，learning with errors，random linear codes，and cryptography［J］.Journal of the ACM，2009，56（6）：1－40.

［5］ PEIKERT C.Public-key cryptosystems from the worst-case shortest vector problem［C］／／Proc 41st ACM Symp on Theory of Computing（STOC）.New York：ACM，2009：333－342.

［6］ AGRAWAL S，BONEH D，BOYEN X.Efficient lattice（H）IBE in the standard model［C］／／Advances in Cryptology-Eurocrypt 2010.Berlin：Springer Verlag，2010：553－572.

［7］ LYUBASHEVSKY V，PEIKERT C，REGEV O.On ideal lattices and learning with errors over rings［C］／／Advances in Cryptology-Eurocrypt 2010.Berlin：Springer Verlag，2010：1－23.

［8］ LENSTRA A K，LENSTRA H W，LOV′ASZ L.Factoring polynomials with rational coefficients［J］.Math Ann，1982，261（4）：515－534.

［9］ MICCIANCIO D，REGEV O.Worst-case to average-case reductions based on gaussian measures［J］.SIAM J Comput，2007，37（1）：267－302.

［10］AITAI M.Generating hard instances of the short basis problem［C］／／ICALP 1999.Berlin：Springer Verlag，1999：1－9.

［11］CASH D，HOFHEINZ D，KILTZ E，etal.Bonsai trees，or how to delegate a lattice basis［C］／／Advances in Cryptology－EUROCRYPT 2010.Berlin：Springer Verlag，2010：523－552.

［12］MICCIANCIO D，WARINSCHI B.A linear space algorithm for computing the Hermite normal form［C］／／Proceedings of the 2001 International Symposium on Symbolic and Algebraic Computation（ISSAC）.Berlin：Springer Verlag，2001：231－236.

Lattice-based Proxy Signature Scheme

XIA Feng1，2，YANG Bo1?，MA Sha1，SUN Wei-wei1，ZHANG Ming-wu1

（1.College of Informatics，South China Agricultural Univ，Guangzhou，Guangdong 510642，China；2.School of Information Science and Technology，Hainan Normal Univ，Haikou，Hainan 571158，China）

By using trapdoor functions with preimage sampling，lattice＇s growth，and lattice basis randomization in the bonsai tree，a lattice-based proxy signature scheme was proposed.The security of the proxy signature is based on the hardness of average-case SIS（Small Integer Solution）and ISIS（Inhomogeneous Small Integer Solution）.It is also existential unforgeability under adaptive chosen-message attack in the random oracle.Compared with the schemes based on factoring or discrete log，the public and secret keys of our scheme are larger，but it requires only linear operation on small integers.

lattice；random oracle；proxy signature；preimage sampling

TP309

A

1674-2974（2011）06-0084-05＊

2010-12-01

國(guó)家自然科學(xué)基金資助項(xiàng)目（60973134）；廣東省自然科學(xué)基金資助項(xiàng)目（10351806001000000）

夏 峰（1975－），男，湖南永州人，華南農(nóng)業(yè)大學(xué)博士研究生

?通訊聯(lián)系人，E-mail：byang＠scau.edu.cn