吳華麟,陳文彬,3,高崇志,劉 淼,李 進(jìn)

1.廣州大學(xué) 計算機(jī)科學(xué)與網(wǎng)絡(luò)工程學(xué)院,廣州 510006

2.廣州大學(xué) 人工智能與區(qū)塊鏈研究院,廣州 510006

3.廣西密碼學(xué)與信息安全重點實驗室,桂林 541004

1 引言

同態(tài)簽名是指在沒有簽名私鑰的情況下,允許任何實體對已認(rèn)證的數(shù)據(jù)進(jìn)行同態(tài)運算操作生成新數(shù)據(jù),并得到新數(shù)據(jù)的有效簽名.自被提出以來,同態(tài)簽名越來越受到人們的關(guān)注.同態(tài)簽名特殊的性質(zhì)使其具有廣泛的理論研究空間和極高的科研價值,并在許多實際應(yīng)用中都有著重要的作用,比如可以為網(wǎng)絡(luò)編碼、云計算以及傳感網(wǎng)絡(luò)等領(lǐng)域提供有效的解決方案.

同態(tài)簽名方案的概念最早在2000年由Rivest提出[1],緊接著Johnson等人在2002年引入了同態(tài)簽名的形式化定義以及總體框架[2],隨后相繼產(chǎn)生了許多不同類型的同態(tài)簽名方案.同態(tài)簽名方案如果按同態(tài)運算函數(shù)進(jìn)行分類,可以分為線性同態(tài)簽名、多項式函數(shù)同態(tài)簽名和全同態(tài)簽名.最初提出的方案是線性同態(tài)簽名方案,在2007年Zhao等人提出了一個線性同態(tài)簽名方案[3],該方案允許對簽名數(shù)據(jù)進(jìn)行任意的線性組合計算,能夠方便地檢查接收消息的完整性,還能有效防止建立在網(wǎng)絡(luò)編碼上的應(yīng)用程序受到污染攻擊.在接下來的時間里,人們針對效率、安全性和隱私保護(hù)進(jìn)行進(jìn)一步改進(jìn),提出了大量高效實用的線性同態(tài)簽名方案[4-6].線性同態(tài)簽名方案允許任意的實體在沒有簽名私鑰的情況下,對已簽名的數(shù)據(jù)進(jìn)行線性組合生成新數(shù)據(jù),并且能夠生成新數(shù)據(jù)的有效簽名.而Lin等人受到了Rivest在2000年提出的開放問題的啟發(fā),于2017年提出了帶有指定實體的線性同態(tài)簽名方案[7].除了線性同態(tài)簽名外,人們還構(gòu)造了更加靈活的多項式函數(shù)同態(tài)簽名方案和全同態(tài)簽名方案.2011年Boneh等人提出了第一個多項式函數(shù)同態(tài)簽名,該方案能夠允許對簽名數(shù)據(jù)進(jìn)行多元多項式計算[8].而全同態(tài)簽名與線性同態(tài)簽名、多項式函數(shù)同態(tài)簽名不同,全同態(tài)簽名不再對函數(shù)進(jìn)行限制,而是允許對簽名數(shù)據(jù)進(jìn)行任意電路運算,比較具有代表性的是2014年Gorbunov等人提出的基于格的層次型全同態(tài)簽名方案[9].然而上述這些同態(tài)簽名方案都假定每一個輸入的簽名數(shù)據(jù)是使用相同的私鑰進(jìn)行簽名的,也就是說這些同態(tài)簽名方案只適用于單用戶或者單源網(wǎng)絡(luò)編碼系統(tǒng)的情況,對于多用戶或者多源網(wǎng)絡(luò)編碼系統(tǒng)的應(yīng)用程序卻不能提供有效的解決方案.為了克服這一限制,Zhang等人將聚合屬性引入到多用戶情況下的同態(tài)簽名方案中,即允許對使用不同的私鑰產(chǎn)生的簽名數(shù)據(jù)進(jìn)行計算操作,從而構(gòu)造出同態(tài)聚合簽名方案[10].除了同態(tài)聚合簽名方案之外,最近幾年還提出了多鑰同態(tài)簽名方案,該類型的方案不僅能為多密鑰的環(huán)境下提供解決方案,并且還使得密鑰空間也具有同態(tài)性,而其他類型的同態(tài)簽名方案中的同態(tài)性僅限于消息空間[11].

在設(shè)計與應(yīng)用同態(tài)簽名方案的時候,我們需要考慮方案的正確性和安全性是否能夠達(dá)到一定的要求.同態(tài)簽名方案的安全性包括不可偽造性(unforgeability)和隱私性(privacy).一般來說,同態(tài)簽名方案能夠達(dá)到的最強(qiáng)大的安全要求為在自適應(yīng)選擇消息攻擊下具有不可偽造性(existential unforgeability under adaptive chosen message attack,EUF-CMA)[12],以及隱私性達(dá)到完全上下文隱藏[13].除了安全性之外,還需要考慮其他的特性,比如構(gòu)造的方案基于哪些密碼學(xué)基礎(chǔ)、計算效率的高低、簽名數(shù)據(jù)長短,以及安全性證明是基于隨機(jī)預(yù)言機(jī)模型還是標(biāo)準(zhǔn)模型等.本文將描述可以使用同態(tài)簽名方案的三個云計算應(yīng)用場景(電子投票、智能電網(wǎng)和電子健康記錄)的要求,然后根據(jù)各種類型的同態(tài)簽名方案所具有的特性判斷其是否能夠適用于以上的應(yīng)用場景.

本文主要描述了同態(tài)簽名方案的基本概念、相關(guān)特性和密碼學(xué)基礎(chǔ),概述了目前同態(tài)簽名方案的研究現(xiàn)狀,分別介紹了各種類型的同態(tài)簽名方案,并給出了各種類型中具有代表性的同態(tài)簽名方案,然后為具體應(yīng)用場景提供合適的同態(tài)簽名方案,最后總結(jié)同態(tài)簽名方案未來的發(fā)展方向.

2 同態(tài)簽名

同態(tài)簽名是具有同態(tài)屬性的一種數(shù)字簽名.隨著近幾年來云計算的發(fā)展,同態(tài)簽名成為了現(xiàn)代密碼學(xué)的研究熱點,并且擁有廣泛的應(yīng)用空間.同態(tài)簽名最初被設(shè)計用于在網(wǎng)絡(luò)編碼中建立身份驗證和解決污染攻擊,它的一些特性可以適用于與云計算相關(guān)的應(yīng)用,比如說電子投票、智能電網(wǎng)和電子健康記錄等.

同態(tài)性(Homomorphism)[14]:設(shè)有兩個同類型的代數(shù)系統(tǒng)〈G1,?〉和〈G2,?〉,集合G1和G2上所對應(yīng)的代數(shù)運算是?和?,f是G1到G2的映射.如果有任意的a,b∈G1滿足:

f(a?b)=f(a)?f(b)

則f是從〈G1,?〉到〈G2,?〉的一個同態(tài)映射,簡稱同態(tài).

同態(tài)簽名允許任意的第三方在沒有簽名私鑰的情況下對已認(rèn)證的數(shù)據(jù)進(jìn)行同態(tài)運算操作生成新數(shù)據(jù),并得到新數(shù)據(jù)的有效簽名.也就是說,假設(shè)?和?是二元運算,簽名者的私鑰是sk,y和y′分別是x和x′的簽名,第三方在不知道私鑰sk的情況下,可以通過計算x?=x?x′,y?=y?y′,得出新數(shù)據(jù)x?的同態(tài)簽名y?[15].

2002年Johnson等人在文獻(xiàn)[2]中提出了同態(tài)簽名的第一個形式化定義,同時作者還指出了文獻(xiàn)中的同態(tài)簽名方案存在的主要問題,并明確了未來工作的研究方向.目前已有的同態(tài)簽名方案主要分為5種類型:線性同態(tài)簽名方案、多項式函數(shù)同態(tài)簽名方案、全同態(tài)簽名方案、同態(tài)聚合簽名方案以及多鑰同態(tài)簽名方案.本節(jié)首先詳細(xì)描述同態(tài)簽名方案的基本概念和安全性定義,然后分析同態(tài)簽名具有的其他相關(guān)特性以及密碼學(xué)基礎(chǔ).

2.1 同態(tài)簽名方案的基本概念

一個完整的同態(tài)簽名方案需要包含一個消息空間M,一個簽名消息空間Y,一個包含所有私鑰的集合K以及一個包含所有公鑰的集合K′[16].同態(tài)簽名方案和傳統(tǒng)的數(shù)字簽名方案定義一樣,也包含三個概率多項式算法:密鑰生成算法Setup,簽名算法Sign和驗證算法Verify.除此之外,同態(tài)簽名方案還引入了一個核心算法Evaluate.

與一般的數(shù)字簽名相比,同態(tài)簽名引入了一些新的參數(shù):(1)整數(shù)N:表示最大的數(shù)據(jù)集大小,即同態(tài)運算函數(shù)可以操作的最大消息數(shù),對應(yīng)于消息空間的維數(shù).(2)同態(tài)運算函數(shù)集合F:定義了同態(tài)簽名方案能夠在簽名數(shù)據(jù)上進(jìn)行的所有可能的計算函數(shù).其中函數(shù)f:M N→M是集合F中的一個元素.(3)索引i:能夠?qū)?shù)據(jù)集(m1,m2,···,m N)∈M中的消息進(jìn)行標(biāo)記跟蹤.(4)標(biāo)簽τ:在進(jìn)行簽名運算的時候,每一個數(shù)據(jù)集都會加上一個標(biāo)簽τ來標(biāo)識區(qū)分不同的數(shù)據(jù)集,標(biāo)簽τ對于同態(tài)簽名的安全性起到重要的作用.

同態(tài)簽名在已有的傳統(tǒng)數(shù)字簽名方案的基礎(chǔ)上引入了新的簽名數(shù)據(jù)計算算法Evaluate:K′×{0,1}λ×F×Y N→Y,該算法是同態(tài)簽名方案的核心部分[16].Evaluate算法允許任何人對簽名數(shù)據(jù)進(jìn)行同態(tài)運算操作,也就是將作用在消息上的函數(shù)轉(zhuǎn)換為作用在簽名上的函數(shù).下面將基于文獻(xiàn)[13]給出同態(tài)簽名方案的形式化定義.

同態(tài)簽名方案是包含以下概率多項式時間算法的元組(Setup,Sign,Verify,Evaluate)[16]:

?Setup(1λ,N):該算法輸入一個安全參數(shù)λ和一個整數(shù)N,輸出一個私鑰k和相應(yīng)的公鑰k′.公

鑰k′決定了消息空間M,簽名空間Y,以及同態(tài)運算函數(shù)f:M N→M的集合F.

?Sign(k,τ,m,i):該算法輸入一個私鑰k,一個標(biāo)簽τ∈{0,1}λ,一個消息m∈M,以及一個索引i∈{1,2,···,N},輸出一個簽名σ∈Y,其中σ由私鑰k計算得出,是標(biāo)簽τ標(biāo)記的數(shù)據(jù)集中的第i個消息m的簽名.

?Verify(k′,τ,m,σ,f):該算法輸入一個公鑰k′,一個標(biāo)簽τ∈{0,1}λ,一個消息m∈M,一個簽名σ∈Y,以及一個函數(shù)f∈F.如果σ是消息m的一個有效的簽名,則輸出1,否則輸出0.

關(guān)于同態(tài)簽名方案的正確性,我們設(shè)一個投射函數(shù)πi:M N→M使得πi(m1,m2,···,m N)→m i,其中πi∈F,i∈{1,2,···,N}.

在給出同態(tài)簽名方案的安全性定義之前,我們首先將敵手A的優(yōu)勢Adv定義為:敵手A查詢了消息m1,m2,···,m N之后,對消息m′/∈span?(m1,m2,···,m N)輸出有效簽名(m′,σ′)的概率,其中計算操作為“*”.

安全性[16]:如果每個敵手A最多進(jìn)行q次選擇消息查詢,運行時間最多為t,并且優(yōu)勢AdvA≤ε,則計算操作為“*”的同態(tài)簽名方案對于存在偽造是(t,q,ε)-安全的.

2.2 同態(tài)簽名方案的一般特性

同態(tài)簽名方案除了具有上述定義的正確性和不可偽造的安全性以外,還擁有其他的一些特性,例如隱私性和可證明安全性理論.除此之外,在某些情況下算法的效率以及簽名的長度也是重要的特性.以上的這些特性都能夠作為評估一個同態(tài)簽名方案的標(biāo)準(zhǔn),我們可以根據(jù)這些特性為具體的實際應(yīng)用提供有效的同態(tài)簽名方案.本節(jié)將對上述的特性進(jìn)行詳細(xì)的討論和定義.

2.2.1 不可偽造性

不可偽造性是同態(tài)簽名方案的基本安全要求之一,同態(tài)簽名方案的不可偽造性安全模型主要包括兩種,一種是Boneh等人的安全定義,其中定義了一個相對較弱的敵手;另外一種則是Freeman的安全定義,其中定義了一個較強(qiáng)的敵手.上述兩種不可偽造性安全模型由敵手(adversary)、挑戰(zhàn)者(challenger)和游戲(game)組成.首先由挑戰(zhàn)者生成密鑰對(k,k′),并發(fā)送公鑰k′給敵手,挑戰(zhàn)者保留私鑰k用來生成簽名.然后敵手可以自適應(yīng)地選擇任意數(shù)據(jù)集,每個數(shù)據(jù)集最多包含N個消息,挑戰(zhàn)者為所選擇的數(shù)據(jù)集隨機(jī)選擇標(biāo)簽τ,并根據(jù)敵手選擇的數(shù)據(jù)集生成對應(yīng)的簽名,然后將標(biāo)簽和簽名返回給敵手.最后,敵手返回一個消息簽名對(m?,σ?),一個同態(tài)運算函數(shù)f和一個標(biāo)簽τ.下面描述關(guān)于不可偽造性的兩個定義.

Boneh等人的安全定義[8]:從上述的同態(tài)簽名方案的基本概念可知,標(biāo)簽τ對于同態(tài)簽名方案的安全要求來說是一個非常重要的參數(shù).這是因為在挑戰(zhàn)者和敵手A之間的博弈中,每個數(shù)據(jù)集都添加了標(biāo)識符τ用于區(qū)分不同的數(shù)據(jù)集,如果沒有了標(biāo)簽τ來標(biāo)識數(shù)據(jù)集,敵手就只能查詢部分消息,而不能查詢整個數(shù)據(jù)集[17].敵手A可以通過兩種不同的偽造行為來獲勝.第一種對應(yīng)于普通數(shù)字簽名偽造的一般概念,敵手生成一個未查詢過的數(shù)據(jù)集m?的偽造簽名σ?.而第二種類型是敵手A生成一個已被查詢過的數(shù)據(jù)集m?的偽造簽名σ?,但是數(shù)據(jù)集m?不等于同態(tài)運算函數(shù)f的消息,即該數(shù)據(jù)集m?能夠驗證其函數(shù)之一的不正確值.接下來將基于文獻(xiàn)[8]簡單描述Boneh等人的安全定義.

如果一個同態(tài)簽名方案S=(Setup,Sign,Verify,Evaluate)對于安全參數(shù)λ以及所有的最大消息數(shù)N,任何的概率多項式時間敵手A贏得下列游戲的概率可以忽略不計,那么同態(tài)簽名方案S是不可偽造的.

?Setup:挑戰(zhàn)者通過運行Setup(1λ,N)生成密鑰對(k,k′),并把公鑰k′給敵手.公鑰k′定義了一個消息空間M,簽名空間Y以及一個同態(tài)運算函數(shù)f:M N→M的集合F.

?Output:敵手A輸出τ?∈{0,1}λ,一個消息m?∈M,一個同態(tài)運算函數(shù)f∈F以及一個簽名σ?∈Y.

如果敵手偽造的簽名滿足以下兩種類型中的一種,并且能夠驗證Verify(k′,τ?,m?,σ?,f)=1,則敵手獲勝.

(1)I型偽造:對于所有的i∈{1,2,···,N},τ??=τi.

(2)II型偽造:對于某個i有τ?=τi,但是m??=f(→m i).

Freeman的安全定義[13]:在2012年由Freeman提出的較強(qiáng)的安全模型中[13],敵手A擁有了更強(qiáng)的能力,不再局限于一次查詢給定數(shù)據(jù)集中的所有消息,而是可以一次查詢一條消息,然后根據(jù)前一個查詢的輸出選擇下一條消息.除此之外,敵手A還可以在每個數(shù)據(jù)集中自適應(yīng)地執(zhí)行此操作,并且還能在不同的數(shù)據(jù)集中分散查詢.也就是說敵手能夠根據(jù)查詢過的數(shù)據(jù)集輸出函數(shù)-消息對(f,m?),以及(f,m?)上的簽名σ?.這一類型的偽造被稱為III型偽造.然而在這一類型中敵手A并不能在給定的數(shù)據(jù)集上查詢足夠的信息來準(zhǔn)確地定義同態(tài)運算函數(shù)f.

2.2.2 隱私性

同態(tài)簽名方案的另外一個基本安全要求是隱私性.隱私性是同態(tài)簽名方案對生成的新簽名的隱私保護(hù).生成的簽名除了被簽名的消息之外,不應(yīng)該泄露其他任何信息.根據(jù)一個方案所能夠達(dá)到的隱私保護(hù)程度,同態(tài)簽名方案的隱私性由弱到強(qiáng)可以分為以下三種不同程度的概念:

?弱上下文隱藏(weakly context hiding)[18]:設(shè)消息m′的簽名σ′是由原始簽名集σ1,σ2,···,σN派生出來的,除了對應(yīng)的消息m′之外,σ′不會泄露上述原始簽名集σ1,σ2,···,σN各自的數(shù)據(jù)集m1,m2,···,m N的信息.

?強(qiáng)上下文隱藏(strong context hiding)[19]:要求即使在原始簽名集σ1,σ2,···,σN公開的情況下也不可能將其與其派生的簽名σ′聯(lián)系起來.

?完全上下文隱藏(completely context hiding)[20]:要求公開私鑰的敵手選擇的簽名能夠隱藏上下文,也就是說一個同態(tài)簽名方案即使在原始簽名是由非法簽名算法生成的情況下仍然具有不可鏈接性.

2.2.3 可證明安全性理論

對于所有的密碼方案,不僅僅是同態(tài)簽名方案,無論是簽名體制還是加密體制都需要經(jīng)過可證明安全性的流程.密碼方案的可證明安全性是指一種歸約的方法,首先需要確定密碼體制的安全目標(biāo),比如加密體制的安全目標(biāo)是信息的機(jī)密性,而簽名體制的安全目標(biāo)是簽名的不可偽造性.然后根據(jù)敵手的能力構(gòu)建一個形式化的安全模型.最后再通過歸約的方法分析敵手能夠成功破解密碼體制的概率[21].密碼方案的安全性證明通常在隨機(jī)預(yù)言機(jī)模型和標(biāo)準(zhǔn)模型中進(jìn)行,前一種是可證明安全性的理想框架,后一種是實際框架.

隨機(jī)預(yù)言機(jī)模型(random oracle model,ROM)的概念起源于1986年Fiat等人把哈希函數(shù)看作是隨機(jī)函數(shù)的思想[22],然后在1993年Bellare等人正式提出了隨機(jī)預(yù)言機(jī)模型的思路框架[23].在隨機(jī)預(yù)言機(jī)模型下,每個哈希函數(shù)都會被一個完全隨機(jī)函數(shù)所替代;相反在方案的實際執(zhí)行時,則會用具體的哈希函數(shù)來替換方案中的隨機(jī)預(yù)言機(jī).因此在隨機(jī)預(yù)言機(jī)模型下證明安全的方案在實際具體實現(xiàn)中未必是安全的,這是因為在隨機(jī)預(yù)言機(jī)模型中,假定敵手不會利用散列函數(shù)的弱點來攻擊密碼學(xué)方案,只是在理想的情況下進(jìn)行安全性證明.

由于一些隨機(jī)預(yù)言機(jī)模型下的密碼方案已經(jīng)被證明是不安全的,學(xué)者們提出了一個更加現(xiàn)實的框架來執(zhí)行證明,稱為標(biāo)準(zhǔn)模型(standard model).該模型不依賴于隨機(jī)預(yù)言機(jī),僅使用了現(xiàn)實中哈希函數(shù)可以實現(xiàn)的特性.由于標(biāo)準(zhǔn)模型可以將密碼學(xué)方案歸約到數(shù)論中的困難問題上,因此在標(biāo)準(zhǔn)模型下的安全證明更加令人信服.然而實際上在標(biāo)準(zhǔn)模型下建立安全性歸約是比較復(fù)雜困難的,而且在標(biāo)準(zhǔn)模型下設(shè)計的密碼算法的效率也沒有在隨機(jī)預(yù)言機(jī)模型下的密碼算法高.由此可見,無論是隨機(jī)預(yù)言機(jī)模型還是標(biāo)準(zhǔn)模型,都具有重大的意義以及廣泛的應(yīng)用.

2.2.4 長度效率

同態(tài)簽名方案由于需要進(jìn)行取冪、乘法以及模運算等復(fù)雜的計算操作,因此會增加處理開銷并影響方案的效率,這是公鑰密碼體系共有的缺點[24].不僅如此,同態(tài)簽名方案在實際應(yīng)用中的效率還可能會受到移動終端計算和存儲能力大小的限制.目前還沒有一個能夠衡量同態(tài)簽名方案效率的標(biāo)準(zhǔn),如何制定一個嚴(yán)格的效率標(biāo)準(zhǔn)仍需要進(jìn)一步的研究.不過對于同態(tài)簽名方案生成簽名的長度,文獻(xiàn)[8]提出了一個長度效率的概念:對于固定的安全參數(shù)λ,如果派生簽名的長度僅對數(shù)地依賴于數(shù)據(jù)集的大小N,那么同態(tài)簽名方案就是長度有效的.

2.3同態(tài)簽名方案的密碼學(xué)基礎(chǔ)

本節(jié)將會簡單地介紹同態(tài)簽名方案的一些密碼學(xué)基礎(chǔ)知識.已有的同態(tài)簽名方案基本上都是基于以下3種密碼學(xué)基礎(chǔ):第一種是建立在雙線性群的Diffie-Hellman問題上;第二種基于RSA問題;第三種基于格上困難問題.Diffie-Hellman問題和RSA問題分別建立在離散對數(shù)和整數(shù)分解問題之上,這兩種問題都已被證明難以抵抗量子攻擊,而格問題卻可以提供抗量子攻擊的特性.以下的密碼學(xué)基礎(chǔ)均為目前難以解決的數(shù)學(xué)困難問題,這里的難以解決是指在概率多項式時間內(nèi)無法以不可忽略的概率求得解.

2.3.1 雙線性群

如果存在一個雙線性映射e:G1×G2→GT,則稱元組(G1,G2,GT,p,e)為雙線性群[25].一些同態(tài)簽名方案都是基于雙線性群的密碼學(xué)基礎(chǔ)之上[26-28],接下來介紹關(guān)于雙線性群的一些常見的密碼學(xué)基礎(chǔ).

?計算性Diffie-Hellman問題(CDH):如果在雙線性群(G1,G2,GT,p,e)中G1=G2=G,則雙線性映射e為:G×G→GT.設(shè)G是一個階為素數(shù)p的循環(huán)群,g是G的生成元,給定元組(g,g a,g b)∈G,計算g ab∈G.

?決策性Diffie-Hellman問題(DDH):如果在雙線性群(G1,G2,GT,p,e)中G1=G2=G,則雙線性映射e為:G×G→GT.設(shè)G是一個階為素數(shù)p的循環(huán)群,g是G的生成元,給定元組(g,g a,g b,g c)∈G,判斷在Zp中c=ab是否為真.

2.3.2 RSA

RSA最早是在1976年由Rivest等人提出的,是目前使用最為廣泛的公鑰密碼體制之一[29].現(xiàn)有的一部分同態(tài)簽名方案是建立在RSA問題之上的[30],它的安全性是基于整數(shù)因式分解的困難性.如果一個整數(shù)N是兩個不同素數(shù)p和q的乘積,那么稱整數(shù)N為RSA模數(shù).1997年Baric等人在RSA問題的基礎(chǔ)上提出了強(qiáng)RSA問題[31].一般來說,給定一個公共的RSA模數(shù)N,以及一個隨機(jī)值z∈Zp,任何概率多項式時間算法都不能計算出z的e次方根,其中e?=1.RSA問題和強(qiáng)RSA問題的區(qū)別在于,后者的指數(shù)e可以根據(jù)z進(jìn)行選擇,而RSA問題中的e是獨立選擇的[30].以下是強(qiáng)RSA問題的定義.

定義1(強(qiáng)RSA問題)給定一個長度為k的整數(shù)N=pq以及一個隨機(jī)元素z∈Zp,其中k∈N為安全參數(shù),p和q為不同的素數(shù).對于任何概率多項式時間算法E,概率

Pr[(y,e)←A(N,z):y e=zmodN∧e?=1]

可以忽略不計.

2.3.3 格

近年來,基于格的密碼系統(tǒng)由于其在量子計算機(jī)的上的安全性而成為了密碼學(xué)的研究熱點.格密碼學(xué)基礎(chǔ)能夠提供雙線性群和RSA問題都沒有的抗量子攻擊特性,因此學(xué)者們提出了許多基于格的同態(tài)簽名方案[18,32].接下來介紹同態(tài)簽名方案中的關(guān)于格的密碼學(xué)基礎(chǔ).

3 同態(tài)簽名方案的類型及研究現(xiàn)狀

同態(tài)簽名的概念自提出以來,就引起了密碼學(xué)家的廣泛關(guān)注,在經(jīng)過了十多年的研究與發(fā)展之后,誕生了許多不同類型的同態(tài)簽名方案,其中按照不同的同態(tài)運算操作可以分為線性同態(tài)簽名、多項式函數(shù)同態(tài)簽名和全同態(tài)簽名.以往的同態(tài)簽名方案都是假定每個輸入的簽名數(shù)據(jù)使用相同的私鑰生成的,因此只適用于單用戶的場景.為了能夠在多用戶的場景下提供有效的解決方案,密碼學(xué)家們還提出了具有聚合屬性的同態(tài)聚合簽名方案,以及在密鑰空間中也具有同態(tài)屬性的多鑰同態(tài)簽名方案.本節(jié)將會介紹各種類型的同態(tài)簽名方案的相關(guān)概念以及研究現(xiàn)狀.

3.1 線性同態(tài)簽名方案

線性同態(tài)簽名允許在簽名數(shù)據(jù)上進(jìn)行線性計算操作.最早的同態(tài)簽名方案是線性的,當(dāng)時是為了在網(wǎng)絡(luò)編碼中建立身份驗證以及解決污染問題而提出了一些線性同態(tài)簽名方案[3,6,34,35],利用網(wǎng)絡(luò)編碼中數(shù)據(jù)包的線性特性,方便有效地檢查接收到數(shù)據(jù)包的完整性,但是這些線性同態(tài)簽名方案都已經(jīng)被證明是不安全和不實用的.直到2009年Boneh等人提出了一個線性同態(tài)簽名方案[26],該方案可以看作是線性同態(tài)簽名方案的里程碑.在這項工作中給出了第一個線性同態(tài)簽名方案的形式化定義,并且定義了弱對手的概念.在他們的方案中,數(shù)據(jù)包被視為素數(shù)域上的線性向量空間,對接收到的向量進(jìn)行修改可以看作是具有某些整數(shù)系數(shù)的向量的線性組合.也就是說,該方案實際上是對線性子空間進(jìn)行簽名,從向量子空間V上的簽名σ可以精確驗證V中的向量.此外,每個節(jié)點都可以驗證數(shù)據(jù)包的真實性并為新的有效數(shù)據(jù)包創(chuàng)建有效簽名.并且他們在隨機(jī)預(yù)言模型中證明了基于co-CDH假設(shè)的方案是安全的.在隨后的幾年中,學(xué)者們提出了大量的線性同態(tài)簽名方案,這些方案在效率、安全性和隱私性方面得到了進(jìn)一步改進(jìn).

2010年Gennaro等人提出了一個基于RSA困難問題的線性同態(tài)簽名方案[5],并證明了該方案在隨機(jī)預(yù)言模型中的可證明安全性.該方案基于整數(shù)分解的困難問題,使得其效率比文獻(xiàn)[26]中基于雙線性群的線性同態(tài)簽名方案更高.由于可以選擇較小的整數(shù)系數(shù)來實現(xiàn)線性組合,因此大大減少了計算開銷并提高了計算效率,能夠在合理的時間內(nèi)運行,并且該方案也是當(dāng)時計算復(fù)雜度最低的方案.

除了基于雙線性群和RSA假設(shè)的線性同態(tài)簽名方案之外,為了能夠提供抵抗量子攻擊的特性,2011年Boneh等人提出了第一個基于格的線性同態(tài)簽名方案[18],是在二進(jìn)制域上對向量進(jìn)行驗證的方案.方案的安全性是基于k-SIS困難問題,這是他們首次提出的一個新的關(guān)于格的困難問題.由于方案是在格困難問題上建立的,因此可能沒有文獻(xiàn)[5]中基于RSA困難問題的方案那么高效.2013年Wang等人對第一個基于格的困難問題構(gòu)造的線性同態(tài)簽名方案進(jìn)行了改進(jìn)[32].該方案的線性同態(tài)是通過使用基于格的哈希函數(shù)的同態(tài)來實現(xiàn)的.與2011年提出的線性同態(tài)簽名方案相比,該方案在公鑰大小、簽名長度和計算效率上具有一定的優(yōu)勢.

2018年Lin等人對線性同態(tài)簽名進(jìn)行了推廣,引入了基于身份的簽名技術(shù),構(gòu)造出了基于身份的線性同態(tài)簽名方案[36].由于添加了基于身份的特性,因此避免了使用公鑰證書的缺點.該方案的安全性基于雙線性群的計算性Diffie-Hellman問題(CDH),在隨機(jī)預(yù)言機(jī)模型下被證明可以防止自適應(yīng)選擇消息的存在偽造和ID攻擊.基于身份的線性同態(tài)簽名方案可以適用于電子商務(wù)和云計算,并且還能在區(qū)塊鏈中實現(xiàn)身份驗證.

上述線性同態(tài)簽名方案都是基于隨機(jī)預(yù)言模型的,2011年Attrapadung和Libert提出了第一個在標(biāo)準(zhǔn)模型之下具有可證明安全的線性同態(tài)簽名方案[37].他們的方案是在復(fù)合階數(shù)N的雙線性群上建立的,其中線性組合系數(shù)和向量坐標(biāo)都屬于ZN,而不是素數(shù)域.并且該方案允許對單個向量進(jìn)行動態(tài)簽名,簽名的長度是恒定不變的.然而與在隨機(jī)預(yù)言模型中構(gòu)造的方案相比,該方案效率相對較低.在2012年Attrapadung和Libert對他們提出的方案做出了進(jìn)一步的改進(jìn)[20],修改了方案的復(fù)雜性假設(shè),所考慮的雙線性群(G,GT)的復(fù)合階數(shù)為p=p1p2p3.修改后的方案與之前的方案相比,簽名的長度更短,效率更高.

自從2011年Attrapadung等人提出了標(biāo)準(zhǔn)模型下的線性同態(tài)簽名方案之后,隨后幾年里逐漸出現(xiàn)了一些安全性基于RSA假設(shè)或者Diffie-Hellman假設(shè)的標(biāo)準(zhǔn)模型下的線性同態(tài)簽名方案.然而當(dāng)時還沒有基于格困難問題的標(biāo)準(zhǔn)模型下的線性同態(tài)簽名方案,在2016年Chen等人針對這一方向進(jìn)行了深入研究,構(gòu)造出了標(biāo)準(zhǔn)模型下的第一個基于格困難問題的線性同態(tài)簽名方案[38].Chen等人在這項工作中利用了修剪樹的技術(shù)[39]與文獻(xiàn)[8]中提出的兩個整數(shù)格的交集法相結(jié)合,在標(biāo)準(zhǔn)模型下構(gòu)造了基于SIS問題的線性同態(tài)簽名方案.該方案已被證明能夠?qū)谷鯏呈?并且能夠提供弱上下文隱藏的隱私性.

Chen等人提出的線性同態(tài)簽名方案的公鑰是由O(l)個矩陣與O(k)個向量組成,其中l(wèi)是文件標(biāo)簽的長度,k是最大數(shù)據(jù)集的大小.而在2020年由Lin等人提出的標(biāo)準(zhǔn)模型下基于格的線性同態(tài)簽名方案具有相對較短的公鑰[40],由O(1)個矩陣與O(k)個向量組成,方案的安全性依賴于SIS困難問題并且能夠?qū)谷鯏呈?在這項工作中Lin等人構(gòu)造了兩個能夠在有限域上對向量進(jìn)行驗證的線性同態(tài)簽名方案.他們首先在標(biāo)準(zhǔn)模型下構(gòu)造了一個基于滿秩差分散列函數(shù)且滿足選擇性安全的線性同態(tài)簽名方案,接著修改了文獻(xiàn)[39]中的變色龍散列函數(shù)得到一個線性同態(tài)變色龍散列函數(shù)(LHCHF),并將其應(yīng)用于具有選擇性安全的線性同態(tài)簽名方案當(dāng)中,轉(zhuǎn)換為完全安全的線性同態(tài)簽名方案.這兩種方案都可以用來對多個文件進(jìn)行簽名,并且具有相對較短的公鑰.

2017年Lin等人提出了第一個帶有指定實體的線性同態(tài)簽名方案[7],該方案是受到了2000年Rivest提出的指定實體的傳遞簽名開放問題的啟發(fā).與其他線性同態(tài)簽名方案不相同,在這個方案中只有一個實體(指定的操作者)可以執(zhí)行同態(tài)運算,并且只有一個實體(指定的驗證者)可以對同態(tài)簽名進(jìn)行驗證.Lin等人在這項工作中給出了該方案的正式定義以及相關(guān)的安全要求,分別在雙線性群上的co-Bilinear Diffie-Hellman假設(shè)和Gap Bilinear Diffie-Hellman假設(shè)實例化了指定實體的線性同態(tài)簽名方案,并在隨機(jī)預(yù)言模型下證明了方案的安全性.

3.2 多項式函數(shù)同態(tài)簽名方案

多項式函數(shù)同態(tài)簽名允許在簽名數(shù)據(jù)上使用多項式函數(shù),多項式函數(shù)是多變量和次數(shù)有界的,而線性函數(shù)是一次多項式,因此多項式同態(tài)簽名可以看作是線性同態(tài)簽名的推廣.

2011年Boneh和Freeman構(gòu)造了第一個多項式函數(shù)同態(tài)簽名方案[8].他們提出的方案使用了Gentry、Peikert和Vaikuntanathan的原像采樣算法[33],定義在理想格上,基于SIS困難問題構(gòu)造,能夠?qū)σ押灻臄?shù)據(jù)進(jìn)行多元有界多項式運算,安全性在隨機(jī)預(yù)言模型中得到證明.只要給定公鑰和簽名數(shù)據(jù)集,該方案就可以在簽名數(shù)據(jù)的平均值、標(biāo)準(zhǔn)偏差等其他統(tǒng)計數(shù)據(jù)上生成同態(tài)簽名.并且對于次數(shù)為常數(shù)的多項式,同態(tài)簽名的長度與數(shù)據(jù)集的大小成對數(shù)關(guān)系.然而該方案的隱私保護(hù)水平尚不清楚.2013年Hiromasa對文獻(xiàn)[8]中的方案進(jìn)行了改進(jìn),提出了簽名長度更短的多項式函數(shù)同態(tài)簽名方案[41],該方案使用Micciancio和Peikert的算法[42]替代了Gentry、Peikert和Vaikuntanathan的原像采樣算法,Micciancio和Peikert的算法比Gentry等人的原像采樣算法更加有效,采樣的原像更小.這也使得改進(jìn)后的多項式函數(shù)同態(tài)簽名方案不僅簽名長度更短,而且效率更高.

上述的兩個多項式函數(shù)同態(tài)簽名方案的安全性都是在隨機(jī)預(yù)言模型中得到證明的.為了不再依賴于隨機(jī)預(yù)言模型,2014年Catalano等人構(gòu)造了第一個標(biāo)準(zhǔn)模型下的多項式同態(tài)簽名方案[43].除此之外,該方案能夠面對更強(qiáng)的敵手,并且簽名驗證的效率更高.方案的安全性依賴于k-augmented power multilinear Diffie-Hellman(k-APMDHP)假設(shè),這是作者首次提出的困難問題.該方案還存在一定的缺點,為了達(dá)到比文獻(xiàn)[8,41]中方案更好的安全級別,需要付出更大的計算開銷,而且也沒有實現(xiàn)任何程度的隱私性.

3.3 全同態(tài)簽名方案

2009年,Gentry構(gòu)造了第一個全同態(tài)加密方案[44],隨后全同態(tài)加密體制吸引密碼學(xué)家們的廣泛關(guān)注,其中不少密碼學(xué)者開始了對全同態(tài)簽名的研究.層次型全同態(tài)簽名不再對作用在簽名數(shù)據(jù)上的函數(shù)進(jìn)行限制,而是允許對簽名數(shù)據(jù)進(jìn)行任意電路運算,該電路具有一定的尺寸和深度d.

2014年Gorbunov等人提出了第一個層次型全同態(tài)簽名方案[9].該方案可以對已簽名的數(shù)據(jù)進(jìn)行任意電路的運算,電路的最大深度d是一個先驗值,同態(tài)簽名的長度與d呈多項式關(guān)系,但與電路大小和數(shù)據(jù)大小無關(guān).Gorbunov等人在這項工作中引入了同態(tài)陷門函數(shù)(HTDF)的新概念,該概念可由同態(tài)加密與簽名結(jié)合在一起實現(xiàn).方案的不可偽造性基于SIS困難問題,并且能夠在標(biāo)準(zhǔn)模型下證明方案的安全性.除此之外該方案還能對抗弱敵手以及提供弱上下文隱藏的隱私特性.

在與文獻(xiàn)[9]的一項并行工作中,Boyen等人提出了第二個層次型全同態(tài)簽名方案[45],該方案也是基于格上困難問題構(gòu)造的,并且對于兩種不同的電路類型還具有不同的實例:令λ為安全參數(shù),當(dāng)電路深度d為λ的對數(shù)的多項式(polylog(λ))時,方案能夠在SIS困難問題下實現(xiàn)了自適應(yīng)安全性;而當(dāng)電路深度d為λ的多項式(poly(λ))時,方案的自適應(yīng)安全性則依賴于次指數(shù)SIS困難問題.相對于Gorbunov等人提出的層次型全同態(tài)簽名方案,該方案不僅在效率方面得到了提高,而且能夠?qū)馆^強(qiáng)的敵手,但是該方案沒能實現(xiàn)任何程度的隱私性安全.

Gorbunov等人提出了同態(tài)陷門函數(shù)(HTDF)的新概念以及構(gòu)造了第一個層次型全同態(tài)簽名方案之后,2015年Wang等人將同態(tài)陷門函數(shù)的概念與基于身份的特性相結(jié)合,提出了基于身份的同態(tài)陷門函數(shù)(IBHTDF),并利用其構(gòu)造了第一個基于身份的層次型全同態(tài)簽名方案(IBFHS)[46].基于身份的同態(tài)陷門函數(shù)(IBHTDF)具有無爪(claw-free)的函數(shù)對,可以提供抗碰撞的特性,使得基于SIS困難問題的IBFHS具有強(qiáng)不可偽造性,能夠?qū)馆^強(qiáng)的敵手.Wang等人還使用了巴林頓定理(Barrington’s Theorem)來減少參數(shù)的大小,與文獻(xiàn)[9]中的層次型全同態(tài)簽名方案相比,最大噪聲水平大致從O(m dβ)降低到O(4d mβ),這也將會使得當(dāng)電路的最大深度d=O(logλ)時,模數(shù)q=poly(λ),其中λ是安全參數(shù).該方案的一個缺點是公共參數(shù)仍然比較大,如何構(gòu)造非層次的IBFHS或者具有較小公共參數(shù)的IBFHS可以作為后期的研究方向.

而在2020年最新的一項工作中,Wang等人對上述的基于身份的同態(tài)陷門函數(shù)(IBHTDF)進(jìn)行了改造,提出了新的同態(tài)運算算法,構(gòu)造了新的基于身份的層次型全同態(tài)簽名方案(IBFHS)[47].在該同態(tài)運算算法中乘法門電路的噪聲水平與加法門電路的噪聲水平相同,這意味著新的IBHTDF的最大噪聲水平是最理想的,因此使得新的IBFHS的噪聲水平進(jìn)一步從O(4d mβ)降低到O(2dβ).

3.4 同態(tài)聚合簽名方案

上述同態(tài)簽名方案都是在單源網(wǎng)絡(luò)或者單用戶的場景下構(gòu)造的,算法中所有輸入的簽名都是使用相同的私鑰產(chǎn)生的.在現(xiàn)實生活中,有很多應(yīng)用場景都是具有多源網(wǎng)絡(luò)或者多用戶的.在這些場景中,生成的新簽名是由不同消息對應(yīng)的簽名聚合得到的,這些消息由不同的用戶進(jìn)行簽名,每個用戶有各自的私鑰,對于這些場景則可以使用聚合簽名方案.但是如果想要對已經(jīng)聚合的簽名數(shù)據(jù)進(jìn)行計算操作,上述所有的簽名方案都不能提供有效的解決方案,于是在聚合簽名方案的基礎(chǔ)上引入了同態(tài)屬性,構(gòu)造出同態(tài)聚合簽名方案[10],滿足了以上的要求.在3.4.1節(jié)中,首先提供聚合簽名的基本概念,然后在3.4.2節(jié)中給出同態(tài)聚合簽名的基本概念.

3.4.1 聚合簽名

聚合簽名最先是由Boneh等人提出的[48].聚合簽名方案是一種具有聚合屬性的數(shù)字簽名方案,聚合簽名方案可以將N個不同的簽名聚合成一個新的簽名,這N個不同的簽名由N個不同的用戶使用各自的私鑰產(chǎn)生.新簽名可以作為所有N個消息的一個簽名,并且和單個的原始簽名一樣長.此外,聚合而成的新簽名是具有增量特性的.也就是說,給定簽名σ1,σ2聚合得到簽名σ12,然后σ12可以進(jìn)一步聚合σ3得到簽名σ123,這樣我們就避免了對簽名σ1,σ2,σ3重新進(jìn)行聚合.

3.4.2 同態(tài)聚合簽名

同態(tài)簽名方案使用同態(tài)運算函數(shù)對單個用戶不同消息的簽名進(jìn)行計算操作,而聚合簽名方案只能對不同用戶的簽名進(jìn)行聚合卻不能進(jìn)行計算操作.實際上,為了保證多源網(wǎng)絡(luò)編碼的安全性和多用戶網(wǎng)絡(luò)數(shù)據(jù)的安全聚合,需要一個同時具有同態(tài)屬性和聚合屬性的簽名方案[10],因此構(gòu)造同態(tài)聚合簽名方案是一件非常有價值的研究.

下面給出同態(tài)聚合簽名的正式定義.

同態(tài)聚合簽名方案是包含以下概率多項式時間算法的元組(Setup,Sign,Verify,Aggm,Aggσ):

當(dāng)驗證單個簽名時,對于聚合簽名方案的Verify算法,只需要輸入一個公鑰,而不是N個公鑰.

目前現(xiàn)有的同態(tài)聚合簽名方案都是線性同態(tài)聚合簽名方案,即對來自不同用戶的簽名數(shù)據(jù)進(jìn)行線性組合計算,文獻(xiàn)[10]和文獻(xiàn)[49]先后給出了不同的線性同態(tài)聚合簽名方案.為了給多元網(wǎng)絡(luò)編碼和傳感器數(shù)據(jù)聚合提供解決方案,2012年Zhang等人構(gòu)造了第一個同態(tài)聚合簽名方案[10],他們的方案支持對二進(jìn)制域的線性運算,安全性依賴于格的ISIS問題.該方案與其他的基于格的同態(tài)簽名方案相比,由于主要使用模的加法以及模的乘法運算,因此效率相對較高.2014年Jing對文獻(xiàn)[18]中提出的線性同態(tài)簽名方案進(jìn)行了改進(jìn),添加了聚合屬性,構(gòu)造出了第二個同態(tài)聚合簽名方案[49],該方案也是支持對二進(jìn)制域的線性運算,不同的是其安全性是基于格的SIS問題,能夠提供弱上下文隱藏的隱私特性,并且具有較短的簽名長度和較高的效率.上述兩個同態(tài)聚合簽名方案都能夠?qū)箯?qiáng)的敵手,而且都是在隨機(jī)預(yù)言模型下證明了安全性.

3.5 多鑰同態(tài)簽名方案

以上提到的各種類型的同態(tài)簽名方案都存在有一個局限:同態(tài)性只在消息空間中存在.而在密鑰同態(tài)加密方案的研究背景之下[50],密碼學(xué)者開始對多密鑰場景下的同態(tài)簽名方案進(jìn)行研究,構(gòu)造出了多鑰同態(tài)簽名方案.多鑰同態(tài)簽名方案允許對由不同密鑰生成的簽名進(jìn)行同態(tài)運算,除了在消息空間具有同態(tài)性之外,還在簽名方案中引入了密鑰同態(tài)的特性,從而產(chǎn)生了多鑰密鑰同態(tài)簽名(M-KHS)的概念.

以下是多鑰同態(tài)簽名方案與同態(tài)簽名方案之間的一些差異:(1)Setup算法輸出一個公共的參數(shù)pp,該參數(shù)隱式輸入到所有算法中.(2)密鑰生成算法KGen輸入公共參數(shù)pp,輸出公鑰pk和秘鑰sk.(3)簽名算法Sign輸出的是一組簽名Σ.(4)同態(tài)運算算法Evaluate輸出一個簽名σ,σ是對在組合公鑰pk=g(pk1,pk2,···,pkK)和組合標(biāo)簽τ=g(τ1,τ2,···,τK)下的消息數(shù)據(jù)m=g(M1,M2,···,M K)的簽名.

下面給出多鑰同態(tài)簽名方案的正式定義:

?Setup(1λ):該算法輸入一個安全參數(shù)λ,輸出一個公共參數(shù)pp,該參數(shù)定義了消息空間M和包含標(biāo)識函數(shù)id:M→M的函數(shù)族G.

?KGen(pp):該算法輸入公共參數(shù)pp.輸出公鑰pk和秘鑰sk.

?Sign(sk,τ,M):該算法輸入一個私鑰sk,一個標(biāo)簽τ∈{0,1}?和一組消息M∈M?.輸出一組簽名Σ.

?

Verify(pk,τ,m,σ,g):該算法輸入一個公鑰pk,一個標(biāo)簽τ,一個簽名σ,一個消息m∈M和一

個同態(tài)運算函數(shù)g∈G.如果σ是消息m的一個有效的簽名,則輸出1,否則輸出0.

2016年Fiore等人在受到單用戶場景下的同態(tài)認(rèn)證的啟發(fā)下[51],定義了多鑰同態(tài)認(rèn)證的概念,構(gòu)造了一種基于標(biāo)準(zhǔn)格的多鑰同態(tài)簽名方案,該方案支持多項式深度的布爾電路同態(tài)運算,安全性基于標(biāo)準(zhǔn)格上的SIS問題.此外這項工作還提出了基于偽隨機(jī)函數(shù)和支持低階算術(shù)電路的多密鑰同態(tài)消息認(rèn)證碼(MAC)方案,盡管該方案只支持表達(dá)能力較弱的計算,并且只能進(jìn)行秘密驗證,但還是具有簡單高效的特性.

Boneh等人在2014年使用了一種完全密鑰同態(tài)加密的機(jī)制構(gòu)造了基于屬性的短密鑰加密系統(tǒng)[50],受到該項工作的啟發(fā),2016年Lai等人從自適應(yīng)零知識的簡潔非交互式知識證明(ZK-SNARK)以及其他標(biāo)準(zhǔn)假設(shè)出發(fā),引入了密鑰同態(tài)的特性[11].他們以多密鑰同態(tài)簽名(M-HS)作為中心概念,研究了其他多密鑰的擴(kuò)展,比如多鑰分層同態(tài)簽名(M-HiHS)和多鑰消息同態(tài)簽名(M-KMHS),以及多鑰密鑰同態(tài)簽名(M-KHS)的概念.該項工作還根據(jù)標(biāo)準(zhǔn)假設(shè)構(gòu)造了第一個層次密鑰全同態(tài)簽名方案(leveled fully KHS)以及第一個分布式的基于屬性的簽名方案(D-ABS),并且在此項工作中提出的多鑰同態(tài)簽名方案可以與現(xiàn)有的多密鑰同態(tài)加密方案一起使用,以實現(xiàn)可驗證的安全多方計算.

文獻(xiàn)[51]中提出的多鑰同態(tài)簽名方案存在著一種局限,該方案的不可偽造性是在假定所有簽名者都是誠實的情況下證明的.2018年Lai等人針對這一局限,從零知識的簡潔非交互式知識證明(ZK-SNARK)以及其他標(biāo)準(zhǔn)假設(shè)出發(fā),提出了在內(nèi)部腐敗下不可偽造的多鑰同態(tài)簽名方案[52],并且證明了該方案的存在意味著零知識的簡潔非交互式知識證明(ZK-SNARK)的存在.但是該方案如果在標(biāo)準(zhǔn)假設(shè)中存在腐敗簽名人的情況下,不能確定其真實性和實用性能夠達(dá)到什么樣的程度.

2019年Aranha等人將文獻(xiàn)[26]中的線性同態(tài)簽名方案推廣至多密鑰版本中,構(gòu)造出了多鑰線性同態(tài)簽名方案(MKLHS)[53],方案的安全性依賴于雙線性群的co-Computational Diffie-Hellman(co-CDH)問題,在隨機(jī)預(yù)言模型下得到證明.他們的方案縮短了多鑰同態(tài)簽名方案中大多數(shù)操作的執(zhí)行時間.與現(xiàn)有的多鑰同態(tài)簽名方案相比,該方案的構(gòu)造更加直接簡單,性能更高,并且生成的簽名明顯更短.

4 代表性方案以及具體應(yīng)用場景

前幾節(jié)中討論了方案的隱私性、不可偽造性、安全證明模型以及簽名的長度效率,給出了各種方案所依賴的密碼學(xué)基礎(chǔ),詳細(xì)描述了5種類型的同態(tài)簽名方案的基本概念與研究現(xiàn)狀.接下來本節(jié)將會為線性同態(tài)簽名方案、多項式函數(shù)同態(tài)簽名方案、全同態(tài)簽名方案、同態(tài)聚合簽名方案以及多鑰同態(tài)簽名方案分別選取一個具體的代表性方案介紹上述5類同態(tài)簽名方案的設(shè)計思路,分析這些方案所提供的特性.最后描述了可以使用同態(tài)簽名方案的具體應(yīng)用場景以及同態(tài)簽名方案需要滿足的要求,并對各類同態(tài)簽名方案的特性進(jìn)行比較,提供合適的同態(tài)簽名方案.

4.1 基于雙線性群的線性同態(tài)簽名方案

4.1.1 方案描述

Boneh等人在2009年提出了第一個線性同態(tài)簽名的形式化定義[26],這項工作是線性同態(tài)簽名的里程碑.該方案可以看作是在網(wǎng)絡(luò)編碼中對線性子空間的簽名,即子空間V中的簽名σ準(zhǔn)確地驗證了V中的某些向量,并且安全性依賴于雙線性群中的計算性Diffie-Hellman問題(CDH).基于雙線性群的線性同態(tài)簽名方案描述如下:

4.1.2 特性分析

該方案首次定義了弱對手的概念,依賴于雙線性群(G1,G2)中的co-CDH困難問題,可證明安全性基于隨機(jī)預(yù)言模型.因為公鑰和簽名的大小獨立于數(shù)據(jù)集的大小,所以具有較低的通信開銷[17].除此之外,作者還證明了線性子空間中的簽名長度的一個下界,表明了該方案在簽名長度這方面本質(zhì)上是最優(yōu)的.但是,由于方案定義在雙線性群上,因此在驗證每個簽名的時候需要付出比較大的代價[54],并且只能對抗相對較弱的敵手.盡管如此,方案在隱私性方面還是能夠達(dá)到完全上下文隱藏的隱私性[55].

4.2 基于格的多項式函數(shù)同態(tài)簽名方案

4.2.1 方案描述

由于不滿足以往的方案只能在簽名數(shù)據(jù)上進(jìn)行線性計算,Boneh和Freeman在2011年利用Gentry、Peikert和Vaikuntanathan的原像采樣算法構(gòu)造了第一個能夠在簽名數(shù)據(jù)上支持多元多項式運算的同態(tài)簽名方案[8].給定公鑰和簽名數(shù)據(jù)集,該方案就可以對簽名數(shù)據(jù)的平均值、標(biāo)準(zhǔn)差和其他統(tǒng)計信息生成簽名.并且該方案的安全性依賴于理想格上的困難問題,能夠有效抵抗量子計算機(jī)的攻擊.基于格的多項式函數(shù)同態(tài)簽名方案描述如下:

(b)Sign(sk,τ,m,i):輸入私鑰sk,一個標(biāo)簽τ∈{0,1}λ,一個消息m∈Fp和一個索引i.計算αi:=H(τ‖i)∈Fq,計算h=h(x)∈R使得h(a)modp=m和h(b)modq=αi.通過原像采樣算法SamplePre(p·q,T,h,v)輸出一個簽名σ∈(p·q)+h.

4.2.2 特性分析

該方案是第一個支持在簽名數(shù)據(jù)上使用多項式函數(shù)的同態(tài)簽名,方案的安全性依賴于理想格上的SIS困難問題,能夠在隨機(jī)預(yù)言機(jī)模型下證明安全性.此外,該方案還首次給出了簽名長度效率的定義,即簽名的長度對數(shù)地依賴于數(shù)據(jù)集的大小.但是該方案效率并不高,只能對抗相對較弱的敵手,而且方案的隱私性所達(dá)到的隱私保護(hù)程度還有待明確.

4.3 基于格的層次型全同態(tài)簽名方案

4.3.1 方案描述

Boyen等人在2014年提出了基于格的層次型全同態(tài)簽名方案[45],這是第二個全同態(tài)簽名方案,第一個是同年由Gorbunov等人提出的基于格的層次型全同態(tài)簽名方案[9].這兩個方案都能夠在簽名數(shù)據(jù)上進(jìn)行任意電路運算.文獻(xiàn)[45]中的方案描述如下:

4.3.2 特性分析

該方案是基于格上困難問題構(gòu)造的,即便在量子計算機(jī)攻擊的情況下也保證其安全性,并且可以在簽名數(shù)據(jù)上進(jìn)行任意電路的運算.對于多重對數(shù)深度電路,該方案在標(biāo)準(zhǔn)短整數(shù)解(SIS)問題下實現(xiàn)了自適應(yīng)安全性.對于多項式深度的電路,方案的安全性依賴于次指數(shù)SIS問題.雖然沒有對簽名的長度進(jìn)行討論,但相對于第一個提出的基于格的層次型全同態(tài)簽名方案[9],效率得到了明顯提高,可證明安全基于標(biāo)準(zhǔn)模型,并且最重要的一個改進(jìn)是該方案可以應(yīng)對相對較強(qiáng)的敵手.但是該方案目前還不能實現(xiàn)任何程度的隱私性,因此不適用于對隱私保護(hù)有要求的實際應(yīng)用.

4.4 基于格的同態(tài)聚合簽名方案

4.4.1 方案描述

在許多實際應(yīng)用中,可能需要聚合由不同用戶在不同消息上生成的簽名,但是同態(tài)簽名方案不能夠提供有效的解決方案,而聚合簽名方案[48]能夠應(yīng)對這種多用戶的情況.然而又為了能夠在聚合簽名上進(jìn)行運算操作,于是將同態(tài)屬性添加到聚合簽名方案中,從而構(gòu)造出同態(tài)聚合簽名方案.2014年Jing等人就提出了基于格的同態(tài)聚合簽名方案[49],方案的描述如下:

4.4.2 特性分析

該方案是第二個同態(tài)聚合簽名方案,第一個是由Zhang等人在2012年提出的[10].這兩個方案都支持在二進(jìn)制域上進(jìn)行線性操作,并且都是基于格問題構(gòu)造的,文獻(xiàn)[10]依賴的是ISIS問題,而文獻(xiàn)[49]則依賴于SIS問題,因此都可以抵抗量子計算機(jī)的攻擊.兩個簽名方案都是在隨機(jī)預(yù)言機(jī)模型中被證明能夠應(yīng)對相對較強(qiáng)的敵手.相對于第一個同態(tài)聚合簽名方案,第二個在效率、簽名長度以及隱私性方面都要更優(yōu).實際上,第二個同態(tài)聚合簽名方案可以看作是文獻(xiàn)[18]中提出的線性同態(tài)簽名方案的一個適用于多用戶的變體,它能夠提供第一個同態(tài)聚合簽名方案沒有的弱上下文隱藏特性.

4.5 基于雙線性群的多鑰線性同態(tài)簽名方案

4.5.1 方案描述

現(xiàn)有的多鑰同態(tài)簽名方案構(gòu)造主要包括基于格問題的方案[51]、基于零知識的簡潔非交互式知識證明(ZK-SNARK)的方案[52],或者是利用Matrioska編譯器將單鑰同態(tài)簽名方案轉(zhuǎn)化為多鑰同態(tài)簽名方案[56].而Aranha等人在多鑰同態(tài)簽名中引入了線性同態(tài)簽名的概念,提出了多鑰線性同態(tài)簽名方案(MKLHS)[53].并且他們在128位的安全級別上,使用了兩組參數(shù)在橢圓曲線上的配對來實現(xiàn)多鑰線性同態(tài)簽名方案.Aranha等人提出的多鑰線性同態(tài)簽名方案是目前性能最好、簽名最短的多鑰同態(tài)簽名方案,方案的描述如下:

4.5.2 特性分析

該方案的安全性基于雙線性群的co-Computational Diffie-Hellman(co-CDH)問題,很好地適應(yīng)了非對稱配對,安全性在隨機(jī)預(yù)言模型下得到證明.與現(xiàn)有的多鑰同態(tài)簽名方案相比,該方案的結(jié)構(gòu)更加簡單,性能更高,生成的簽名明顯更短,并且能夠?qū)箯?qiáng)敵手,然而缺點是不具有隱私性.

4.6 具體應(yīng)用場景

上述5個不同類型的代表性同態(tài)簽名方案都具有各自的優(yōu)良特性,總結(jié)見表1.其中N表示數(shù)據(jù)集的最大值,d表示為電路函數(shù)的深度.本節(jié)描述同態(tài)簽名方案適用的三個云計算應(yīng)用場景:電子投票、智能電網(wǎng)和電子健康記錄,并根據(jù)表1對各個方案進(jìn)行比較,提供滿足要求的同態(tài)簽名方案.

表1 代表性方案的比較Table 1 Comparison of representative schemes

4.6.1 電子投票

電子投票是建立在網(wǎng)絡(luò)投票系統(tǒng)上的選舉活動,結(jié)果完全由程序輸出,無需人工參與,具有高效率、便捷、成本較低和不易出錯等優(yōu)點,適用于投票人數(shù)較多的選舉.一般來說,電子投票系統(tǒng)需要滿足安全性和隱私性(在匿名投票的情況下)等要求,如果系統(tǒng)的安全性能不夠強(qiáng),則會遭到黑客的攻擊,對投票結(jié)果進(jìn)行篡改以及泄露投票人的隱私.因此安全性和隱私性是設(shè)計電子投票系統(tǒng)過程中優(yōu)先考慮的重點.由此可得同態(tài)簽名方案需要能夠?qū)瓜鄬^弱及以上級別的敵手.在隱私性方面,同態(tài)簽名方案只需要不把選票簽名對應(yīng)的投票者的消息泄露出去,也就是說達(dá)到弱上下文隱藏的隱私特性就足夠了.如果只是對加密的選票進(jìn)行簽名,那么就可以不考慮同態(tài)簽名方案的隱私性.對于電子投票系統(tǒng)來說,只要能夠保證驗票計票的準(zhǔn)確性,效率相對來說并不顯得那么重要.在投票的結(jié)果公布之后,數(shù)據(jù)就沒必要進(jìn)行長期保存,投票的真實性也不需要長期進(jìn)行保護(hù),因此簽名的長度效率也可以忽略,使用的簽名方案只需要基于整數(shù)分解問題或者離散對數(shù)問題即可[16].在投票的過程中,一般投票者在投票之后不會收到任何的反饋,簽名的選票也不會在投票結(jié)束之前公布,在這種情況下選票簽名有可能會被偽造,投票者對選票進(jìn)行簽名過程中具有兩種不同的情況,一種是所有的選票都用相同的私鑰進(jìn)行簽名,另外一種則是利用不同投票者的私鑰對一個或者一組選票進(jìn)行簽名.如果是第一種情況那么只需要具有同態(tài)屬性的簽名方案,而第二種則需要同態(tài)聚合簽名方案或者多鑰同態(tài)簽名方案.

對于表1中的同態(tài)簽名方案,文獻(xiàn)[26]中的線性同態(tài)簽名方案能夠滿足電子投票系統(tǒng)的要求.該方案不僅能夠?qū)谷鯏呈?并且還具有完全上下文隱藏的隱私性.而基于格的層次型全同態(tài)簽名方案[45]和基于格的同態(tài)聚合簽名方案[49]也滿足要求,并且文獻(xiàn)[49]的同態(tài)聚合簽名方案還能夠?qū)馆^強(qiáng)的敵手.如果需要簽名的數(shù)據(jù)是經(jīng)過加密的,那么具有高效驗證多項式函數(shù)的同態(tài)簽名方案[8]和多鑰線性同態(tài)簽名方案[53]也是不錯的選擇.

4.6.2 智能電網(wǎng)

智能電網(wǎng)是電網(wǎng)的智能化,是建立在集成的、高速雙向通信網(wǎng)絡(luò)基礎(chǔ)上的一種新技術(shù),能夠?qū)崿F(xiàn)智能發(fā)電、負(fù)載均衡、資源分配和基于實時用電的動態(tài)定價等功能[16].但新技術(shù)目前還存在著許多問題,由于用戶大量的用電數(shù)據(jù)會經(jīng)智能電表傳輸并存儲在云中,因此用電數(shù)據(jù)可能會被黑客篡改或者泄露,并且電力供應(yīng)商的工作人員也有可能利用收集的信息分析出消費者的相關(guān)隱私信息.為了保護(hù)消費者的數(shù)據(jù)安全和隱私,學(xué)者們提出了一些網(wǎng)內(nèi)數(shù)據(jù)聚合的安全隱私保護(hù)方案,首先對數(shù)據(jù)使用同態(tài)加密方案進(jìn)行加密,然后使用同態(tài)屬性進(jìn)行聚合,因此同態(tài)簽名方案起到了重要的作用.和上述電子投票系統(tǒng)對選票簽名的過程類似,在智能電網(wǎng)中對加密數(shù)據(jù)簽名的過程中也存在兩種不同的情況.第一種是所有的智能電表對加密數(shù)據(jù)都使用同一個私鑰進(jìn)行簽名,這種情況只需要考慮具有同態(tài)屬性的簽名方案.第二種是智能電表使用不同的私鑰進(jìn)行簽名,那么則要考慮同態(tài)聚合簽名方案或者多鑰同態(tài)簽名方案.對于智能電網(wǎng)來說,由于電力使用數(shù)據(jù)需要實時傳輸,簽名必須在短時間內(nèi)生成,因此要保證同態(tài)簽名方案能夠提供較高的效率.并且智能電網(wǎng)的存儲能力有限,方案生成的簽名長度不能太長.除此之外,發(fā)送的數(shù)據(jù)可能存在被拒絕需要重新發(fā)送的情況,敵手可以進(jìn)行多次查詢,因此同態(tài)簽名方案需要對抗較強(qiáng)的敵手.由于只對加密的數(shù)據(jù)進(jìn)行簽名,簽名方案沒有關(guān)于隱私性方面的限制.

應(yīng)用于智能電網(wǎng)的同態(tài)簽名方案需要能夠?qū)箯?qiáng)敵手,而表1中的同態(tài)聚合簽名方案[49]和多鑰線性同態(tài)簽名方案[53]能夠滿足上述的要求.其中文獻(xiàn)[49]的同態(tài)聚合簽名方案是基于格困難問題的,可以提供對抗量子計算機(jī)攻擊的特性.文獻(xiàn)[53]的多鑰線性同態(tài)簽名方案的簽名長度與數(shù)據(jù)集大小成對數(shù)關(guān)系,具有較小的簽名.現(xiàn)有的線性同態(tài)簽名方案都不能夠滿足智能電網(wǎng)的要求,這是因為受到了不可偽造性的限制.因此,設(shè)計一個適用于智能電網(wǎng)的線性同態(tài)簽名方案可以作為未來的一個研究方向.

4.6.3 電子健康記錄

電子健康記錄是人們在醫(yī)療與健康相關(guān)的活動中直接形成的具有保存?zhèn)洳閮r值的電子化歷史記錄.電子健康記錄中的個人健康信息通過計算機(jī)進(jìn)行數(shù)字化存儲和管理,不同的醫(yī)療機(jī)構(gòu)都能夠訪問存儲的數(shù)據(jù),并且還能夠?qū)ζ溥M(jìn)行計算操作[16].因此需要同態(tài)簽名方案來實現(xiàn)上述的功能.電子健康記錄系統(tǒng)在對健康數(shù)據(jù)進(jìn)行簽名的時候,也存在著兩種情況,一種是由一個醫(yī)生或者一個醫(yī)療機(jī)構(gòu)使用一個私鑰對健康數(shù)據(jù)進(jìn)行簽名,這種情況只需要具有同態(tài)屬性的簽名方案.另外一種是由多個醫(yī)生或醫(yī)療機(jī)構(gòu)使用多個不同的私鑰進(jìn)行簽名,那么這種情況則需要同態(tài)聚合簽名方案或者多鑰同態(tài)簽名方案.由于電子健康記錄的數(shù)據(jù)涉及到用戶的敏感信息,同態(tài)簽名方案生成的簽名不能泄露原始數(shù)據(jù)集的信息,因此同態(tài)簽名方案需要能夠?qū)崿F(xiàn)至少為弱上下文隱藏的隱私特性.另外,方案需要較高的效率,因為電子健康記錄系統(tǒng)要存儲的數(shù)據(jù)量較大,并且在數(shù)據(jù)上的計算功能比較重要,而相對來說簽名的大小并不是很重要.由于敵手可以進(jìn)行多次數(shù)據(jù)查詢,因此同態(tài)簽名方案需要能夠?qū)瓜鄬^強(qiáng)的敵手.

由于受到了不可偽造性和隱私性的限制,目前存在的線性同態(tài)簽名方案、多項式同態(tài)簽名方案、全同態(tài)簽名方案和多鑰同態(tài)簽名方案都不能夠滿足上述的要求,因此如何改進(jìn)這4種類型的同態(tài)簽名方案以適用于電子健康記錄系統(tǒng)可以作為進(jìn)一步的研究方向.表1中的基于格的同態(tài)聚合簽名方案[49]則可以滿足電子健康記錄系統(tǒng)的要求.該方案不僅能夠通過抗量子攻擊特性,而且效率比較可觀,關(guān)鍵是能夠?qū)馆^強(qiáng)的敵手和提供弱上下文隱藏的隱私特性.

5 結(jié)束語

同態(tài)簽名是數(shù)字簽名技術(shù)的一個重要的分支,在信息時代具有重要的作用,目前在該領(lǐng)域上的研究已經(jīng)取得了不少的成果,本文對同態(tài)簽名方案在最近十多年的進(jìn)展做出了一個最新的、全面的綜述.文章給出了同態(tài)簽名方案的框架及相關(guān)定義,描述了同態(tài)簽名方案所具有的特性,簡單介紹了同態(tài)簽名方案所依賴的不同類型的密碼學(xué)基礎(chǔ),并且系統(tǒng)地論述了線性同態(tài)簽名方案、多項式函數(shù)同態(tài)簽名方案、全同態(tài)簽名方案、同態(tài)聚合簽名方案以及多鑰同態(tài)簽名方案的基本概念與研究現(xiàn)狀,然后分別給出了5種不同類型的具有代表性的同態(tài)簽名方案,最后為云計算應(yīng)用場景提供了合適的同態(tài)簽名方案.根據(jù)以上對同態(tài)簽名方案研究現(xiàn)狀的分析,提出未來研究工作可能的幾個研究方向:

(a)由于沒有對現(xiàn)有的同態(tài)簽名方案的效率進(jìn)行深入的比較與分析,也沒有一個能夠衡量同態(tài)簽名方案的效率標(biāo)準(zhǔn),因此為了能夠更好地分析并提高一個方案的效率,以便適用于各種應(yīng)用實例,如何制定一個嚴(yán)格的效率標(biāo)準(zhǔn)可以作為進(jìn)一步的研究方向.

(b)目前常用的同態(tài)聚合簽名方案和多鑰同態(tài)簽名方案只支持在簽名數(shù)據(jù)上進(jìn)行線性操作,這是遠(yuǎn)遠(yuǎn)不夠的,并且在方案中添加指定實體的特性也是一個不錯的考慮.在未來的工作中,構(gòu)造類型更多的同態(tài)聚合簽名方案和多鑰同態(tài)簽名方案將會是未來的研究熱點.

(c)現(xiàn)有的多項式函數(shù)同態(tài)簽名方案都不能夠提供弱上下文隱藏的隱私特性,不能夠適用于有隱私保密要求的具體應(yīng)用,因此設(shè)計能夠提供隱私特性的多項式函數(shù)同態(tài)簽名方案具有較高研究價值.