一類具有指定驗證者性質的無證書聚合簽名方案

馬陵勇 楊秋宏 賴佳境

摘 要：本文提出了一種無證書具有指定驗證者性質的聚合簽名方案，并對方案的安全性進行了分析。結果表明，新方案不僅滿足聚合簽名的安全性，而且還滿足不可傳遞性和指定的可驗證性。

關鍵詞：雙線性對;計算Diffie-Hellman問題;聚合簽名;廣義指定驗證者

中圖分類號：TP309文獻標識碼：A文章編號：1003-5168（2020）19-0010-03

Abstract： In this paper， we proposed an aggregate signature scheme with no certificate and designated verifier， and analyzed the security of the scheme. The results show that the new scheme not only satisfies the security of aggregate signature， but also satisfies the non transitivity and the specified verifiability.

Keywords： bilinear paring;computational Diffie-Hellman problem;aggregate signature;universal designated verifier

無證書的公鑰密碼體系[1]于2003年由Riyami AI和Paterson K首次提出。在該體系中，密鑰生成中心只生成和掌握用戶的部分私鑰，用戶的完整私鑰由用戶自己的秘密信息和部分私鑰結合生成。相對于基于身份的密碼系統，無證書的公鑰密碼體系避免了密鑰生成中心完全掌控用戶密鑰所進行的不誠實欺騙[2]。同時，與基于證書的密碼系統相比，無證書密碼系統是利用用戶的唯一身份信息（比如，身份證號碼、Email地址等）直接作為用戶公鑰，因此，不需要對公鑰進行認證，節省了因公鑰認證而所付的昂貴代價。無證書密碼系統的這些優點吸引了很多密碼學者的關注。

Boneh在無證書密碼系統中提出聚合簽名的概念。在一些多重簽名交易中，假如交易過程涉及[n]個用戶的多重簽名，則簽名接收者需要對[n]個簽名逐一驗證有效性，其計算量和由此花費的代價可能是難以估量的;而聚合簽名可以把多重簽名合并成一個簽名，接收者只需要驗證這個合并后的簽名，不需要分別驗證個體簽名，就可以確信每一個個體簽名的合法性和有效性。這種思想備受區塊鏈開發者們的關注，因為只需要驗證合并后的聚合簽名，既提高了驗證效率，也節省了節點空間的占用。Gong等人[2]提出了一種無證書的聚合簽名并定義了一種安全模型。關于無證書聚合簽名的最新研究成果可以參考一些其他文獻[3]。

對于任意第三方，傳統的聚合簽名方案都可以使用系統公開的參數對聚合簽名進行驗證，但是，這種公開驗證性暴露了簽名生成者的信息，某些實際應用中（如電子選舉、電子商務等）需要保護簽名者的信息，只有被賦予權限的用戶才可以驗證聚合簽名，其他用戶不能驗證聚合簽名，也就不能確信簽名者的信息。而指定驗證者簽名方案的提出很好地解決了這個問題。

Chen等[3]在2015年提出了一類高效的無證書聚合簽名方案，研究者在該方案中引入指定驗證者簽名方法，設計了一種新的無證書的指定驗證者聚合簽名方案。新方案滿足正確性、強指定驗證性、不可偽造性、不可傳遞性和高效性。

1 預備知識

1.1 定義1：雙線性對

設[G1]是一個加法循環群，其階為素數[q]，[P]是它的一個生成元;[G2]是一個乘法循環群，其階也為[q]。若映射[e：G1×G1→G2]滿足以下三個條件，則稱這個映射為雙線性映射，也叫雙線性對。

第一，雙線性：對于任意[U，V∈G1，a，b∈Z*q]，[e（aU，bV）][=e（U，V）ab]。

第二，非退化性：存在[U，V∈G1]，使得[e（U，V）≠1G2]。

第三，可計算性：對于任意的[U，V∈G1]，存在已知高效的算法來計算[e（U，V）]的值。

1.2 定義2：計算性Difiie-Hellman問題（CDHP）

給定一個階為[q]的循環群[G]，它的一個生成元[P]以及[aP，bP∈G]（[a，b∈Z*q]且值未知），計算[abP∈G]。

1.3 定義3：計算雙線性Difiie-Hellman問題（CBDHP）

對任意[a，b，c∈Z*q]，且值未知，給定[P，aP，bP，cP]計算[e（P，P）abc]的值。

2 具有廣義驗證者性質的無證書聚合簽名方案

2.1 方案描述

Ming等把無證書廣義驗證者聚合簽名定義為三類算法：第一類是無證書聚合簽名算法;第二類是指定驗證者簽名算法;第三類是指定驗證者驗證算法。本文把聚合簽名算法與指定驗證者簽名算法統一為指定驗證者聚合簽名生成算法，同時，把聚合簽名算法與指定驗證者驗證算法也統一為指定驗證者聚合簽名驗證算法，研究者提出的方案由此簡化為6個算法，具體描述如下。

第一，建立初始系統。輸入安全參數[k]，該算法輸出系統全局參數空間[param=（G1，G2，e，q，P，P0，H1，][H2，H3，H4，H5，HDV）]，其中[（G1，+）]和[（G2，·?）]是上述定義1中的循環群，階均為素數[q≥2k]，[P]是[G1]的一個生成元，[e]為定義1中的雙線性對，[H1，H2，H3：{0，1}*→G1?]，[H4，H5：0，1?→Z?q]，[HDV：0，1?→Zq?]是安全的哈希函數，密鑰生成中心（Key Generation Centre，KGC）輸出系統主密鑰[s∈Z?q]并保密，[P0=sP]為系統公鑰。

第二，部分私鑰提取。由用戶和KGC交互完成，用戶提交自己的身份[IDi∈{0，1}?]給KGC，KGC計算[Di=sQi=sH1（IDi）]，然后把[Di]經安全方式返回給用戶。

第三，公/私鑰對生成。用戶[IDi]隨機選取[xi∈Z*p]，計算[Pi=xiP]，公鑰為[Pi]，私鑰為[（xi，Di）]。

第四，個體簽名生成。聚合簽名生成者[IDA]選取一個狀態信息[Δ]，并廣播給每一個參與個體，身份[IDi]的用戶，執行如下計算，從而對消息[mi]（i = 1，2，…，n）進行簽名。①隨機選取[r∈Z*p]，計算[Ri=riPhi=H4（miΔRiIDi）]和[gi=H5（miΔRiPi）];②計算[Wi=giDi+xihiU+riV]，其中[U=H2（ΔP），V=H3（ΔP0）];③輸出[σi=（Ri，Wi）]為個體簽名。

第五，指定驗證者聚合簽名生成算法。假如聚合者為[IDA]，[IDA]收齊[n]個個體簽名后，在公開狀態信息[Δ]下對被指定的驗證者身份[IDDV]，公鑰為[PDV]的指定驗證者聚合簽名按如下方式進行：①計算[W=W1+W2+…+Wn]和[hDV=HDV（xAPDV）];②計算[S=e（W，hDVPDV）]。

輸出給指定驗證者[IDDV]的聚合簽名為[σ=（R1，R2，…，Rn，S）]。

第六，指定驗證者聚合簽名驗證算法。指定驗證者[IDDV]的用戶對來自于聚合者[IDA]簽名[σ=（R1，R2，…，Rn，S）]的有效性進行驗證。輸入身份信息集[{ID1，ID2，…，IDn}]、公鑰信息集[{P1，P2，…，Pn}]、消息集合[{m1，m2，…，mn}]以及聚合簽名[σ=（R1，R2，…，Rn，S）]，[IDDV]的操作為：①計算[U=H2（ΔP），V=H3（ΔP0）][，hi=H4（miΔRiIDi）]，[gi=H5（miΔRiPi）]和[Qi=H1（IDi）];②計算[hDV=HDV（xDVPA）];③驗證[S=[e（i=1ngiQi，P0）e（i=1nhiPi，U）e（i=1nRi，V）]xDVhDV]是否為真，若真，則接受[σ]，否則，拒絕[σ]。

2.2 安全性分析

2.2.1 方案的正確性。定理1：本文提出的新方案是正確的。

證明：指定驗證者聚合簽名[σ=（R1，R2，…，Rn，S）]能而且只能由被指定的身份為[IDDV]，公鑰為[PDV]的用戶正確驗證：

[S=eW，hDVPDV=ei=1nWi，hDVPDV=ei=1ngiDi+xihiU+riV，hDVPDV=ei=1ngiDi，hDVPDVei=1nxihiU，hDVPDVei=1nriV，hDVPDV=ei=1ngiQi，P0ei=1nhiPi，Uei=1nRi，VxDVhDV] ? ? ? ? ? （1）

所以，本文方案是正確的。

2.2.2 強指定驗證性。根據定理1的證明過程，指定驗證者的聚合簽名的驗證階段需要恢復[hDV=HDV（xAPDV）]，而[hDV=HDV（xAPDV）=HDV（xAxDVP）=HDV（xDVPA）]，只有[IDDV]擁有私鑰[xDV]，其他用戶不能正確地恢復出[hDV=HDV（xAPDV）]，也就無法驗證聚合簽名的正確性;而指定驗證者[IDDV]可以利用自己的私鑰恢復[hDV=HDV（xAPDV）]，同時，根據驗證算法，[IDDV]信任這個聚合簽名[σ=（R1，R2，…，Rn，S）]是來自聚合者[IDA]，身份為[IDi（i=1，2，…，n）]的用戶對消息[mi（i=1，2，…，n）]分別進行了簽名，所以，本文方案滿足強指定驗證性。

2.2.3 不可偽造性。一般的無證書聚合簽名方案的不可偽造性需要考慮一類攻擊，這類偽造攻擊中存在兩個具有不同能力的敵手[AⅠ]和[AⅡ]，相應的有一個可以解決某種困難問題的挑戰者[C]，挑戰者[C]與敵手進行兩類交互游戲，關于敵手[AⅠ]和[AⅡ]的定義以及挑戰者[C]與之進行的交互游戲見Chen H的研究[3]。同時，基于CDH困難問題，Chen H的研究[3]也證明了其無證書聚合簽名方案滿足適應性選擇消息和身份攻擊下的存在性不可偽造。而本文方案是基于Chen H的研究[3]進行改進的，所以，本文方案滿足自適應性選擇消息和身份攻擊下的存在性不可偽造。

無證書的指定驗證者聚合簽名方案除了滿足上述的一類攻擊安全之外，還要考慮另一種攻擊類型，即對指定驗證者身份的攻擊。

關于第二類攻擊，我們定義一類攻擊者[AⅢ]，[AⅢ]所具有的攻擊能力類似于前述的攻擊者[AⅠ]和[AⅡ]，在不同的攻擊下可以分別充當外部敵手和內部不誠實的KGC身份，指定驗證者聚合簽名方案如果存在敵手[AΙΙΙ]以不可忽略的概率在如下游戲1中獲勝，則無證書具有指定驗證者的聚合簽名方案在適應性選擇消息和指定身份攻擊下指定驗證者簽名不可偽造。

游戲1：假設[C]為游戲的挑戰者。[C]在游戲開始之前進行的運算和第一類攻擊者下挑戰者所做的運算一樣產生系統參數和系統主密鑰[s]，并與攻擊者[AⅢ]模擬交互，而攻擊者[AⅢ]在游戲過程中可以詢問以下預言機。

①Hash函數詢問、部分私鑰提取詢問、秘密值詢問、用戶公鑰詢問、公鑰替換詢問，這些詢問與第一類攻擊類型中敵手[AⅠ]與挑戰者之間的游戲相同，如果[AⅢ]是不誠實的KGC，則不能做部分私鑰詢問和公鑰替換詢問。

②指定驗證者聚合簽名詢問：[AⅢ]可以獲得[M?={m1?，m2?，…，mn?}]指定驗證者[IDDV?]的簽名。

攻擊者[AⅢ]按照上述詢問得到的信息，可以輸出對[M?={m1?，m2?，…，mn?}]指定驗證者[IDDV?]的指定驗證者聚合簽名[σDV?]，[AΙΙΙ]在該游戲中獲勝當且僅當以下條件滿足：第一，[σDV?]是一個有效的無證書指定驗證者聚合簽名，可以通過合法驗證;第二，[AⅢ]之前沒有對[M?={m1?，m2?，…，mn?}]進行過指定驗證者聚合簽名詢問;第三，[AⅢ]沒有對指定驗證者[IDDV]的私鑰詢問。

定理2：本文的無證書指定驗證者聚合簽名方案對第二類攻擊者[AⅢ]滿足存在性不可偽造。

證明：不妨假設敵手[AⅢ]對偽造的身份[IDDV?]，偽造的消息集合[M?={m1?，m2?，…，mn?}]所計算的指定驗證者的聚合簽名為[σDV?=（M?，R1?，R2?，…，Rn?，S?）]。如果該偽造能夠順利通過驗證算法，兩種方式敵手[AⅢ]都可以實現偽造，取得[IDDV]的私鑰，或者取得對[M?={m1?，m2?，…，mn?}]偽造的聚合簽名。

第一種方式偽造是不可能的，哈希函數[HDV]的輸入只有兩個值，即[xAPDV]和[xDVPA]，由這兩個輸入值獲取[xDV]相當于計算CDH困難問題。同時，由于哈希函數本身的單向性，由哈希值獲得哈希輸入也是不可能的。

第二種方式的偽造同樣不可行，敵手[AⅢ]要獲得對[M?={m1?，m2?，…，mn?}]的偽造聚合簽名，等價于[AⅢ]扮演了敵手類型[AⅠ]和[AⅡ]，這在Chen H的研究中[8]中已經被證明是不可能的。

所以，本文的方案滿足對第二類攻擊者[AⅢ]的存在性不可偽造。

2.2.4 不可傳遞性。所謂不可傳遞性是指指定驗證者可以模仿聚合生成者生成一個合法的指定聚合簽名，其他第三方不能冒充，以防止指定驗證者的抵賴行為。

定理3：方案滿足指定驗證者簽名的不可傳遞性。

證明：在簽名[σ=（R1，R2，…，Rn，S）]中，[S=e（W，hDVPDV）]，而[hDV=HDV（xAPDV）=HDV（xDVPA）]，由于指定驗證者可以恢復[hDV]，所以其可以模仿聚合生成者[IDA]生成一個簽名的副本[σ′]，而且可以順利通過驗證者算法。

3 方案的效率分析

Chen H的研究[3]比較了幾類經典無證書聚合簽名方案的效率，證實了其提出的無證書聚合簽名方案具有高效性，本方案是對Chen H提出的方案[3]的改進，在指定驗證者簽名和指定驗證者驗證時均沒有增加計算復雜性，所以新方案依然具有高效性。

4 結語

基于Chen H的研究[3]提出了一種無證書的具有指定驗證者性質的聚合簽名方案。新方案滿足正確性、強指定驗證性、不可為造性、不可傳遞性和高效性。設計安全高效的無證書指定驗證者聚合簽名方案仍然是需要進一步研究的課題。

參考文獻：

[1] Al-Riyami S S，Paterson K G . Certificateless Public Key Cryptography[C]// International Conference on the Theory and Application of Cryptology and Information Security. Springer， Berlin， Heidelberg，2003.

[2] Gong Z ， Long Y ， Hong X ， et al. Two Certificateless Aggregate Signatures From Bilinear Maps[C]// Eighth ACIS International Conference on Software Engineering，Artificial Intelligence， Networking， and Parallel/Distributed Computing （SNPD 2007）. IEEE， 2007.

[3]Chen H， Wei SM， Zhu CJ， Yang Y. S ecure certificateless aggregate signature scheme[J].Ruan Jian Xue Bao/Journal of Software，2015（5）：1173-1180.