基于Lattice的驗證方環簽名改進算法研究

趙洪建，達漢橋，胡元明

1.武漢大學后勤服務集團，武漢 430072

2.武漢大學測繪遙感信息工程國家重點實驗室，武漢 430072

3.武漢大學數學與統計學院，武漢 430072

基于Lattice的驗證方環簽名改進算法研究

趙洪建1，達漢橋2，胡元明3

1.武漢大學后勤服務集團，武漢 430072

2.武漢大學測繪遙感信息工程國家重點實驗室，武漢 430072

3.武漢大學數學與統計學院，武漢 430072

隨著信息安全技術的不斷發展，數字簽名技術也得到了廣泛關注，相關研究也在逐漸更新，如文獻[1]中提出一種基于特定目標的驗證方簽名安全機制，在此簽名方案中，盡管第三方機構尚不能辨別簽名源產生于第一簽名方還是中間驗證方，然而能夠辨別其驗證簽名源出自兩者之一。依據此研究結論，文獻[2]設計出一種強約束驗證方簽名安全機制，即SDVS簽名機制，此機制是在文獻[1]的基礎上進一步改進，強制約定只能通過特定驗證方才能進行驗證簽名，這樣保證了其私鑰數據信息的唯一安全性。文獻[3]對SDVS簽名機制的安全性、性能效率進行詳細分析與研究，即SDVS簽名機制保證了無法偽造、無法傳遞私鑰數據信息，同時也保證了第一簽名方身份合法性、隱私性等。正是基于這種安全性優勢，強約束安全機制逐漸引入到基于特定目標的驗證方簽名機制中，并使其在B2B、G2G等多種行業領域得到重要應用[4-6]。

依據格結構的高效安全性優點，可將其引入到信息安全公鑰密碼機制中，能夠抵抗多種入侵攻擊，如抗量子計算攻擊、隨機實例困難問題、最難實例困難問題等。所以，基于格結構的密碼安全機制逐漸受到研究學者青睞。如文獻[7]創造性地提出了在均等條件下的標準小整數解問題與在最差條件下的格結構一類NP問題的困難系數相一致，并給出了詳細地結論分析與證明。文獻[8]提出了錯誤學習機制問題（LWE）與最差條件下的格結構一類NP問題的困難系數相等，同樣作出了相關分析與證明。文獻[9]以格結構理論原理為基礎，形成了基于格結構的特定陷門單向函數，同時在隨機預言標準模型下，構造出一種新型技術架構的驗證方簽名安全機制。文獻[10]對文獻[9]進行了深入分析，在陷門單向函數理論原理基礎之上，設計出一種抽樣算法。文獻[11]對文獻[10]設計的抽樣算法進行了實踐拓展，基于標準模型條件下，將其抽樣算法應用于基于格結構的簽名安全機制中，并進行了安全性分析與證明。另外，針對隨機預言模型條件下出現的安全性不穩定等情況，文獻[12]設計出一種基于格結構的驗證方簽名安全機制。上述現有文獻均依據傳統簽名安全機制進行了相關研究，盡管在某些方面得到了廣泛推廣，然而其隱藏的安全隱私問題也較為常見。

目前，關于環簽名安全機制的分析與研究正處于如火如荼的階段，環簽名安全機制[13]對傳統簽名安全機制進行模式上的改進與更新，使其在構建標準模型條件下解決更多難解性問題，如基于離散對數困難問題等，并且因此，為了解決現有的數字簽名機制在多個應用中出現的各種隱私安全問題，本文利用環簽名安全機制代替傳統簽名安全機制，引入格結構理論原理，結合強約束安全機制，設計出一種基于格結構的強約束驗證方環簽名改進算法，即L_SRS算法。通過詳細安全與性能分析，表明L_SRS算法具有應用高安全性、簽名計算高效率性等優點。

1 概念知識

1.1 格結構（Lattice）

預先設定安全系統參數值是n，其非線性關系的數值向量均是列向量，矩陣A的正交化矩陣記作A?。如下：

1.2 困難問題

關于環簽名安全機制的研究是對傳統簽名安全機制進行模式上的改進與更新，使其在構建標準模型條件下解決更多難解性問題，本文所提算法安全性的理論基礎是標準模型條件下的格結構。關于標準模型條件下基于格結構的小整數解問題的困難性，其主要說明如下：

1.3 相關算法

1.4 強約束環簽名

環簽名安全機制引入強約束概念，主要有以下幾個子多項式時間算法組成：

（1）構建系統模型階段。n是系統模型輸入參數值。此部分是用戶Ui取得公鑰-密鑰鍵值對(PKt，SKt)的過程。注：假定任意Ui都具有隨機的公鑰數據信息，所以一個Ui對應唯一性的公鑰數據信息，如同用戶身份ID。

（2）環簽名階段。環結構R?S={U1，U2，…，Umax}是已知輸入參數，另外，包括簽名用戶Ui∈R、私鑰數據信息SKt與傳輸信息M，經過操作，輸出數據信息是環結構R對傳輸信息M的簽名值x。

（3）強約束驗證階段。輸入參數包括環結構R?S= {U1，U2，…，Umax}、傳輸信息M與（2）的輸出參數：簽名值x。經過操作，輸出數據信息是判定結果，即有效驗證（Valid）與無效驗證（Invalid）。

從上述描述可知，對于一個具有安全性、正確性的強約束環簽名安全機制而言，若簽名用戶Ui∈R保持誠實狀態，那么強約束環簽名安全機制的第（3）驗證階段其以有效驗證（Valid）作為輸出結果的概率最大。

2 形式化與模型分析

關于簽名安全機制而言，形式化描述與安全模型的分析是至關重要的，接下來將進行簡略介紹。

2.1 形式化描述

假定簽名用戶是WO，特定驗證方是NI，那么一個傳統的驗證方簽名安全機制（以SDVS為示例）主要由以下幾個重要部分構成，即包括多個子多項式時間算法，如下：

（1）公共系統參數產生部分：n是輸入系統安全參數值，para是輸出公共系統參數值。

（2）密鑰操作部分：para作為輸入，產生公鑰-私鑰鍵值對(pki，ski)(i∈{WO，NI})。

（3）環簽名部分：將第（2）部分輸出結果，即公鑰-私鑰鍵值對(pki，ski)作為此部分輸入，另加入傳輸信息M，輸出結果是簽名σ。

（4）驗證部分：輸入參數包括(pki，ski)、傳輸信息M以及第（3）輸出結果，即簽名σ。在簽名σ處于Valid狀態下，此部分輸出結果是接受（Accept），反之拒絕（Reject）。

（5）副本操作處理部分：輸入參數包括(pki，ski)、傳輸信息M，經過此部分操作處理之后，輸出結果是與第（3）部分輸出的簽名σ不可辨別的簽名副本數據信息σ′。

2.2 安全模型

一般條件下，簽名機制的安全模型具體內容包括以下幾個方面，如下：

（1）強不可偽造性。強不可偽造性是在傳統無法偽造性基礎上，達到了更具安全性要求，即強約定不可偽造性。強不可偽造性只允許WO與NI兩者可以偽造相關簽名數據信息，此安全性描述可通過一種挑戰方-攻擊敵方的形式化游戲概括，具體如下：

①構造階段：首先預執行公共系統參數產生部分，得到para，其次經過密鑰操作部分，獲取公鑰-私鑰鍵值對(pki，ski)(i∈{WO，NI})，與此同時將其(pkWO，skWO)傳輸給攻擊敵方。

②環簽名詢問-應答階段：攻擊敵方提交傳輸信息M，挑戰方執行環簽名部分，輸出其有效簽名σ，且將其σ回饋給攻擊敵方。

③強約定詢問-應答階段：攻擊敵方提交簽名數據信息對(M，σ)，挑戰方執行強約定驗證部分，返回輸出結果給攻擊敵方。

④挑戰方執行偽造階段：此部分輸出結果是偽造信息(M*，σ*)，假定簽名σ*有效，M*沒有再次經過環簽名詢問-應答階段，那么攻擊敵方戰勝了挑戰方。

說明6若如上的攻擊敵方不存在，那么在形式化游戲中執行時間周期將小于等于t，環簽名詢問-應答階段的次數至多是qsign，強約定詢問-應答階段的次數至多是qverify，攻擊敵方戰勝挑戰方的概率將大于等于δ，那么此種強約束驗證方簽名安全機制對(t，qsign，qverify，δ)具有強不可偽造性。

（2）強不可傳遞性。對預先設定的傳輸消息M與簽名σ而言，其不管是簽名用戶WO還是特定環簽名驗證方NI，對其簽名數據信息都是無條件無法傳遞的。

（3）簽名用戶的隱私信息安全性。對預先設定的傳輸消息M與其對應的一個簽名而言，不管是簽名用戶WO還是特定環簽名驗證方NI，假定無NI私鑰信息，那么一個用戶需要判定是WO0還是WO1獲取了此簽名在操作處理上是不可行的，從而保證了簽名用戶的隱私信息安全性。

3 L_SRS算法

本文以隨機預言模型下的相關簽名方案為理論基礎，提出了一種基于格結構（Lattice）的強約束驗證方環簽名改進算法，即L_SRS算法，其具體描述如下：

（1）公共系統參數產生部分(Setup(1n))：預先假定相關參數q≥2，m≥6nlgq，傳輸信息M={0，1}l，選取隨機集合矩陣信息C0，C1，…，Cl∈Zqn×m與實體參數向量u∈Zqn；使。那么para={n，q，m，l，C0，C1…Cl，u，L，s}。

4 安全性分析

4.1 正確性

4.2 強不可偽造性

4.3 強不可傳遞性

4.4 簽名用戶的隱私安全

由于(NI，p=NIT·s+gmodq)為一個錯誤學習問題（LWE）示例，NI可采取私鑰信息SNI計算得出s向量，那么強約束驗證環簽名信息e的有效性，但除了NI之外，無任何一方可依據p獲取s，反之任何一方都可成功計算求出LWE問題的解，可知任何一方不可能強約束驗證簽名信息的有效性，從而L_SRS算法保證了簽名用戶隱私安全。

4.5 安全性比較

現比較已有的標準模型下簽名安全機制的相關安全性，對是否具有強不可偽造性、強不可傳遞性、簽名用戶的隱私安全性等方面進行了縱向對比分析，如表1所示（注：√表示具有，×表示不具有）。

5 性能分析

本章將從性能效率方面橫向比較現有的標準模型下簽名安全機制的性能與效率，主要對比點由簽名時間、驗證簽名時間與簽名長度等組成。如表2所示（注：l表示簽名環數量值；TE、TS表示ExtBasis與SamplePre子算法操作時間周期；TM表示m次向量操作時間周期；k屬于正整數常量；m是大于1的正整數；d是隨機常量）。

表2 幾種標準模型下的類似簽名機制性能對比

現對表2中各部分進行詳細分析，如下：

（1）簽名時間方面：DVS算法的簽名時間周期需要m(L+d)TE+m(L+d+1)TS，SDVS算法則在DVS算法基礎上通過添加m(L+k-1)次向量操作，實現了無需Ext-Basis子算法處理機制，優化了SamplePre子算法操作流程，簽名時間周期減少到只需mTS+m(L+k-1)TM，本文的L_SRS算法繼續對SDVS算法進行改進，優化了向量操作處理機制，減少了向量操作時間周期，簽名時間周期得到進一步優化，僅需mTS+m(L+1)TM。

（2）驗證簽名時間方面：現有的簽名算法依據理論原理，在驗證階段相關操作僅與向量操作處理機制有關，因此，DVS算法的驗證簽名時間周期需要m(L+d+1)TM，SVDS算法通過優化DVS算法驗證簽名過程中的驗證流程，減低了驗證簽名時間周期，只需m(L+k)TM，本文的L_SRS算法融合了SVDS與其他相關簽名算法的驗證簽名優點，實現了驗證簽名次優化，其驗證簽名時間周期僅需m(L+2)TM。

（3）簽名長度方面：依據相關簽名算法原理與簽名機制，DVS算法的簽名長度是m(L+d+1)；SVDS算法通過對DVS的簽名過程優化，其簽名長度得到減少，只需m(L+k)+1，本文的L_SRS算法添加了一種強約束安全機制，實現了進一步優化，在保證高簽名安全性的前提下，簽名長度得到了進一步縮短，僅需m(L+2)。

從上面分析可知，在保證高簽名安全性的前提下，本文的L_SRS強約束環簽名算法比傳統的、在標準模型下的DVS、SDVS簽名算法性能效率更高。

6 結束語

本文針對現有的數字簽名機制在發放軟件著作、專利許可證以及項目工程招投標等應用中出現的各種隱私安全問題，以隨機預言模型下的相關簽名方案為理論基礎，提出了一種基于格結構（Lattice）的強約束驗證方環簽名改進算法，即L_SRS算法，該算法在標準模型下給出了詳實的安全性分析，依據標準的小整數解困難問題，L_SRS算法增加了一種強約束安全機制，能夠有效抵抗適應性選擇消息攻擊，對其具有強不可偽造性。通過安全性與性能分析，本文的L_SRS算法具有應用高安全性、簽名計算高效率性等特點。

[1]Ki J，Hwang J Y，Nyang D，et al.Constructing strong identity-based designated verifier signature with self-unverifiability[J].ETRI Journal，2012，34（2）：235-244.

[2]李繼國，姜平進.標準模型下可證安全的基于身份的高效簽名方案[J].計算機學報，2009，32（11）：2130-2136.

[3]Boyen X.Lattice mixing and vanishing trapdoors：a framework for fully secure short signatures and more[C]//Lecture Notes in Computer Science 6056：Proceedings of the 13th International Conference on Practice and Theory in Public Key Cryptography（PKC’10）.Berlin：Springer-Verlag，2010：499-517.

[4]Alwen J，Peikert C.Generating shorter bases for hard random lattices[J].Theory of Computing Systems，2011，48（3）：535-553.

[5]張建中，郭振，蘭建青.一個基于身份的無需可信中心的簽名方案[J].計算機工程與應用，2010，46（13）：80-81.

[6]Gordon D，Katz J，Vaikuntanathan V.A group signature scheme from lattice assumptions[C]//LNCS 6477：Proceedings of the ASIACRYPT 2010.Berlin：Springer Verlag， 2010：395-412.

[7]Galindo D，Herranz J，Kiltz E.On the generic construction of identity-based signatures with additional properties[C]// LNCS 4284：Proceedings of the ASIACRYPT 2006.Berlin：Springer-Verlag，2006：178-193.

[8]Stehle D，Steinfeld R，Tanaka K，et al.Efficient public-key encryption based on ideal lattices[C]//LNCS 5912：Proceedings of the ASIACRYPT 2009.Berlin：Springer-Verlag，2009：617-635.

[9]Al-Riyami S S，Paterson K G.CBE from CL-PKE：a generic construction and efficient schemes[C]//Public Key Cryptography PKU 2005：8th International Workshop on Theory and Practice in Public Key Crytography，Switzerland，2005.

[10]Gorantlam C，Saxena A.An efficient certificateless signature scheme[C]//CIS 2005，2005：110-116.

[11]Boneh D，Hanbury M.Generalized identity based and broadcast encryption schemes[C]//Pieprzyk J.LNCS 5350：Advances in Cryptology ASIACRYPT 2008.Berlin：Springer-Verlag，2008：455-470.

[12]Zhao Z M，Wang X Y，Xu C G.An identity signature scheme based on iris information[J].Journal of Electronics&Information Technology，2010，32（10）：2388-2392.

[13]田苗苗，黃劉生，楊威.高效的基于格的環簽名方案[J].計算機學報，2012，35（4）：712-718.

ZHAO Hongjian1,DA Hanqiao2,HU Yuanming3

1.Department of Logistics,Wuhan University,Wuhan 430072,China
2.State Key Laboratory of Information Engineering in Surveying,Mapping and Remote Sensing,Wuhan University,Wuhan 430072,China
3.School of Mathematics and Statistics,Wuhan University,Wuhan 430072,China

In order to solve various privacy problems about existing signature schemes,such as issuing software license, issuing patent license and public bidding,in this paper,the random oracle model is the basis theory,and it designs a latticebased strong constraint verifier ring signature improved algorithm（L_SRS）.This algorithm provides detailed security analysis,and it adds a strong constraint security mechanism based on SIS.L_SRS algorithm can efficiently resist adaptive chosen message attack with strong unforgeability.The performance analysis shows L_SRS algorithm has characteristics of shorter signature length,high efficiency and stronger security.

strong constraint;small integer solution;Lattice-based Strong constraint verifier Ring Signature（L-SRS）; ring signature;strong unforgeability

為了解決現有的數字簽名機制在發放軟件著作、專利許可證以及項目工程招投標等應用中出現的各種隱私安全問題,以隨機預言模型下的相關簽名方案為理論基礎，提出了一種基于格結構（Lattice）的強約束驗證方環簽名改進算法，即L_SRS算法。該算法在標準模型下給出了詳實的安全性分析，依據標準的小整數解困難問題，L_SRS算法增加了一種強約束安全機制，能夠有效抵抗適應性選擇消息攻擊，對其具有強不可偽造性。通過安全性與性能分析，L_SRS算法具有應用高安全性、簽名計算高效率性等特點。

強約束；小整數解困難問題；基于格結構（Lattice）的強約束驗證方環簽名（L_SRS）；環簽名；強不可偽造性

A

TP309

10.3778/j.issn.1002-8331.1404-0344

ZHAO Hongjian,DA Hanqiao,HU Yuanming.Improved algorithm research for lattice-based verifier ring signature.Computer Engineering and Applications,2014,50（18）：103-108.

趙洪建（1955—），男，工程師，研究方向為信息安全，高校信息化建設；達漢橋（1956—），男，研究員，研究方向為測繪系統可信化技術；胡元明（1964—），男，副教授，研究方向為數學建模。

2014-04-22

2014-08-07

1002-8331（2014）18-0103-06