基于格的代理簽名方案＊

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

（1.華南農業(yè)大學信息學院，廣東廣州 510642；2.海南師范大學信息科學技術學院，海南?？?571158）

基于格的代理簽名方案＊

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

（1.華南農業(yè)大學信息學院，廣東廣州 510642；2.海南師范大學信息科學技術學院，海南?？?571158）

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

格；隨機預言機；代理簽名；原像采樣

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

1 預備知識

1.1 符號說明

1.2 格上的困難問題

1.3 格上的高斯分布

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

格上的離散高斯分布為：

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

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

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

當s≥ηε（Λ）時，定理2給出了對離散高斯分布中的向量進行采樣時獲得向量概率的最大上界.

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

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

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

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

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

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

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

2）函數(shù)fA定義為fA（e）＝Ae（modq），定義域為上是統(tǒng)計均勻分布的.

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

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

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

3）單向陷門求逆算法SampleISIS（A，S，s，u）求得f－1A（u）如下：先計算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 格的擴展和格基的隨機化操作

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

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

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

2 基于格的代理簽名方案

2.1 方案描述

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

2.2 安全性證明

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

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

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

假設存在一個敵手AI能偽造代理簽名，則存在一個多項式時間算法SI能找到關于H（·）的一對碰撞.

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

簽名詢問：當AI詢問M的簽名時，SI查表（M，eδ），并將eδ做為M的簽名返回給AI.

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

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

證畢.

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

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

證畢.

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

2.3 效率分析

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

3 結束語

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

［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

國家自然科學基金資助項目（60973134）；廣東省自然科學基金資助項目（10351806001000000）

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

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