基于格的可截取簽名方案*

趙 勇， 楊少軍， 張福泰，3， 黃欣沂

1. 福建師范大學(xué) 計(jì)算機(jī)與網(wǎng)絡(luò)空間安全學(xué)院， 福州 350117

2. 福建師范大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院， 福州 350117

3. 福建師范大學(xué) 福建省網(wǎng)絡(luò)安全與密碼技術(shù)重點(diǎn)實(shí)驗(yàn)室， 福州 350007

4. 密碼科學(xué)技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室， 北京 100878

5. 香港科技大學(xué)(廣州) 信息樞紐 人工智能學(xué)域， 廣州 511455

1 引言

數(shù)據(jù)安全對(duì)于政治安全、國(guó)防安全、經(jīng)濟(jì)安全和國(guó)計(jì)民生至關(guān)重要，對(duì)于解決數(shù)據(jù)泄露、數(shù)據(jù)篡改等安全問題具有重要的意義. 數(shù)字簽名[1]可檢測(cè)數(shù)據(jù)的真實(shí)性、完整性和不可抵賴性， 是保障數(shù)據(jù)安全的重要公鑰密碼技術(shù). 數(shù)字簽名的傳統(tǒng)安全性要求是在自適應(yīng)選擇消息攻擊下滿足存在不可偽造性(existential unforgeability under adaptive chosen-message attacks， EUF-CMA)[2]. EUF-CMA 要求: 在自適應(yīng)選擇消息攻擊下， 敵手偽造新消息有效簽名的概率是可忽略的. 這雖然可以檢測(cè)數(shù)據(jù)篡改， 但也阻礙了對(duì)已簽名數(shù)據(jù)進(jìn)行刪除、合并、替換等合理操作， 不支持電子病歷、電子投票等應(yīng)用場(chǎng)景中由隱私保護(hù)帶來的數(shù)據(jù)修改需求.

例如醫(yī)療信息化建設(shè)的過程中產(chǎn)生了大量包含姓名、藥敏、治療記錄、身份證號(hào)、家庭地址等敏感數(shù)據(jù)的電子病歷. 當(dāng)電子病歷用于醫(yī)學(xué)研究或統(tǒng)計(jì)分析時(shí)， 需要?jiǎng)h除可標(biāo)識(shí)用戶身份的敏感數(shù)據(jù)， 以保護(hù)用戶的隱私. 同時(shí)， 為了保證研究結(jié)果和分析結(jié)果的有效性， 又需要向數(shù)據(jù)使用方證實(shí)刪除敏感數(shù)據(jù)后電子病歷的真實(shí)性. 具有EUF-CMA 性質(zhì)的數(shù)字簽名只能證實(shí)整份電子病歷的有效性， 無(wú)法證實(shí)刪除用戶敏感數(shù)據(jù)后電子病歷的真實(shí)有效性. 針對(duì)這個(gè)問題， 一種簡(jiǎn)單的解決辦法是， 先將電子病歷分為若干個(gè)數(shù)據(jù)塊， 然后對(duì)每個(gè)數(shù)據(jù)塊分別進(jìn)行簽名， 最后將所有的數(shù)據(jù)塊-簽名發(fā)給簽名持有人. 簽名持有人可以為刪除敏感數(shù)據(jù)后的病歷生成有效的簽名， 但計(jì)算和通信的開銷會(huì)隨著分塊的細(xì)化而增大， 不能很好地滿足實(shí)際需求.

為解決上述問題， 2001 年， Steinfeld 等人[3]提出可截取簽名(extraction signatures， ES)， 在不與簽名人交互的情況下， 簽名持有人(截取者) 可刪除已簽名數(shù)據(jù)中的敏感數(shù)據(jù)塊， 并為截取后的數(shù)據(jù)生成有效簽名. 近年來， 可截取簽名在數(shù)據(jù)類型、形式化安全定義、截取規(guī)則等多個(gè)方面取得了積極的研究進(jìn)展.

目前， 可截取簽名方案的安全性大多基于大數(shù)分解問題、離散對(duì)數(shù)問題等傳統(tǒng)數(shù)論困難問題. 然而， 隨著近幾年量子計(jì)算的快速發(fā)展， 一些傳統(tǒng)數(shù)論困難問題在量子計(jì)算模型下可被有效求解. 例如在量子計(jì)算模型下， Shor 算法能夠在多項(xiàng)式時(shí)間內(nèi)解決經(jīng)典的大整數(shù)分解問題和離散對(duì)數(shù)問題[4]. 換言之， 一旦出現(xiàn)足夠規(guī)模的量子計(jì)算機(jī)， 基于傳統(tǒng)數(shù)論困難問題的可截取簽名將不再安全. 然而， 目前未見抗量子的可截取簽名方案在主流密碼期刊和會(huì)議上公開發(fā)表. 因此， 研究抗量子的可截取簽名方案具有重要的理論意義和科學(xué)價(jià)值.

格密碼具有抗量子、實(shí)現(xiàn)簡(jiǎn)單高效和平均情況/最差情況等價(jià)的安全性[5]等特點(diǎn)， 是最通用的后量子密碼之一. 近年來， 格密碼技術(shù)得到了快速的發(fā)展. 2008 年， Gentry 等人[6]提出的原像抽樣函數(shù)(preimage sampleable functions， PSF) 是重要的格上密碼技術(shù)， 已被廣泛地應(yīng)用于數(shù)字簽名、IBE 等格上密碼方案. 因此， 本文利用原像抽樣函數(shù)， 提出基于格上小整數(shù)解問題(small integer solution， SIS) 的可截取簽名方案， 在自適應(yīng)選擇消息攻擊下滿足存在不可偽造性和隱私性.

1.1 相關(guān)工作

本節(jié)介紹可截取簽名和格簽名的相關(guān)工作.

1.1.1 可截取簽名

現(xiàn)有的可截取簽名方案可以處理集合型數(shù)據(jù)[3，7]、樹型數(shù)據(jù)[8，9]、圖表型數(shù)據(jù)[10，11]等多種數(shù)據(jù)結(jié)構(gòu).可截取簽名方案要滿足兩個(gè)基本安全要求: 不可偽造性和隱私性. 不可偽造性確保在自適應(yīng)選擇消息攻擊下， 除依據(jù)截取規(guī)則生成已詢問數(shù)據(jù)的子數(shù)據(jù)簽名外， 敵手為新數(shù)據(jù)偽造有效簽名的概率是可忽略的; 隱私性確保在自適應(yīng)選擇消息攻擊下， 敵手不能在多項(xiàng)式時(shí)間內(nèi)獲取被刪除的信息. 為了滿足不同應(yīng)用場(chǎng)景的需求， 可截取簽名還要滿足透明性[8]、不可關(guān)聯(lián)性[12]、可審計(jì)性[13，14]和可合并性[15，16]等安全要求.透明性確保敵手很難判斷收到的簽名是原始簽名還是截取后的簽名.不可關(guān)聯(lián)性確保敵手很難判斷兩個(gè)截取后的數(shù)據(jù)簽名對(duì)是否來源于同一個(gè)原始數(shù)據(jù)簽名對(duì). 可審計(jì)性確保審計(jì)者可以有效地判斷出數(shù)據(jù)-簽名的生成人. 可合并性確保截取者可合并原始數(shù)據(jù)的截取數(shù)據(jù)組， 并為合并后的數(shù)據(jù)生成有效簽名.

為了實(shí)現(xiàn)對(duì)可截取內(nèi)容的控制， Steinfeld 等人[3]引入內(nèi)容截取訪問結(jié)構(gòu)(content extraction access structure， CEAS)， 簽名人為簽名持有人指定可被截取的數(shù)據(jù)塊集合， 以實(shí)現(xiàn)對(duì)簽名持有人的截取控制.2003 年， Bull 等人[17]提出群組截取規(guī)則， 并為此提供了有效的編碼方法. 2004 年， Bull 等人[18]提出實(shí)行分級(jí)群組策略的可截取簽名方案， 但僅能應(yīng)用于分層結(jié)構(gòu)化數(shù)據(jù). 2005 年， Miyazaki 等人[19]提出帶有公開條件控制的可截取簽名方案， 然而簽名長(zhǎng)度過大. 為解決這個(gè)問題， 2006 年， Miyazaki、Hanaoka 等人[20]提出基于雙線性對(duì)的可截取簽名方案. 隨后， Ma 等人[21]引入動(dòng)態(tài)粗粒度截取規(guī)則， 并提出一種安全高效的可截取簽名方案. 2017 年， Ma 等人[22]提出具有細(xì)粒度單調(diào)修訂控制的可截取簽名方案. 2019年， Liu 等人[23]提出門限型的可截取簽名方案， 限制了可刪除數(shù)據(jù)塊數(shù)量的閾值. 這些研究工作均豐富了可截取簽名截取規(guī)則的表達(dá)力， 增強(qiáng)了可截取簽名的實(shí)用性.

1.1.2 格簽名

1997 年， Goldreich 等人[24]首次提出基于格上困難問題的數(shù)字簽名方案， 即GGH 簽名方案. 雖然該方案的簽名和驗(yàn)證算法都比較高效， 但沒有嚴(yán)格的安全性證明. 2001 年， Hoffstein 等人[25]提出基于NTRU 格的簽名方案， 即NSS 簽名方案. 2003 年， Hoffstein 等人[26]設(shè)計(jì)出一種更加高效的格上簽名方案， 即NTRUSign 簽名方案. 但Gentry 等人[27，28]證明了NSS 簽名方案及其變形均可被攻破， 并指出GGH 簽名方案和NTRUSign 簽名方案均存在安全漏洞. 2006 年， Nguyen 等人[29]提供了一種可以攻破GGH 簽名方案的方法. 隨后， 分別在隨機(jī)諭言器模型和標(biāo)準(zhǔn)模型下可證明安全的格上簽名方案受到了高度關(guān)注.

隨機(jī)諭言器模型下的格簽名. 2008 年， Gentry 等人[6]改進(jìn)格上抽樣技術(shù)， 設(shè)計(jì)了一種單向陷門函數(shù)，并提出可證明安全的格上簽名方案. 2012 年， Lyubashevsky[30]基于Fiat-Shamir 轉(zhuǎn)換， 提出無(wú)陷門的格上簽名方案. 2013 年， Ducas 等人[31]利用雙峰高斯， 設(shè)計(jì)出安全高效的BLISS 簽名方案. 2014 年， Bai等人[32]優(yōu)化壓縮技術(shù)， 縮短了簽名的長(zhǎng)度.

標(biāo)準(zhǔn)模型下的格簽名. 2008 年， Lyubashevsky 等人[33]提出可證明安全的格上簽名方案， 但僅是一次簽名方案. 2010 年， Cash 等人[34]借助單向陷門函數(shù)， 以及格基委派技術(shù)， 提出了可證明安全的格上簽名方案. 2012 年， Micciancio 等人[35]改進(jìn)格基陷門生成算法， 并提出一種高效的格上簽名方案. 2014 年，Ducas 等人[36]構(gòu)造出理想格中的數(shù)字簽名方案， 縮短了公鑰長(zhǎng)度. 2016 年， Zhang 等人[37]實(shí)現(xiàn)了格上可編程哈希函數(shù)， 并提出一種可證明安全的短簽名方案.

近年來， 在美國(guó)國(guó)家標(biāo)準(zhǔn)與技術(shù)研究院征集的后量子密碼方案中， 格上密碼方案最多. 在第三輪入圍的數(shù)字簽名中， 格上簽名方案獨(dú)占兩席， 即Dilithium[38]和Falcon[39]. Falcon 的密鑰較短， Dilithium具有較高的計(jì)算效率. 這兩類格上簽名方案代表了格簽名的發(fā)展方向.

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

本節(jié)首先給出相關(guān)符號(hào)說明， 其次介紹關(guān)于格密碼的基本概念及其相關(guān)基礎(chǔ)知識(shí).

2.1 符號(hào)

數(shù)據(jù)M由N個(gè)數(shù)據(jù)塊組成， 表示為M={M[1]，M[2]，···，M[N]}， 其中M[i] 表示M中第i個(gè)數(shù)據(jù)塊; 另外， 用CI(M) 表示M中非空數(shù)據(jù)塊對(duì)應(yīng)的索引集合.

表1 數(shù)據(jù)M 與索引集CI(M)Table 1 Data M and index set CI(M)

2.2 格

格是定義在Rm上的離散加法子群. 下面給出格的定義.

定義1 給定Rm中一組線性無(wú)關(guān)的向量B={b1，b2，···，bn}， 則由B生成的格Λ 定義如下:

2.3 可截取簽名

可截取簽名允許簽名持有人(截取者)在不與簽名人交互的情況下對(duì)已簽名的數(shù)據(jù)進(jìn)行刪除截取操作，并為截取后的數(shù)據(jù)獨(dú)立計(jì)算有效的簽名.

定義4[3]可截取簽名方案(extraction signatures， ES) 由下面四個(gè)多項(xiàng)式時(shí)間算法構(gòu)成:

(1) ESGK(k): 輸入安全參數(shù)k， 輸出公私鑰對(duì)(pk， sk). 記作

(3) ESExt(M，pk，X，σ): 輸入數(shù)據(jù)M， 公鑰pk， 待截取子集X ?[N] 和可截取簽名σ， 輸出被截取的數(shù)據(jù)簽名對(duì)(M′，σE)， 其中CI(M′)=X. 記作

(4) ESVer(pk，M，σ): 輸入公鑰pk， 數(shù)據(jù)M和簽名σ. 輸出驗(yàn)證結(jié)果“1” 或“0”， 其中“1” 表示簽名σ有效， “0” 表示簽名σ無(wú)效. 記作

可截取簽名方案的正確性. 對(duì)任意數(shù)據(jù)M和(pk，sk)←ESGK(k)， 有

· ESVer(pk，M，ESSig(M，sk))=1.

· ESVer(pk，ESExt(M，pk，X，ESSig(M，sk)))=1.

可截取簽名方案的安全性. 可截取簽名方案ES 的兩個(gè)基本安全要求是不可偽造性和隱私性.

可截取簽名方案的不可偽造性要求， 在自適應(yīng)選擇消息攻擊下， 敵手不能在多項(xiàng)式時(shí)間內(nèi)偽造出新數(shù)據(jù)的有效簽名. 該安全性通過敵手A與挑戰(zhàn)者C之間的交互實(shí)驗(yàn)ESUFExpA，ES(k) 定義:

(1) 挑戰(zhàn)者C運(yùn)行密鑰生成算法， 獲取公私鑰對(duì)(pk， sk)， 并將公鑰pk 發(fā)送給敵手A.

(2) 敵手A適應(yīng)性地選取q個(gè)數(shù)據(jù){M1，M2，···，Mq}詢問簽名諭言器， 得到q個(gè)原始簽名. 令Q={M1，M2，···，Mq}.

(3) 敵手A輸出偽造的數(shù)據(jù)簽名對(duì)(M*，σ*E).

(4) 挑戰(zhàn)者C運(yùn)行驗(yàn)證算法， 得到b= ESVer(pk，M*，σ*E). 如果b= 1， 且?M ∈Q，M*?M， 則敵手A偽造成功， 并返回“1”; 否則敵手A失敗， 并返回“0”.

定義5 如果對(duì)于所有的PPT 敵手A， 存在可忽略函數(shù)negl 滿足:

則稱可截取簽名方案ES 在自適應(yīng)選擇消息攻擊下滿足存在不可偽造性.

可截取簽名方案的隱私性要求， 在自適應(yīng)選擇消息攻擊下， 攻擊者不能在多項(xiàng)式時(shí)間內(nèi)獲取到已被刪除的信息. 該安全性通過敵手A與挑戰(zhàn)者C之間的交互實(shí)驗(yàn)ESPRExpA，ES(k) 定義:

則稱可截取簽名方案ES 在自適應(yīng)選擇消息攻擊下滿足隱私性要求.

3 基于格的可截取簽名方案

本節(jié)結(jié)合可截取簽名方案的定義[1]， 利用格上原像抽樣函數(shù)， 構(gòu)造基于格上小整數(shù)解問題的可截取簽名方案， 并給出此方案的正確性分析和安全性證明.

3.1 方案設(shè)計(jì)

基于格的可截取簽名方案由以下五個(gè)算法構(gòu)成:

(1) Setup(k): 輸入安全參數(shù)k， 選取正整數(shù)n，q ≥2， 維數(shù)m=O(nlogq). 輸出參數(shù)組params =(n，q，m).

3.2 正確性分析

3.3 安全性證明

證明: 假設(shè)存在敵手AES能以不可忽略的概率攻破上述可截取簽名方案的不可偽造性. 現(xiàn)構(gòu)造算法S模擬攻擊環(huán)境， 具體過程如下:

4 實(shí)驗(yàn)結(jié)果

本節(jié)介紹本文方案的實(shí)驗(yàn)結(jié)果. 實(shí)驗(yàn)主要測(cè)試密鑰生成算法、簽名算法和截取簽名算法的運(yùn)行時(shí)間，以表明本文方案的實(shí)用性. 另外， 在本文實(shí)驗(yàn)給定的參數(shù)設(shè)置下， 給出本文方案相應(yīng)的比特安全性.

本文方案的實(shí)現(xiàn)在Intel? Xeon(R) Gold 6248 CPU @ 2.50 GHz×80 的服務(wù)器上進(jìn)行. 借助Sage-Math 編譯器的良好性能， 配置并調(diào)用多個(gè)外部庫(kù)(如PyCryptodome、FPYLLL 等)， 充分提高了方案的實(shí)現(xiàn)效率.

在簽名算法的實(shí)現(xiàn)方面， 基于文獻(xiàn)[31] 中優(yōu)化的離散高斯抽樣算法， 實(shí)現(xiàn)原像抽樣算法. 此外， 由于本文方案是基于G-陷門構(gòu)造的， 原像抽樣算法的輸入基矩陣是稀疏的， 有效地簡(jiǎn)化了抽樣算法， 從而改良了簽名算法的性能. 除了對(duì)簽名算法的分析， 實(shí)驗(yàn)還分析并測(cè)試了截取簽名算法的有效性. 在實(shí)驗(yàn)中， 分別截取原始數(shù)據(jù)的50%、25%、12.5%， 作為截取簽名算法的輸入， 以檢測(cè)在不同的截取需求下截取簽名算法的有效性與實(shí)用性. 實(shí)驗(yàn)結(jié)果如表2 所示.

表2 實(shí)驗(yàn)數(shù)據(jù)Table 2 Experimental data

表2 中的實(shí)驗(yàn)數(shù)據(jù)表明， 隨著n變大， 簽名算法所耗時(shí)間也隨之增加. 另外， 在不同的截取比例下， 實(shí)驗(yàn)檢測(cè)了截取簽名算法的有效性， 更有力地表明截取簽名算法的實(shí)用性. 正如圖1 所示， 截取簽名算法所耗時(shí)間與待截取的數(shù)據(jù)塊數(shù)量成反比， 能夠大批量地處理實(shí)際的截取需求. 綜上所述， 在達(dá)到較高比特安全性的同時(shí)， 本文方案的效率較高， 接近實(shí)際應(yīng)用的要求.

圖1 截取簽名算法的效率與截取比例之間的關(guān)系Figure 1 Relationship between efficiency of extraction signature algorithm and extraction ratio

值得注意的是， 若在本文方案的原始簽名中加入信息〈c[i]〉i∈[N]， 則可在不影響方案安全性的情況下，就去除截取簽名算法中耗時(shí)的矩陣向量乘法， 而只需對(duì)原始的數(shù)據(jù)簽名對(duì)執(zhí)行簡(jiǎn)單的刪除操作. 此時(shí)， 截取簽名算法的效率將是微秒級(jí). 因此， 如果不考慮原始的簽名長(zhǎng)度， 本文方案的截取簽名算法將會(huì)得到極大的優(yōu)化.

5 總結(jié)與展望

本文提出一個(gè)基于格上小整數(shù)解問題的可截取簽名方案， 并證明了該方案在適應(yīng)性選擇消息攻擊下具有不可偽造性和隱私性. 在不同的參數(shù)設(shè)置下， 本文從理論上分析了該方案對(duì)應(yīng)的比特安全性. 實(shí)驗(yàn)結(jié)果表明， 本文方案在達(dá)到較高安全強(qiáng)度的同時(shí)， 具有較好的效率， 為進(jìn)一步研究格上的可截取簽名方案打下了良好的基礎(chǔ). 此后， 基于格上的其他困難問題， 研究者可嘗試設(shè)計(jì)更加安全高效的可截取簽名方案. 另外， 為進(jìn)一步實(shí)現(xiàn)對(duì)數(shù)據(jù)的有效控制， 研究者可結(jié)合已有的一些截取控制規(guī)則構(gòu)造出更具實(shí)用性的格上可截取簽名方案.