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

田苗苗，陳靜，仲紅

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

1 引言

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

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

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

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

具體地，本文的主要貢獻(xiàn)包括以下3 個(gè)方面。

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

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

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

2.1 符號(hào)定義

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

如果對(duì)任意的常數(shù)c，存在整數(shù)N，當(dāng)n>N時(shí)，f(n)

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

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

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

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

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

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

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

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

基于身份的增量簽名方案首先要滿足正確性，即對(duì)任意的身份id 和消息μ，如果算法Setup(n)、Extract(mpk,msk,id)以及Sign(mpk,id,skid,μ)均正確執(zhí)行，則：1) Verify(mpk,id,μ,sig)應(yīng)以極大概率輸出1；2) 對(duì)任意一個(gè)消息μ′以及一個(gè)有效的消息簽 名 對(duì)(μ,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如果對(duì)任意的多項(xiàng)式時(shí)間敵手A，其贏得以下游戲的概率是可忽略的，則稱該基于身份的增量簽名方案滿足適應(yīng)性選擇身份和選擇消息攻擊下的不可偽造性。游戲由敵手A 和挑戰(zhàn)者C 執(zhí)行，包括以下5 個(gè)階段：系統(tǒng)建立階段、私鑰提取詢問階段、標(biāo)準(zhǔn)簽名詢問階段、增量簽名詢問階段和偽造階段。

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

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

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

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

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

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

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

2.3 格基礎(chǔ)知識(shí)

2.4 離散高斯分布

2.5 格陷門函數(shù)

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

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

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

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

3 具體方案

3.1 方案描述

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

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

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

4 方案分析

4.1 正確性分析

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

證明考慮標(biāo)準(zhǔn)簽名和增量簽名2 種情況。

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

4.2 安全性分析

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

4.3 對(duì)比分析

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

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

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

表1 3 種增量簽名方案對(duì)比

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

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

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

4.4 性能評(píng)估

本節(jié)將通過具體實(shí)驗(yàn)來展示增量簽名算法相對(duì)于標(biāo)準(zhǔn)簽名算法的性能提升情況。

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

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

下面給出各算法的實(shí)驗(yàn)運(yùn)行結(jié)果，具體包括標(biāo)準(zhǔn)簽名算法、增量簽名算法以及簽名驗(yàn)證算法的計(jì)算開銷。

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

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

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

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

圖1 當(dāng)n=128 時(shí)，2 種簽名算法的計(jì)算時(shí)間對(duì)比

圖2 當(dāng)n=256 時(shí)，2 種簽名算法的計(jì)算時(shí)間對(duì)比

表4 不同參數(shù)下驗(yàn)證算法的計(jì)算時(shí)間對(duì)比

5 結(jié)束語

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