格上基于身份的增量簽名方案

田苗苗，陳靜，仲紅

（安徽大學計算機科學與技術(shù)學院，安徽 合肥 230601）

1 引言

隨著信息化的深入發(fā)展，數(shù)字信息在當今社會發(fā)揮著越來越重要的作用，保障數(shù)字信息的完整性和不可偽造性是現(xiàn)代社會健康發(fā)展的前提。數(shù)字簽名[1]是一種基礎(chǔ)的密碼學原語，可以用來保證數(shù)字消息的完整性、發(fā)送者身份的不可抵賴性等，廣泛應(yīng)用于網(wǎng)上銀行、電子政務(wù)、電子合同等諸多領(lǐng)域。傳統(tǒng)的數(shù)字簽名沒有考慮消息之間的聯(lián)系，每次簽署消息所需的開銷與消息的長度成正比，難以滿足一些特定應(yīng)用場景的需求。例如，在面向自然災(zāi)害預防或天氣預報的環(huán)境傳感網(wǎng)絡(luò)中，分布于不同地理位置的一系列傳感器需要監(jiān)測環(huán)境數(shù)據(jù)并將其上傳到上層收集設(shè)備保存[2]，為了保證這些監(jiān)測數(shù)據(jù)的真實性，需要對其進行簽名。由于要精準地進行自然災(zāi)害或天氣預測，這些傳感器需要持續(xù)監(jiān)測并實時更新監(jiān)測數(shù)據(jù)，而通常連續(xù)的監(jiān)測數(shù)據(jù)，如溫度和濕度數(shù)據(jù)等僅有微小的差異。隨著監(jiān)測任務(wù)的持續(xù)進行，數(shù)據(jù)不斷增加，如果采用傳統(tǒng)的數(shù)字簽名方法，每次更新數(shù)據(jù)都必須重新計算簽名，會導致傳感器的開銷很大。為了降低傳感器的開銷，延長傳感器的使用壽命，可以采用增量簽名[3]方案對這些監(jiān)測數(shù)據(jù)進行簽名。

增量簽名的概念由Bellare 等[3]于1994 年提出，其基本出發(fā)點是，數(shù)字簽名主要包括對消息進行哈希運算和對哈希結(jié)果進行簽名兩部分，如果哈希函數(shù)具有增量性，那么當已知一個消息的哈希值時，用戶可以快速得到另一個相似消息的哈希值，對該哈希值進行簽名，即可得到新消息的簽名。由于增量簽名方案可以加快相似消息的簽名過程，使簽名生成時間與消息間的變化量成正比，因此對數(shù)據(jù)連續(xù)更新的場景或者存在大量相似數(shù)據(jù)的場景，采用增量簽名方案而非傳統(tǒng)簽名方案，可以大大降低系統(tǒng)的整體開銷。區(qū)塊鏈是當前的一個研究熱點，將一個交易加入?yún)^(qū)塊鏈中的前提是確保該交易的完整性和不可偽造性，為此需對該交易簽名并向全網(wǎng)廣播，由其他用戶檢查簽名的有效性，僅當簽名有效時才將該交易加入?yún)^(qū)塊鏈[4]。由于區(qū)塊鏈中通常存在較多的相似數(shù)據(jù)，因此采用增量簽名方案對交易進行簽名有望大幅提高區(qū)塊鏈系統(tǒng)的效率。最近，著名區(qū)塊鏈公司Kadena 已經(jīng)在其企業(yè)級區(qū)塊鏈上采用了增量簽名算法。

增量簽名這一概念被提出以來，許多增量簽名方案[3,5-6]相繼被提出，然而現(xiàn)有的增量簽名方案都依賴于公鑰基礎(chǔ)設(shè)施（PKI,public key infrastructure），用戶的公鑰是一串隨機字符，需要通過數(shù)字證書綁定用戶的身份與其公鑰的匹配關(guān)系，這會給系統(tǒng)帶來額外的存儲開銷和計算開銷。為了解決這個問題，本文借鑒基于身份的密碼學思想[7]，提出了基于身份的增量簽名概念，用戶使用能唯一標識其身份的字符串（如電話號碼、郵箱地址等）作為其公鑰，相應(yīng)的私鑰由可信的私鑰生成器（PKG,private key generator）根據(jù)系統(tǒng)主密鑰和用戶身份生成，從而消除了傳統(tǒng)增量簽名方案存在的證書管理問題。

此外，本文利用格上相關(guān)困難問題——標準的小整數(shù)解（SIS,small integer solution）問題[8-9]，設(shè)計了一種具體的基于身份的增量簽名方案，該方案在標準模型下對適應(yīng)性選擇身份和選擇消息攻擊滿足不可偽造性?；诟竦拿艽a學也是當前的一個研究熱點，與基于離散對數(shù)和大數(shù)分解等傳統(tǒng)困難問題的密碼方案相比，基于格的密碼方案有望抵抗量子計算機的攻擊[10]，并且僅需要向量點乘、線性求和以及模運算等簡單操作，計算效率較高。近年來，基于格的數(shù)字簽名方案受到人們的廣泛關(guān)注，格上基于身份的各類簽名方案也被相繼提出，如格上基于身份的（標準）簽名方案[11-16]和環(huán)簽名方案[17-18]等。然而，這些方案要么僅能在隨機預言模型下證明是適應(yīng)性安全的[13-14,16-17]，要么只能達到標準模型下的選擇安全性（即僅能實現(xiàn)選擇身份攻擊下的不可偽造性）[11-12,18]。由于隨機預言模型下證明安全的方案在實際應(yīng)用中不一定安全[19]，因此構(gòu)造標準模型下適應(yīng)性安全的格上基于身份的簽名方案具有重要的理論和現(xiàn)實意義。如果不考慮增量性，本文方案也可以看作一種在標準模型下對適應(yīng)性選擇身份和選擇消息攻擊滿足不可偽造性的格上基于身份的簽名方案。

具體地，本文的主要貢獻包括以下3 個方面。

1) 本文提出了基于身份的增量簽名概念及模型，消除了以往增量簽名中存在的證書管理問題，提高了增量簽名方案的實際效率。

3) 本文證明了在標準的小整數(shù)解困難假設(shè)下，所提格上基于身份的增量簽名方案在標準模型下滿足適應(yīng)性選擇身份和選擇消息攻擊下的不可偽造性。

2 預備知識

2.1 符號定義

本文的安全參數(shù)為n。令? 和? 分別表示實數(shù)集和整數(shù)集。給定正整數(shù)d，令[d]表示集合{0,…,d?1}，令BitDecompb(d)表示d的維比特分解，其中b為正整數(shù)。令矩陣A的格拉姆?施密特正交化為，并且令其最大奇異值為s1(A)=maxu‖Au‖，其中，u是任意的單位向量，‖ ?‖是 ?2范數(shù)。

如果對任意的常數(shù)c，存在整數(shù)N，當n>N時，f(n)

2.2 基于身份的增量簽名方案

本節(jié)介紹基于身份的增量簽名方案的定義及安全模型。

定義1基于身份的增量簽名方案由以下5 個概率多項式時間算法組成，分別為系統(tǒng)建立算法Setup、私鑰提取算法Extract、標準簽名算法Sign、增量簽名算法IncSig 以及簽名驗證算法Verify。各算法的具體描述如下。

Setup。輸入安全參數(shù)n，輸出系統(tǒng)主公鑰mpk和主私鑰msk。

Extract。輸入系統(tǒng)主公鑰mpk 和主私鑰msk，以及身份id，輸出該身份所對應(yīng)的私鑰skid。

Sign。輸入系統(tǒng)主公鑰mpk、身份id 及其對應(yīng)的私鑰skid，以及消息μ，輸出消息μ的簽名sig。

IncSig。輸入系統(tǒng)主公鑰mpk、身份id 及其對應(yīng)的私鑰skid、一個有效的消息簽名對(μ,sig)，以及新消息μ′，輸出消息μ′的簽名sig′。

Verify。輸入系統(tǒng)主公鑰mpk、身份id 和一個消息簽名對(μ,sig)，如果sig 是身份為id 的用戶對消息μ的有效簽名，則輸出1；否則輸出0。

基于身份的增量簽名方案首先要滿足正確性，即對任意的身份id 和消息μ，如果算法Setup(n)、Extract(mpk,msk,id)以及Sign(mpk,id,skid,μ)均正確執(zhí)行，則：1) Verify(mpk,id,μ,sig)應(yīng)以極大概率輸出1；2) 對任意一個消息μ′以及一個有效的消息簽 名 對(μ,sig)，滿 足 Verify(mpk,id,μ,sig)=1，Verify(mpk,id,μ′,IncSig (mpk,id,skid,μ,sig,μ′))應(yīng)以極大概率輸出1。

根據(jù)傳統(tǒng)增量簽名的適應(yīng)性選擇消息安全模型[3]、基于身份簽名的適應(yīng)性選擇身份和選擇消息安全模型[14,23]，可定義基于身份的增量簽名方案在適應(yīng)性選擇身份和選擇消息攻擊下的安全性。

定義2如果對任意的多項式時間敵手A，其贏得以下游戲的概率是可忽略的，則稱該基于身份的增量簽名方案滿足適應(yīng)性選擇身份和選擇消息攻擊下的不可偽造性。游戲由敵手A 和挑戰(zhàn)者C 執(zhí)行，包括以下5 個階段：系統(tǒng)建立階段、私鑰提取詢問階段、標準簽名詢問階段、增量簽名詢問階段和偽造階段。

系統(tǒng)建立階段。挑戰(zhàn)者C 運行算法Setup(n)生成系統(tǒng)主公鑰mpk 和主私鑰msk，然后將主公鑰mpk 發(fā)送給敵手A，并初始化參數(shù)α=0。

私鑰提取詢問階段。敵手A 可以適應(yīng)性地向挑戰(zhàn)者C 詢問身份id 所對應(yīng)的私鑰，挑戰(zhàn)者C 運行算法Extract(mpk,msk,id)生成私鑰skid，并將其發(fā)送給敵手A。

標準簽名詢問階段。敵手A 可以適應(yīng)性地向挑戰(zhàn)者C 進行標準簽名詢問。當敵手A 詢問身份為id的用戶對消息μ的標準簽名時，挑戰(zhàn)者C 運行算法Sign(mpk,id,skid,μ)生成相應(yīng)的簽名sig，并將其發(fā)送給敵手A 。然后挑戰(zhàn)者C保存(μα,sigα)=(μ,sig)，并令α=α+1。

增量簽名詢問階段。敵手A 也可以適應(yīng)性地向挑戰(zhàn)者C 進行增量簽名詢問。不失一般性地，假設(shè)2 個相似消息之間只相差1 bit。當敵手A 詢問身份為id 的用戶對消息μ′的增量簽名時，它需要發(fā)送id 以及一個三元組(i,j,v)，其中，i∈[α]，表明μ′是μi的第j位被v代替所得的新消息。挑戰(zhàn)者C 首先找到有效的消息簽名對(μi,sigi)，然后運行算法IncSig (mpk,id,skid,μi,sigi,μ′)生成相應(yīng)的簽名sig′，并將其發(fā)送給敵手A，最后挑戰(zhàn)者C 保存(μα,sigα)=(μ′,sig′)，并令α=α+1。

偽造階段。敵手A 偽造一個關(guān)于身份id*的偽造消息簽名對(μ*,sig*)，若滿足以下條件，則敵手A 贏得游戲。

1) 敵手A 沒有對身份id*進行過私鑰提取詢問，也沒有對μ*進行過標準簽名詢問或關(guān)于μ*的增量簽名詢問，即μ*?{μ0,μ1, …,μα?1}。

2) 算法Verify(mpk,id*,μ*,sig*)=1。

2.3 格基礎(chǔ)知識

2.4 離散高斯分布

2.5 格陷門函數(shù)

基于格的陷門函數(shù)是格密碼學的重要工具之一，傳統(tǒng)的格陷門是格的一個短基。本文提出的格上基于身份的增量簽名方案采用文獻[21]的G?陷門概念及其相關(guān)算法，分別為陷門生成算法TrapGen、原像采樣算法SampleD 和陷門委派算法DelTrap。這種陷門函數(shù)的參數(shù)較小，計算和存儲開銷也較少。

2.6 可編程哈希函數(shù)

可編程哈希函數(shù)（PHF,programmablehash function）的概念最初由Hofheinz 等[26]提出，可以用來構(gòu)造標準模型下安全的密碼方案。簡單來說，可編程哈希函數(shù)有2 種工作模式，即正常模式和陷門模式。正常模式包含H.Gen和H.Eval這2 種算法，而陷門模式包含H.TrapGen 和H.TrapEval這2 種算法。在擁有陷門信息的情況下，這2 種模式是不可區(qū)分的，因此可以在安全性證明中使用陷門模式模擬正常模式。本文采用Zhang 等[20]提出的基于格的高效可編程哈希函數(shù)來嵌入身份信息。下面給出無覆蓋集合族的概念。

上述引理表明，該可編程哈希函數(shù)存在較好的模擬方法，可以在安全性證明中模擬該函數(shù)。

3 具體方案

3.1 方案描述

本文方案各算法的具體實現(xiàn)過程如下。

1) 系統(tǒng)建立算法

3.2 參數(shù)設(shè)置

4 方案分析

4.1 正確性分析

定理1本文提出的格上基于身份的增量簽名方案滿足正確性。

證明考慮標準簽名和增量簽名2 種情況。

綜上，本文提出的增量簽名方案是正確的。證畢。

4.2 安全性分析

定理2如果小整數(shù)解問題是困難的，則本文提出的格上基于身份的增量簽名方案對適應(yīng)性選擇身份和選擇消息攻擊是不可偽造的。

4.3 對比分析

本節(jié)將本文方案與基于PKI 的增量簽名方案和基于身份的簽名方案分別進行比較。

1) 與基于PKI 的增量簽名方案對比

表1 給出了本文方案與幾種增量簽名方案的特征比較。文獻[3]和文獻[6]的方案都是基于PKI 的，存在證書管理問題。文獻[3]的方案基于離散對數(shù)（DL,discrete logarithm）問題的困難性，在隨機預言模型下對適應(yīng)性選擇消息攻擊是安全的。文獻[6]的方案基于格上k次小整數(shù)解（k-SIS,k-small integer solutions）問題的困難性[27]，在標準模型下對適應(yīng)性選擇消息攻擊是安全的。然而由于將k-SIS 問題規(guī)約到標準SIS 問題會增加乘法因子k！，其中k與簽名次數(shù)有關(guān)，因此文獻[6]中方案的簽名次數(shù)較有限。與這2 種方案相比，本文方案不僅消除了證書管理問題，而且在標準模型下基于標準的SIS 問題證明了方案滿足適應(yīng)性選擇身份和選擇消息攻擊下的不可偽造性。

表1 3 種增量簽名方案對比

2) 與格上基于身份的簽名方案對比

表2 給出了本文方案與幾種格上基于身份的簽名方案的比較結(jié)果，其中n表示安全參數(shù)，。從表2 可以看出，雖然本文方案相比文獻[11-15]中的方案而言，在公開參數(shù)大小、簽名密鑰大小和簽名長度等方面優(yōu)勢不明顯，但本文方案的安全性較高。具體地，文獻[13-14]中的方案僅在隨機預言模型下達到適應(yīng)性選擇身份和選擇消息攻擊下的不可偽造性，文獻[15]中的方案在隨機預言機模型下僅對選擇身份攻擊是安全的，而文獻[11-12]中的方案雖然是在標準模型下可證明安全的，但這些方案只對選擇身份攻擊是安全的。

此外，本文方案還具有增量性。假設(shè)2 個消息僅相差1 bit，則當已知一個消息的哈希值時，采用本文方案計算新消息的哈希值僅需一次矩陣加法運算即可，而完整的哈希計算則需要計算 ?+1次矩陣加法。由于? 通常較大，因此本文方案可以加快標準簽名算法的簽名過程。

4.4 性能評估

本節(jié)將通過具體實驗來展示增量簽名算法相對于標準簽名算法的性能提升情況。

根據(jù)3.1 節(jié)的方案描述可知，標準簽名算法與增量簽名算法都需要運行SampleD 和計算消息的哈希值（由于矩陣Aid具有一定的穩(wěn)定性，因此這里忽略其計算開銷），然而標準簽名算法的消息編碼方式為，其計算時間與整個消息μ的長度成正比，增量簽名算法的消息編碼方式為，其計算時間僅與消息的改變量（μ′和μ之間的比特差異數(shù)）成正比。因此，當需要對d個連續(xù)變化的數(shù)據(jù)進行簽名時，用增量簽名方案僅需執(zhí)行一次標準簽名算法和d?1 次增量簽名算法，而采用標準簽名方案需執(zhí)行d次標準簽名算法。直觀上看，增量簽名算法的運行時間要比標準簽名算法的少，因此增量簽名方案非常適用于處理數(shù)據(jù)僅有細微差別的大數(shù)據(jù)系統(tǒng)。

表2 本文方案與幾種格上基于身份的簽名方案對比

下面給出各算法的實驗運行結(jié)果，具體包括標準簽名算法、增量簽名算法以及簽名驗證算法的計算開銷。

本文方案的實驗代碼采用 C++11 編寫、g++5.4.0 編譯。實驗由配置了Ubuntu 16.04 LTS 系統(tǒng)、Intel Core i5-7500 CPU 和16 GB 內(nèi)存的PC 運行。本文實驗選取2 組數(shù)據(jù)，分別是n=128 和n=256。消息長度分別為256 bit、384 bit 和512 bit，增量簽名的消息改變量為原消息長度的一半。在本文實驗中，令，其中ε=2?80，其他相關(guān)參數(shù)如表3 所示。所有實驗結(jié)果均為運行10 次實驗的平均值。

表3 實驗參數(shù)的具體設(shè)置

圖1 和圖2 分別展示了當n=128 和n=256 時，標準簽名算法和增量簽名算法的計算時間比較。標準簽名算法的計算時間包括計算消息哈希值以及執(zhí)行SampleD 的時間，而增量簽名算法的計算時間包括計算消息增量哈希值以及執(zhí)行SampleD 的時間，其中Hash 表示計算消息哈希值的時間，IncHash表示計算消息增量哈希值的時間，SampleD 表示執(zhí)行SampleD 的時間。從圖1 和圖2 可以看出，隨著消息長度的不斷增加，Hash 和IncHash 都會增長，但IncHash 的值更小。具體地，當n=128 時，增量簽名算法的整體計算效率相比標準簽名算法提高了41.9%～50.2%；當n=256 時，增量簽名算法的整體計算效率相比標準簽名算法提高了39.9%～48.3%。

表4 為不同參數(shù)下簽名驗證算法Verify 的計算時間對比。由于該算法的執(zhí)行時間對標準簽名算法和增量簽名算法都是相同的，因此表4 列出了在不同的n和消息長度的情況下，Verify 算法的執(zhí)行時間變化情況。從表4 中可以看出，隨著n和消息長度的增加，Verify 算法所需的時間也會增加，但其絕對值仍較小。

圖1 當n=128 時，2 種簽名算法的計算時間對比

圖2 當n=256 時，2 種簽名算法的計算時間對比

表4 不同參數(shù)下驗證算法的計算時間對比

5 結(jié)束語

本文提出了基于身份的增量簽名概念，并基于格上困難問題設(shè)計了一種具體方案。在標準的小整數(shù)解困難假設(shè)下，本文方案在標準模型下對適應(yīng)性選擇身份和選擇消息攻擊是不可偽造的。與基于PKI 的增量簽名方案相比，本文方案消除了公鑰證書的管理問題，提高了方案的實際使用效率。此外，與格上基于身份的簽名方案相比，本文方案不僅具有增量性和更好的計算效率，而且安全性也較高。