格上無陷門的基于證書盲簽名

陳江山

（1.閩南師范大學數據科學與統計重點實驗室,福建漳州 363000；2.閩南師范大學數學與統計學院,福建漳州 363000）

隨著信息社會的發展，個人隱私保護問題日益尖銳.在日常的電子商務活動中充斥著各種不愿泄露自身信息的情況.盲簽名技術則提供了其中一種.如：簽名的持有人希望獲得簽名人的一份簽名，但同時不愿意泄露這份簽名所對應的信息.在這種情況下，便可以采用盲簽名技術.盲簽名技術是電子商務的重要應用技術之一.盲簽名技術由Chaum[1]提出，簽名人對盲化過的消息進行簽名，簽名持有人取得簽名后對其進行去盲化，從而得到一份真實有效的簽名.盲簽名技術的應用較為廣泛，比如：電子銀行、電子投票、不經意傳輸等.

應用的廣泛使得盲簽名技術的研究從未間斷[2-6].特別是在不同的密碼體制和密碼應用場景中[7-12].然而，這些盲簽名方案均基于傳統的代數數論困難問題之上.在后量子時代中，傳統的基于代數數論困難問題的密碼技術受到了嚴重的安全威脅.因此，越來越多的密碼學者研究可以不受量子算法威脅的密碼技術[13-16].而且，我國也已然開始了對后量子密碼算法的征集，并納入我國商密標準算法.

在后量子密碼的研究中，基于格的密碼(也稱格基密碼)是其中一個重要研究方向.目前，大部分的后量子密碼算法，均是格基密碼[17-24].然而，多數的格基密碼的效率都因為陷門技術問題大大下降，從而難以實用化.

2012年,Lyubashevsky[25]提出了一個拒絕采樣的格上無陷門簽名方案.該方案在格基密碼的實用化道路上邁出了第一步.在Lyubashevsky工作的基礎上，構造一個格上無陷門的基于證書盲簽名方案.該盲簽名方案與Lyubashevsky的工作一樣拒絕采樣，從而避免了使用格上的陷門技術.同時，該方案具備了必要的無條件盲性和不可加一偽造性.方案所需的存儲空間較小，通信量也較小.由于方案使用無陷門技術，故而方案的計算復雜度也較小.

1 預備知識

1.1 格的基礎知識

定義1(格) 由矩陣B∈Rn×m產生的格L可定義如下：

其中，B是一個由m個線性無關的n維向量{b1,b2,…,bm}組成的矩陣.

定義2（l2-SISq,n,m,β問題）給定整數q和實數β，以及隨機矩陣，計算得到一個向量z∈Zm{0}，使得Az=0(mod q)和‖z‖≤β.

其中，當β≥時，以上困難問題有解.

1.2 拒絕采樣技術

這里，回顧Lyubashevsky的拒絕采樣技術.

1.3 基于證書盲簽名方案的一般性定義

基于證書的盲簽名方案一般由以下幾個算法組成：

Setup算法輸入安全參數，輸出系統的公共參數，證書機構的主公鑰和主密鑰.

UserKeyGen算法輸入系統的公共參數和用戶的身份，輸出用戶的公鑰和私鑰.

CertGen算法輸入系統的公共參數和證書機構的主密鑰，以及用戶的身份和公鑰，輸出用戶的證書.

BlindSign協議輸入系統的公共參數，待簽消息，簽名人的身份、私鑰和證書，輸出簽名.

Verify 算法輸入系統的公共參數，消息簽名對，證書機構的主公鑰，簽名人的身份和公鑰，輸出1 或0.其中:1表示簽名有效，0表示簽名無效.

1.4 盲簽名方案的安全性

盲簽名方案的安全性一般用無條件盲性和不可加一偽造性來刻畫.

無條件盲性：給定兩個盲化的消息簽名對，隨機選擇其中一個進行去盲化處理.對于這個去盲化后的消息簽名對，任意的多項式時間算法（簽名人或區分器）能夠區分正確的優勢是可忽略的，則稱這個盲簽名方案滿足無條件盲性.

不可加一偽造性：盲簽名方案的不可加一偽造性可以通過一個游戲模型證明.該游戲由挑戰者和攻擊者交互進行.挑戰者初始化系統后，將系統公共參數和公鑰發送給攻擊者，并提供詢問諭言機.如Hash詢問諭言機、私鑰提取詢問諭言機、盲簽名詢問諭言機等等.攻擊者可以適應性選擇詢問，除了被攻擊目標的私鑰.攻擊者獲得l個被攻擊目標的對應盲簽名之后，若能輸出l+1個被攻擊目標的可驗證有效的盲簽名，則攻擊者贏得游戲.若任意的攻擊者在多項式時間內贏得游戲的概率是可忽略的，則稱該盲簽名方案滿足不可加一偽造性.

2 格上無陷門的基于證書盲簽名方案

2.1 構造的方案

格上無陷門的基于證書盲簽名方案的構造具體如下：

2.2 正確性

簽名的正確性可以由以下的等式容易驗證.

2.3 安全性分析

1)無條件盲性.由簽名方案的ΒlindSign算法的盲化步驟和去盲步驟可知，用于盲化和去盲的盲化因子x和h'均是均勻隨機選擇的.而且，簽名人所收到的h''是經過盲化處理的，簽名人無法從h''中獲得任何信息.因此，假定從和中隨機選取一個進行去盲化處理.對于簽名人（或區分器）而言，由于未獲得任何有效信息，因而簽名人只能通過拋硬幣決定輸出b'.那么，簽名人輸出一個b'滿足b'=b的優勢是可忽略的.所以，該基于證書盲簽名方案滿足無條件盲性.

2)不可加一偽造性.在游戲過程中，若攻擊者贏得游戲的優勢是不可忽略的，則挑戰者可以利用攻擊者的能力輸出一個Lyubashevsky 方案的有效偽造.挑戰者向攻擊者提供詢問諭言機，同時向Lyubashevsky 方案請求詢問.挑戰者收到攻擊者的詢問后，若該詢問所相關的信息與Lyubashevsky 方案無關，則挑戰者自己建立詢問諭言機并進行回答；否則，挑戰者將攻擊者的詢問加以處理并轉以詢問Lyubashevsky方案，得到回復后，再處理成攻擊者所需的回復并以此回復攻擊者.當攻擊者進行了l個被攻擊目標的對應盲簽名詢問之后，輸出l+1個被攻擊目標的可驗證有效的消息簽名對.那么，其中至少由一個消息簽名對不屬于詢問諭言機回復的簽名結果.由此，挑戰者可以對該消息簽名對進行必要的處理，然后將它作為Lyubashevsky方案的偽造輸出.

由Lyubashevsky方案的不可偽造性可知，攻擊者在多項式時間內贏得游戲的概率是可忽略的.所以，該基于證書盲簽名方案滿足不可加一偽造性.

2.4 效率分析

該基于證書盲簽名方案的構造采用了Lyubashevsky[25]的拒絕采樣技術，從而大大降低了整體的計算復雜度.方案在存儲開銷方面，參照文獻[25]的參數說明及實例，本方案的參數設置如下，見表1.

表1 方案的參數設置Tab.1 Parameters for our scheme

3 結論

Lyubashevsky 構建了一個無陷門的簽名方案，采用拒絕采樣技術，從而使得格基簽名在趨于實用化道路上邁出了一步.在Lyubashevsky 工作的基礎上構建了一個基于證書的盲簽名方案.該方案同樣采用拒絕采樣技術，未使用陷門技術.從而，使得方案的計算復雜度大大下降.而且，方案滿足無條件盲性和不可加一偽造性.方案基本滿足一些電子商務的需求.