緊致安全的基于身份的簽名方案*

劉翔宇, 劉勝利,3, 谷大武

1. 上海交通大學 計算機科學與工程系, 上海200240

2. 密碼科學技術國家重點實驗室, 北京100878

3. 成都衛(wèi)士通信息產(chǎn)業(yè)股份有限公司摩石實驗室, 北京100070

1 引言

在可證明安全中, 密碼學方案總是基于某些困難問題, 且其安全性是通過安全歸約證明來實現(xiàn)的. 安全歸約的思路如下: 如果存在某個運行時間為t 的敵手A 能以優(yōu)勢? 攻擊某個密碼方案S, 我們通過調(diào)用算法A 構造出另一個運行時間t′的算法B, 使得算法B 以?′的優(yōu)勢解決某個困難問題P. 參數(shù)L := (t′?)/(t?′) 定義為安全歸約中的損失因子. 在安全歸約中, 一般要求L 是一個關于安全參數(shù)λ 的多項式. 因為問題P 的困難性假設認為不存在算法可以在多項式時間內(nèi)解決問題P, 所以密碼方案S 不存在多項式時間的敵手A, 故而證明了S 的安全性. 當t′=Θ(t) 時, 歸約損失因子可等價定義為L:=?/?′.如果L 是一個常數(shù), 那么此安全歸約是緊致的. 如果L=O(λ) (λ 為安全參數(shù)), 歸約是幾乎緊致的. 在很多簽名方案(Signature, 簡稱SIG) 中, 松散安全歸約的損失因子L 與敵手得到的簽名數(shù)Q 及其涉及的用戶數(shù)μ 緊密相關. 假設L ≈240, 這就造成了一個很大的安全損失. 為了彌補這個損失, 在密碼方案的實施過程中, 我們需要選擇更大的安全參數(shù), 導致元素尺寸的增大和計算次數(shù)的增加, 從而降低算法的效率.因此, 近些年來的許多密碼方案都在追求緊致安全性[1–9].

基于身份的簽名(identity-based signature, IBS) 方案最早由Shamir[10]提出. IBS 的實施通常建立在一個群組中, 群組管理員產(chǎn)生主公鑰mvk 和主私鑰msk, 并借助msk 為每個用戶產(chǎn)生一個與其身份id 關聯(lián)的私鑰skid. 用戶可以用skid產(chǎn)生對消息m 的簽名σ, 任何驗證者可以結(jié)合主公鑰mvk 和相應的id, 對(m,σ) 進行驗證. 通常一個簽名方案的基本安全要求是“選擇消息攻擊下的不可偽造性” (簡稱EUF-CMA 安全). 該安全性是指, 即使某一敵手得到了多個消息簽名對, 他也很難偽造出一個新消息的合法簽名. 在基于身份的簽名方案中, 敵手還可能冒充某個身份, 從群組管理員中獲得其身份私鑰. 因此, IBS 安全性要求是: 對于用戶id?, 只要敵手不知道其私鑰skid?, 那么即使敵手得到多個由skid?產(chǎn)生的消息簽名對, 他也很難偽造一個針對id?的新消息的簽名, 這就是EUF-CMA&CIA 安全(正式定義見第2 節(jié)).

緊致安全的簽名方案分為單用戶和多用戶場景(基于身份的簽名方案默認為多用戶場景). 單用戶場景下的緊致安全要求其安全損失因子與敵手得到的簽名數(shù)Q 無關(緊致EUF-CMA 安全); 多用戶場景下的緊致安全不僅要求損失因子與Q 無關, 還要求與用戶數(shù)無關(緊致MU-EUF-CMA 安全). 目前已有許多緊致安全的簽名方案的研究. 在單用戶場景的緊致安全方面, Cramer 和Damg?rd[1]基于RSA 假設給出了第一個緊致EUF-CMA 安全的簽名方案. 隨后出現(xiàn)了許多基于樹結(jié)構的緊致安全的簽名方案, 如文獻[2–7], 另外, 緊致安全的簽名方案可由緊致安全的基于身份的加密方案導出, 如文獻[11,12]. 近年來,還出現(xiàn)了利用非交互零知識證明構造的緊致安全簽名方案, 如文獻[13,14]. 在多用戶場景的緊致安全方面, Hofheinz 和Jager[4]基于DLIN 假設構造了第一個緊致MU-EUF-CMA 安全的簽名方案. 隨后, 張等[7]將其擴展為一個通用構造, 并在MDDH 假設和DCR 假設下給出了具體實例. 在基于身份的簽名方面, 目前鮮有緊致安全的研究. Kiltz 和Neven 在文獻[15] 中總結(jié)了IBS 的三種通用構造方法, 分別基于證書思想[16], 身份認證協(xié)議和分層的基于身份的加密方案, 但其構造都沒有考慮緊致安全性. 已有的一些IBS 的具體構造如文獻[17–19] 等, 其安全歸約都是松散的. 張等在文獻[7] 中給出了第一個緊致(弱)安全的IBS, 他們在IBS 的安全性定義中要求, 若敵手得到了某個id 下的消息簽名對后, 不能再獲取此id 對應的私鑰skid, 因此方案實際上只達到了弱EUF-CMA&CIA 安全性. 目前, 還沒有真正意義上緊致EUF-CMA&CIA 安全的基于身份的簽名方案.

本文主要研究如何實現(xiàn)緊致安全的IBS. 我們進一步研究了文獻[15] 的第一種通用構造方法, 即Bellare 等人[16]所提出的基于證書思想的通用轉(zhuǎn)化方法, 結(jié)合一個緊致EUF-CMA 安全的簽名方案S和一個安全性更高(緊致MU-EUF-CMAcorr安全, 見第2 節(jié)) 的簽名方案?S, 構造了第一個緊致EUFCMA&CIA 安全的基于身份的簽名方案. 與文獻[15,16] 的通用構造相比, 我們的目標是追求緊致安全特性, 因此對子組件的安全要求不同, 安全歸約證明過程也有所差異. 我們分別在隨機預言機模型(random oracle model) 和標準模型(standard model) 下給出相應的具體實例, 主要工作如圖1 所示.

圖1 構造與實例化Figure 1 Construction and instantiations

2 預備知識

本節(jié)給出(常規(guī)) 簽名方案與基于身份的簽名方案的定義及安全性要求. 首先對符號做說明如下. 用λ 表示安全參數(shù); 對于自然數(shù)μ, 用[μ] 表示集合{1,2,··· ,μ}; 用x$←?X 表示從集合X 中均勻隨機地選取x; 用y ←A(x) 表示輸入x 運行算法A 并將結(jié)果賦值給y; 用?表示空字符; 用|| 表示串聯(lián)符號; PPT 是概率多項式時間的縮寫; poly(·) 為多項式函數(shù); 可忽略函數(shù)negl(·) 定義為當λ 足夠大時, 都有negl(λ)<1/poly(λ).

2.1 簽名方案及其安全性

定義1 (簽名方案) 一個簽名方案S=(Setup,KGen,Sign,Ver) 由如下四個算法組成:

? Setup(1λ): 預備算法輸入安全參數(shù)1λ, 輸出公開參數(shù)pp. 假定pp 為Sign 和Ver 的一個隱式輸入.

? KGen(pp): 密鑰生成算法輸入pp, 輸出一對驗證公鑰/簽名私鑰(vk,sk).

? Sign(sk,m): 簽名算法輸入私鑰sk 和消息m, 輸出一個簽名σ.

? Ver(vk,m,σ): 驗證算法輸入公鑰vk, 消息m 和簽名σ, 輸出一個比特, 1 代表σ 是消息m 的一個合法簽名, 0 代表不合法.

正確性: 對任意pp ←Setup(1λ), (vk,sk)←KGen(pp), 任意消息m, 都有Ver(vk,m,Sign(sk,m))=1 成立.

針對一個簽名方案, 敵手可能會自主選擇一些消息, 并獲得這些消息的相應簽名. 不可偽造性要求即使敵手看到了這些消息簽名對, 他也不能對一個新的消息偽造出合法簽名. 安全定義具體如下.

定義2 (EUF-CMA 安全) 對簽名方案S=(Setup,KGen,Sign,Ver), 定義敵手A 在選擇消息攻擊下的攻擊優(yōu)勢

一般簽名方案都部署于多用戶場景. 即敵手會看到多對(用戶) 公鑰, 他可以選擇某一用戶進行攻擊.在某些多用戶應用場景如認證密鑰交換中, 敵手還可以動態(tài)地竊取部分用戶的私鑰sk, 方案安全性在這時要求沒有被竊取密鑰的那些用戶(以及對應公私鑰) 下的簽名的不可偽造性, 即MU-EUF-CMAcorr安全[8]. 安全定義具體如下.

定義3 (MU-EUF-CMAcorr安全) 對簽名方案S = (Setup,KGen,Sign,Ver), 定義敵手A 在多用戶場景中選擇消息攻擊& 動態(tài)密鑰竊取攻擊下的攻擊優(yōu)勢

如果在定義3 中A 只有簽名預言機OSign(·,·) 沒有OCorr(·), 那么S 對應具有多用戶場景中選擇消息攻擊下的不可偽造性, 即MU-EUF-CMA 安全. 通過混合論證我們得知, 簽名方案的EUF-CMA 安全性隱含了MU-EUF-CMAcorr安全性, 不過其歸約證明會有一個損失因子μ, 因此不具有緊致安全性.

2.2 基于身份的簽名方案

定義4 (基于身份的簽名方案) 一個基于身份的簽名方案IBS = (Gen,Ext,Sign,Ver) 由如下四個算法組成:

? Gen(1λ): 主密鑰生成算法輸入安全參數(shù)1λ, 輸出主公鑰/主私鑰(mvk,msk). 默認msk 中包含了mvk 的信息.

? Ext(msk,id): 密鑰提取算法輸入主私鑰msk 和某一用戶id, 輸出此id 對應的身份私鑰skid.

? Sign(skid,m): 簽名算法輸入某一身份私鑰skid和消息m, 輸出一個簽名σ.

? Ver(mvk,id,m,σ): 驗證算法輸入主公鑰mvk、用戶id、消息m 和簽名σ, 輸出一個比特, 1 代表σ 是在此id 下對m 的一個合法簽名, 0 代表不合法.

正確性: 對任意(mvk,msk) ← Gen(1λ), 任意id 和skid← Ext(msk,id), 任意消息m, 都有Ver(mvk,id,m,Sign(skid,m))=1 成立.

在基于身份的簽名方案的應用中, 敵手除了可以動態(tài)獲得某些指定消息的簽名外, 還有可能獲得某些用戶的身份私鑰, 在此時我們要求對于那些未泄露私鑰的用戶, 其簽名是不可偽造的. 安全定義具體如下.

定義5 (EUF-CMA&CIA 安全) 對基于身份的簽名方案IBS=(Gen,Ext,Sign,Ver), 定義敵手A 在選擇消息攻擊& 選擇身份攻擊下的攻擊優(yōu)勢

目前已有的一些基于身份的簽名方案, 如文獻[16,17] 等, 都不具有緊致安全性. 第一個緊致安全方案的嘗試為文獻[7], 但他們僅僅達到了一個弱EUF-CMA&CIA 安全, 即安全性定義要求敵手在問詢了id 相關的簽名預言機之后, 不能問其對應的密鑰提取預言機. 上述弱安全性可通過混合論證推導出(常規(guī))EUF-CMA&CIA 安全性, 但會有一個損失因子μ (敵手在簽名和密鑰提取問詢時所涉及的最大用戶數(shù)).因此, 目前實際上沒有真正緊致安全的基于身份的簽名方案的構造.

3 緊致EUF-CMA&CIA 安全的IBS 的通用構造與安全證明

Bellare 等人在文獻[16] 中提出了由(常規(guī)) 簽名方案到基于身份的簽名方案的通用轉(zhuǎn)化方法, 他們使用的組件為EUF-CMA 安全的簽名方案. 本節(jié), 我們借助文獻[16] 中的基于證書思想的通用轉(zhuǎn)化方法, 提出了一個基于身份的簽名方案的通用構造. 我們所使用的模塊為EUF-CMA 安全的簽名方案S 和MU-EUF-CMAcorr安全的簽名方案?S, 且構造出的IBS 的安全性可以緊致歸約到S 和?S 的安全性.

3.1 構造方案

設S = (S.Setup,S.KGen,S.Sign,S.Ver), ?S = (?S.Setup,?S.KGen,?S.Sign,?S.Ver) 是兩個簽名方案, 我們所提出的基于身份的簽名方案IBS 構造如下.

? Gen(1λ): 調(diào)用pp ← S.Setup(1λ), (vk,sk) ← S.KGen(pp), ?pp ← ?S.Setup(1λ), 置mvk :=(vk,pp, ?pp), msk:=sk 并返回(mvk,msk).

? Ext(msk,id): 調(diào)用(?vk, ?sk)←?S.KGen(?pp), cert ←S.Sign(msk,id||?vk), 并返回skid:=(?vk, ?sk,cert).

? Sign(skid,m): 將skid拆分為(?vk, ?sk,cert), 調(diào)用?σ ←?S.Sign(?sk,m), 并返回簽名σ :=(?vk,cert,?σ).

? Ver(mvk,id,m,σ): 將mvk 拆分為(vk,pp, ?pp), σ 拆分為(?vk,cert,?σ), 如果S.Ver(vk,id||?vk,cert)=1 且?S.Ver(?vk,m,?σ)=1 則返回1, 否則返回0.

3.2 正確性與安全性

上述構造的IBS 的正確性源于其兩個構造組件S 和?S 的正確性.

IBS 的安全性依賴于S 的EUF-CMA 安全性和?S 的MU-EUF-CMAcorr安全性, 且安全歸約具有緊致特性, 參見定理1.

首先BS從他的EUF-CMA 實驗的挑戰(zhàn)者中獲得S 的公開參數(shù)pp 與驗證公鑰vk, 挑戰(zhàn)者同時還提供了一個簽名預言機OSign(·), 其接收BS的輸入m, 調(diào)用σ ←S.Sign(sk,m) 并返回σ. ?S 部分由BS自己執(zhí)行, BS調(diào)用 ?pp ←?S.Setup(1λ), 置mvk := (vk,pp, ?pp), 并發(fā)送mvk 給敵手A. 這里BS隱式地設置msk 為sk. 針對A 的不同問詢, BS做如下應答.

? 當A 進行OExt(id) 問詢時, BS將id 存入集合Qid, 并檢查是否存在(id,skid) ∈Qsk. 如果是則返回此skid; 否則BS調(diào)用(?vk, ?sk) ←?S.KGen(?pp), 向他自己的挑戰(zhàn)者詢問簽名預言機獲得關于id||?vk 的簽名cert, 將(id,skid:=(?vk, ?sk,cert)) 存入Qsk, 隨后返回skid.

? 當A 進行OSign(id,m) 問詢時, BS將(id,m) 存入集合Qm.

– 如果Qsk中存在一項(id,skid), BS將此skid拆分為(?vk, ?sk,cert), 調(diào)用?σ ←?S.Sign(?sk,m), 并返回最終簽名σ :=(?vk,cert,?σ).

綜合公式(1), (2) 和(3), 定理1 得證.

4 通用構造的實例化

在本節(jié)中, 我們分別在隨機預言機模型(random oracle model) 和標準模型(standard model) 下給出了緊致EUF-CMA 安全的簽名方案S 和緊致MU-EUF-CMAcorr安全的簽名方案?S 的實例. 我們省略了算法細節(jié)部分, 僅保留方案所基于的安全假設與結(jié)論.

令GGen 表示一個群生成算法, 其輸入安全參數(shù)1λ, 輸出一個階為q 的循環(huán)群G, 生成元為g, 即(G,q,g)←GGen(1λ).

定義6 (CDH 假設) 對于敵手A, 其解決計算型Diffie-Hellman 問題(CDH 問題) 的優(yōu)勢定義為

4.1 緊致EUF-CMA 安全的簽名方案

4.1.1 隨機預言機模型下的簽名方案SDDH

4.1.2 標準模型下的簽名方案SMDDH

Hofheinz 和Jager[4]利用樹結(jié)構給出了一個緊致EUF-CMA 安全的簽名方案, 其安全性基于DLIN假設. 他們的構造首先從一個保持代數(shù)結(jié)構的一次簽名出發(fā), 利用樹結(jié)構先構造出非自適應安全的簽名,隨后再結(jié)合一次簽名[22]構造出EUF-CMA 安全的簽名方案. 隨后,張等[7]將其思想擴展為到了MDDH假設上并構造出方案SMDDH, 算法詳見文獻[7].

4.2 緊致MU-EUF-CMAcorr 安全的簽名方案

4.2.1 隨機預言機模型下的簽名方案?SDDH

表1 基于DDH 假設的IBS 方案的比較Table 1 Comparison of IBS schemes based on DDH assumption

5 結(jié)束語

本文提出了第一個緊致EUF-CMA&CIA 安全的基于身份的簽名方案, 其安全損失因子與敵手得到的簽名數(shù)Q 及其涉及的用戶數(shù)μ 無關. 方案構造用到了兩個組件, 緊致EUF-CMA 安全的簽名方案S, 和緊致MU-EUF-CMAcorr安全的簽名方案?S. 同時, 通過對兩個組件進行實例化, 我們分別在隨機預言機模型和標準模型下得到了緊致(與幾乎緊致) 安全的基于身份的簽名方案IBSDDH和IBSMDDH,其安全性分別基于DDH 假設和MDDH 假設. 我們這里的IBSMDDH方案基于雙線性配對群, 而雙線性映射計算開銷大,效率低. 如何在標準模型下構造更高效的緊致安全IBS 方案仍是一個值得研究的問題.