格上無陷門的無證書簽名

梁紅梅

（1.閩南師范大學數(shù)據(jù)科學與統(tǒng)計重點實驗室,福建漳州363000；2.閩南師范大學數(shù)學與統(tǒng)計學院,福建漳州363000）

無證書公鑰密碼體制(Certificateless Public Key Cryptography, CL-PKC)于2003 年由Al-Riyami 和Paterson[1]在ASIACRYPT’03會議上提出.在無證書密碼體制下，密鑰由兩部分組成.一部分由密鑰生成中心（Key Generator Center，KGC）產(chǎn)生，另一部分由用戶產(chǎn)生.KGC 根據(jù)用戶的公開信息（如身份、郵件等）產(chǎn)生一個部分私鑰，并將部分私鑰通過安全信道傳送給用戶；當用戶收到部分私鑰后，首先驗證部分私鑰的有效性，然后選取一個秘密值并產(chǎn)生相應的公鑰；用戶的私鑰由部分私鑰和自選的秘密值組合產(chǎn)生.無證書公鑰密碼體制，能夠有效地解決傳統(tǒng)公鑰密碼PKI 中的證書管理問題，也能夠有效避免身份基密碼體制中的密鑰托管問題.Al-Riyami等[1]提出了無證書密碼體制之后，無證書密碼體制得到了廣泛的研究.無證書簽名是其中一個重要研究[2-9].

隨著我國商密標準算法的發(fā)展，關(guān)于無證書密碼體制的商密標準算法的制定也已經(jīng)起步.然而，當前關(guān)于無證書密碼體制的研究大多數(shù)仍是建立在傳統(tǒng)代數(shù)數(shù)論的困難問題上.在量子算法的分析下，它們是不能滿足安全需求的.由于量子計算和量子算法給傳統(tǒng)的密碼體制帶來的威脅，后量子密碼逐漸成為了密碼學者們研究的熱點.我國也開始了后量子密碼算法的征集工作.

在后量子密碼當中，格密碼是其中的熱門研究之一[10-15].研究基于格的無證書簽名方案具有一定的理論和實用價值.目前，基于格的無證書簽名方案僅有田苗苗等[16]和謝佳等[17]的方案.他們的方案都是基于Lyubashevsky[18]在Eurocrypt2012 上的格上無陷門簽名方案.可是，他們的方案中依然采用了陷門技術(shù)，這一點與Lyubashevsky 的工作相悖.由此，利用Lyubashevsky[19]在Asiacrypt2009 上的工作，構(gòu)造了一個格上無陷門的無證書簽名方案.

1 預備知識

1.1 格的基礎(chǔ)知識

定義1（格）假設(shè)矩陣B ∈Rn×m由m個線性無關(guān)的n維向量{b1,b2,…,bm}組成，那么由B 產(chǎn)生的格L可定義如下：

一般地，格L(B)上的最短向量記為λ1(L(B)).

定義2（SVPγ問題[20]）給定一個n維格L 和一個有理數(shù)γ ≥1，SVPγ問題的目標是在格L 上找到一個非零向量v，滿足

1.2 抗碰撞Hash函數(shù)

Lyubashevsky等[21]的抗碰撞Hash函數(shù).

設(shè)n是一個2的次冪，R是多項式環(huán)Zp[x]/xn+ 1 .

定義3（抗碰撞Hash函數(shù)族）對于D?R，整數(shù)是一個抗碰撞Hash函數(shù)族.其中，所有的運算都是R上的運算.

抗碰撞Hash 函數(shù)族H(R,D,m)中的任意Hash 函數(shù)h有兩個性質(zhì)：對于任意的y?,z?∈Rm和c?∈R，等式?成立.

定義4（Col(h,D)問題）給定D?R和函數(shù)h∈H(R,D,m)，Col(h,D)問題的目標是在Dm上找到兩個不同的多項式向量成立.

根據(jù)Lyubashevsky 等[21]的工作可知，對于任意的(xn+ 1)循環(huán)格，Col(h,D)問題的困難性等價于SVPγ問題的困難性.

1.3 無證書簽名方案的安全模型

無證書簽名方案的安全性，可以用游戲模型來刻畫.在無證書簽名方案的安全模型中，一般存在兩類攻擊者.一類是第I 型攻擊者AI，也就是非法用戶，即未獲得部分私鑰的用戶；另一類是第II 型攻擊者AII，也就是惡意KGC.下面，分別用游戲Game I 和Game II 來描述無證書簽名方案的安全性.游戲Game I 和Game II分別在挑戰(zhàn)者C與第I型攻擊者AI和第II型攻擊者AII之間交互進行.

Game I：挑戰(zhàn)者C首先運行系統(tǒng)初始化算法生成系統(tǒng)的主私鑰msk、主公鑰mpk和公共參數(shù)params，然后將系統(tǒng)的主公鑰mpk和公共參數(shù)params發(fā)送給AI.系統(tǒng)的主私鑰msk對AI保密.挑戰(zhàn)者C向攻擊者AI提供詢問服務.

用戶建立詢問：攻擊者AI關(guān)于身份ID進行用戶建立詢問，挑戰(zhàn)者C首先為身份ID生成部分私鑰、秘密值、公鑰，然后將公鑰返回給攻擊者AI.

部分私鑰提取詢問：攻擊者AI關(guān)于身份ID進行部分私鑰提取詢問，挑戰(zhàn)者C返回相應的部分私鑰給攻擊者AI.

秘密值提取詢問：攻擊者AI關(guān)于身份ID進行秘密值提取詢問，挑戰(zhàn)者C返回相應的秘密值給攻擊者AI.

公鑰替換詢問：攻擊者AI可以關(guān)于身份ID進行公鑰替換詢問，挑戰(zhàn)者C替換相應的公鑰.

Hash詢問：攻擊者AI關(guān)于任意輸入進行Hash詢問，挑戰(zhàn)者C返回相應的Hash值給攻擊者AI.

簽名詢問：攻擊者AI關(guān)于身份ID和消息μ進行簽名詢問，挑戰(zhàn)者C返回相應的簽名給攻擊者AI.

最后，攻擊者AI輸出一個關(guān)于身份ID*和消息μ*的偽造無證書簽名sig*.

攻擊者AI贏得游戲當且僅當以下條件全部滿足：1）(μ*,sig*)經(jīng)驗證算法驗證是有效的；2）攻擊者AI未關(guān)于身份ID*進行部分私鑰提取詢問；3）(μ*,sig*)不是簽名詢問返回的結(jié)果.

Game II：挑戰(zhàn)者C首先運行系統(tǒng)初始化算法生成系統(tǒng)的主私鑰msk、主公鑰mpk和公共參數(shù)params，并發(fā)送給AII.挑戰(zhàn)者C向攻擊者AII提供詢問服務：用戶建立詢問、部分私鑰提取詢問、秘密值提取詢問、Hash詢問、簽名詢問.（詢問服務與Game I中一樣.）

最后，攻擊者AII輸出一個關(guān)于身份ID*和消息μ*的偽造無證書簽名sig*.

攻擊者AII贏得游戲當且僅當以下條件全部滿足：1）(μ*,sig*)經(jīng)驗證算法驗證是有效的；2）攻擊者AII未關(guān)于身份ID*進行秘密值提取詢問；3）(μ*,sig*)不是簽名詢問返回的結(jié)果.

定義（強不可偽造性）若任意的多項式時間攻擊者贏得Game I和Game II的概率是可忽略的，則稱該無證書簽名方案在隨機諭言機模型下對適應性選擇消息攻擊和適應性選擇身份是強存在性不可偽造的.

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

本節(jié)介紹格上無陷門的無證書簽名方案構(gòu)造.首先簡單說明一下相關(guān)參數(shù).

由安全參數(shù)n，可定義參數(shù)m= logn，d=mn1.5logn，素數(shù)p> 4d2，且滿足p= 3mod 8.當n> 4 時，可驗證不等式p> 4dmn1.5logn和m>成立.根據(jù)n,m,d,p，可定義集合：R= Zp[x]/ ，D=d-n0.5logn}.

2.1 構(gòu)造的方案

無陷門的無證書簽名方案構(gòu)造具體如下.

●Setup(n)：給定安全參數(shù)n，定義參數(shù)m，d，素數(shù)p以及相關(guān)集合：R，D，Dh，Ds，Dz.由R，D，m，定義抗碰撞Hash 函數(shù)族H(R,D,m)，并從中隨機選取一個抗碰撞Hash 函數(shù)h.選取兩個隨機諭言機哈希函數(shù)H1,H2:{0,1}*→Dh.隨機選取輸出系統(tǒng)的主私鑰?、主公鑰?和公共參數(shù)params={n,m,d,p,R,D,Dh,Ds,Dz,H1,H2,h}.

●部分私鑰提?。‥xtract-Partial-Private-Key）：給定系統(tǒng)的公共參數(shù)params、主私鑰msk和用戶的身份ID，操作如下：

●秘密值設(shè)置（Set-Secret-Value）：給定系統(tǒng)的公共參數(shù)params，用戶隨機選取秘密值∈，并計算

●私鑰設(shè)置（Set-Private-Key）：給定系統(tǒng)的公共參數(shù)params、用戶的部分私鑰和秘密值，輸出用戶的私鑰

●公鑰設(shè)置（Set-Public-Key）：給定系統(tǒng)的公共參數(shù)params、用戶的私鑰skID和部分公鑰，輸出用戶的公鑰

●簽名（CL-Sign）：給定系統(tǒng)的公共參數(shù)params、用戶的身份ID和私鑰skID，待簽名消息μ，操作如下：

4)若??Dmz，則重新選取?；否則，輸出簽名

●驗證（CL-Verify）：給定系統(tǒng)的公共參數(shù)params、簽名人的身份ID和公鑰pkID、消息簽名對(μ,sig)，操作如下：

4)若3)成立，則輸出“有效”；否則，輸出“無效”.

2.2 正確性

可知，簽名的正確性可以有效驗證.

2.3 安全性

引理1若存在第I型攻擊者AI能夠在概率多項式時間內(nèi)以不可忽略的概率ε偽造一個我們方案的有效簽名，那么挑戰(zhàn)者C利用攻擊者AI的能力獲得一個Col(h,D)問題的解的概率至少是其中，e 是自然對數(shù)，tI是允許AI進行Hash詢問的最大次數(shù).

證明假設(shè)攻擊者AI是一個概率多項式時間攻擊者.它能夠以不可忽略的概率ε偽造一個方案的有效簽名.下面模擬挑戰(zhàn)者C和攻擊者AI之間的游戲Game I.

挑戰(zhàn)者C運 行Setup(n)算法并輸出主私鑰、主公鑰?和公共參數(shù)params={n,m,d,p,R,D,Dh,Ds,Dz,H1,H2,h}，然后將主公鑰mpk和公共參數(shù)params發(fā)送給AI.主私鑰msk對AI保密.挑戰(zhàn)者C向攻擊者AI提供詢問服務：

用戶建立詢問：挑戰(zhàn)者C初始化列表為空.當AI關(guān)于身份IDi進行詢問時，C查找列表L1.若已存在，則將返回給AI.否則，隨機選取和然后將返回給AI且將保存至列表L1中.

部分私鑰提取詢問：當AI關(guān)于身份IDi進行詢問時，C查找列表L1.若已存在，則將?返回給AI.否則，C先自己進行一次關(guān)于IDi的用戶建立詢問，然后將相應的部分私鑰返回給AI.

秘密值提取詢問：當AI關(guān)于身份IDi進行詢問時，C查找列表L1.若已存在，則將?返回給AI.否則，C先自己進行一次關(guān)于IDi的用戶建立詢問，然后將相應的秘密值返回給AI.

公鑰替換詢問：當AI關(guān)于身份IDi進行公鑰(IDi,)替換詢問時，C查找列表L1中是否存在IDi.若不存在，則C先自己進行一次關(guān)于IDi的用戶建立詢問.最后C替換相應的公鑰并將保存至列表L1中.

H1詢問：C初始化列表為空.當AI關(guān)于進行H1詢問時，C首先查找列表L1中是否存在若存在，則直接將相應的? 返回給AI.否則，C查找列表L2，如果不存在，那么隨機選取∈Dh.C將相應的?返回給AI并將保存至列表L2中.

H2詢問：C初始化列表為空.當AI關(guān)于進行H2詢問時，C查找列表L3.若已存在，則C直接將? 返回給AI.否則，C隨機選取c?i∈Dh，然后返回給AI并將保存至列表L3中.

簽名詢問：C初始化列表為空.當AI關(guān)于(IDi,μi)進行簽名詢問時，C查找列表L4.若已存在，則C直接將返回給AI.否則，C先查找列表L1以獲得若列表L1中不存在IDi，則C自己進行一次關(guān)于的用戶建立詢問.然后，C隨機選取最后，C將返回給AI，并 將分別保存至列表L3、列表L4中.

輸出偽造：攻擊者AI以不可忽略的概率ε輸出一個關(guān)于身份ID*和消息μ*的有效偽造無證書簽名其中，AI從未關(guān)于ID*進行過部分私鑰提取詢問，且不是簽名詢問返回的結(jié)果.

根據(jù)文獻[23]和文獻[24]的分叉引理可知，對H1函數(shù)使用分叉引理時，攻擊者AI可以輸出兩個有效偽造簽名且輸出成功的概率為其中，e是自然對數(shù)，tI是允許AI進行Hash詢問的最大次數(shù).

引理2若存在第II 型攻擊者AII能夠在概率多項式時間內(nèi)以不可忽略的概率ε偽造一個我們方案的有效簽名，那么挑戰(zhàn)者C利用攻擊者AII的能力獲得一個Col(h,D)問題的解的概率至少是其中，e是自然對數(shù)，tII是允許AII進行Hash詢問的最大次數(shù).

證明假設(shè)攻擊者AII是一個概率多項式時間攻擊者.它能夠以不可忽略的概率ε偽造一個方案的有效簽名.下面模擬挑戰(zhàn)者C和攻擊者AII之間的游戲Game II.

挑戰(zhàn)者C運 行Setup(n)算法并輸出主私鑰、主公鑰?和公共參數(shù)params={n,m,d,p,R,D,Dh,Ds,Dz,H1,H2,h}，然后發(fā)送給AII.挑戰(zhàn)者C向攻擊者AII提供如下詢問服務：用戶建立詢問、部分私鑰提取詢問、秘密值提取詢問、H1詢問、H2詢問、簽名詢問.過程與引理1中的一樣.

輸出偽造：攻擊者AII以不可忽略的概率ε輸出一個關(guān)于身份ID*和消息μ*的有效偽造無證書簽名其中，AII從未關(guān)于ID*進行過秘密值提取詢問，且不是簽名詢問返回的結(jié)果.

根據(jù)文獻[23]和[24]的分叉引理可知，對H2函數(shù)使用分叉引理時，攻擊者AII可以輸出兩個有效偽造簽名，且輸出成功的概率為其中，e 是自然對數(shù)，tII是允許AII進行Hash 詢問的最大次數(shù).

從而，C以的概率獲得了一個Col(h,D)問題的解.

根據(jù)引理1、引理2和文獻[19]，可以得到定理1.

定理1在任意(xn+ 1)循環(huán)格Λ上的SVPγ(Λ)問題是難解的困難假設(shè)下，無證書簽名方案在隨機諭言機模型下，對適應性選擇消息和適應性選擇身份攻擊是強存在性不可偽造的.

2.4 效率分析

已有的格上無證書簽名方案中，文獻[16]和文獻[17]的方案較為高效.這兩個方案同樣都是在Lyuba‐shevsky工作的基礎(chǔ)上構(gòu)建的.Lyubashevsky工作的關(guān)鍵技術(shù)是拒絕采樣，即無陷門.然而，文獻[16]和文獻[17]的方案都是在Lyubashevsky 工作的基礎(chǔ)上加入采樣技術(shù)（陷門技術(shù)）后實現(xiàn)無證書簽名的方案.方案雖然也是在Lyubashevsky 工作的基礎(chǔ)上構(gòu)建的，但沒有使用采樣技術(shù)（陷門技術(shù)）.在安全強度方面，方案的安全強度是隨機諭言機模型下的強存在性不可偽造.而文獻[16]和文獻[17]則是存在性不可偽造.如表1所示.

表1 計算復雜性和安全性比較Tab.1 Comparison of computational complexity and security

因此，方案在計算復雜度和安全強度上要優(yōu)于已有方案.

3 結(jié)論

Lyubashevsky 提出了拒絕采樣技術(shù)，并在此基礎(chǔ)上構(gòu)建了無陷門的簽名方案.隨后，在Lyubashevsky工作的基礎(chǔ)上出現(xiàn)了眾多具有不同性質(zhì)的方案.其中便有田苗苗等和謝佳等的無證書簽名方案.然而，他們在Lyubashevsky 工作的基礎(chǔ)上又加入了采樣技術(shù)和陷門技術(shù).這與Lyubashevsky 的拒絕采樣技術(shù)相悖.無證書簽名方案也是在Lyubashevsky工作的基礎(chǔ)上構(gòu)建的，且沒有使用采樣技術(shù)或陷門技術(shù).本方案可以被證明在隨機諭言機模型下，對適應性選擇消息和身份攻擊是強存在性不可偽造的.