標(biāo)準(zhǔn)模型下的基于身份簽名的效率型密碼.doc

標(biāo)準(zhǔn)模型下安全的基于身份的有效簽名Kenneth G. Paterson and Jacob C.N. SchuldtInformation Security Group,Royal Holloway, University of London,Egham, Surrey, TW20 0EX, UKkenny.paterson, jacob.schuldtrhul.ac.uk摘要：唯一已知的基于身份簽名的構(gòu)造方法可以在標(biāo)準(zhǔn)模型下被證明是安全的，這是是基于在非基于身份簽名上附加證書的方法。這種傳統(tǒng)的構(gòu)造方法引起了方案的一些非效率型因素或者枝蔓，這便提出了尋找更有效率更直接的構(gòu)造問題。我們給出了第一個(gè)這種構(gòu)造方案。我們的方案沿襲沃特斯最近提出的基于身份的加密方案的改進(jìn)方案。它是一種效率的算法并且簽名的長度很短。這個(gè)方案的安全性在標(biāo)準(zhǔn)模型下得到驗(yàn)證并且依靠了配對群上Diffie-Hellman問題計(jì)算的困難程度。1. 簡介基于身份的加密（IBE），首次被Shamir 提出Sha84,這使得我們可以給一個(gè)對象計(jì)算一個(gè)公鑰，這僅僅需要取得常規(guī)的特征方案和一串識別對象的字符串（比如郵件地址，電話號碼等）。絕對安全的私鑰生成器（PKG）計(jì)算出私鑰，并且把這些私鑰分配給每個(gè)對象。這樣，就避免了使用在傳統(tǒng)公鑰加密中使用的證書。盡管Shamir早在1984年就提出了IBE 方案的想法，但直到Boneh和Franklin以及Cocks的論文發(fā)表以后才有了既安全又有效的構(gòu)造方法。這以后，這個(gè)領(lǐng)域里出現(xiàn)了大量的論文（查閱BAR可以獲得部分這些論文的列表），包括包涵若干直接構(gòu)造的基于身份簽名的方案。大多數(shù)這些基于身份的簽名方案在隨機(jī)預(yù)言模型中被證實(shí)是安全的。但是，事實(shí)上當(dāng)隨機(jī)預(yù)言模型代入一個(gè)具體的散列函數(shù)時(shí)，結(jié)果方案可能并不是安全的。為了解決這個(gè)問題，進(jìn)來在建立標(biāo)準(zhǔn)模型下絕對安全的IBE方案上花費(fèi)了很多努力。Boneh和Boyen最先提出了一個(gè)IBE方案，這個(gè)方案在使用一個(gè)“精心選擇的ID”的模型下被驗(yàn)證安全了，這個(gè)模型比Boneh和Franklin最初提出的模型條件要弱。同樣的作者在隨后提出了一個(gè)IBE方案，這個(gè)方案在所有Boneh-Franklin安全模型和標(biāo)準(zhǔn)模型下都是安全的，但效率卻不高。最后，Waters成功的構(gòu)造出一個(gè)簡明有效的IBE方案，這個(gè)方案同時(shí)滿足安全和效率兩方面的要求。Naccache和Chatterjee-Sarkar獨(dú)立提出了一個(gè)減少Waters的方案中對尺寸要求的技術(shù)，這使得這個(gè)方案更加適合實(shí)際應(yīng)用。建立IBS方案一個(gè)一般的方法就是使用普通簽名方案（例如非基于身份的簽名方法）并且附加上包含簽名人公鑰的方法來簽名的。這種基于證書的方法似乎很通俗，它的各種不同版本也在過去到現(xiàn)在的各種論文中有所提及。這個(gè)技術(shù)的簡明性表明在某些方面，IBS方案比IBE方案更容易獲取。而且，如果使用普通簽名方法作為簽名的組成部分的方法在標(biāo)準(zhǔn)模型下是安全的，我們就可以得到一個(gè)在標(biāo)準(zhǔn)模型下也安全的IBS方法。但是這種構(gòu)造方法也有缺點(diǎn)。一個(gè)缺點(diǎn)是在建立基于身份的簽名時(shí)我們同時(shí)需要公鑰（簽名人的）和兩個(gè)普通簽名（一個(gè)來自簽名人另一個(gè)來自于證書提供者）。這一點(diǎn)影響簽名的長度。另一個(gè)缺點(diǎn)是每一個(gè)基于身份的簽名方案中的驗(yàn)證都要涉及到兩個(gè)普通簽名的驗(yàn)證。這兩個(gè)不利條件導(dǎo)致了方案的一些沒有效率的問題?？刹豢梢哉业揭粋€(gè)在標(biāo)準(zhǔn)模型下更好的方法？這個(gè)問題逐漸浮現(xiàn)出來。一個(gè)有趣的現(xiàn)象就是，任何IBE方案都可以應(yīng)用到構(gòu)造一個(gè)普通的簽名方案，這個(gè)現(xiàn)象的發(fā)現(xiàn)要?dú)w功于Boneh和Franklin的Nore。這要靠把IBE的主秘密數(shù)作為私鑰，并且公布方案的參數(shù)作為私鑰。對一條名為的信息簽名，使用身份私鑰為而且驗(yàn)證可以通過選擇一個(gè)隨機(jī)信息來執(zhí)行。使用公鑰加密信息，而且驗(yàn)證解密信息可能要用到給出的解密密鑰。如果使用的IBE方案是IND-ID-CPA安全，生成的簽名在適應(yīng)選擇消息攻擊下是存在性不可偽造的。這個(gè)技術(shù)被Boneh，Lynn和Shancham用來從Boeneh和Franklin的IBE方案建立短簽名，類似于Boneh和Boyen從一個(gè)IBE方案得到另一種短簽名方案都要?dú)w功于同一個(gè)作者。正如Gentry和Silverberg所闡述的，如果分等級的IBE方案（HIBE）被使用在一個(gè)IBE方案中，IBS方案可以用一種十分相似的方法建立出來。事實(shí)上這將會(huì)導(dǎo)出一個(gè)分等級的IBS方案，這個(gè)方案身份簽名是一個(gè)比使用到HIBE方案少一個(gè)層次的層次結(jié)構(gòu) 一部分。當(dāng)身份簽名消息，身份作為的一個(gè)孩子被插入到層次結(jié)構(gòu)中。綜上，一個(gè)簽名就是的私鑰，驗(yàn)證者檢查一條通過使用公鑰作為身份隨機(jī)信息是可能的。限制HIBE的等級數(shù)為2等級方案就是普通的IBS方案了。我們的構(gòu)造。這個(gè)方案是在提供一個(gè)在不適用隨機(jī)預(yù)言時(shí)安全的方案的研究的一個(gè)自然延伸，我們給出了第一個(gè)直接構(gòu)造IBS的方案，這個(gè)方案在標(biāo)準(zhǔn)模型下被證實(shí)是安全的。我們的方案是基于對Waters的方案在分等級上的擴(kuò)展，我們用了上面所描述的一個(gè)轉(zhuǎn)化2層HIBE方法到一個(gè)IBS方法來構(gòu)造我們的方案。我們在通過計(jì)算Diffie-Hellman問題難度的假設(shè)來保證我們的簽名方案是安全的。這個(gè)假設(shè)似乎比現(xiàn)今介紹到基于配對的加密方法中的硬度假設(shè)更加自然。就簽名的長度和計(jì)算的效率上說，我們的新方法在已經(jīng)存在的基于身份的簽名方案中是很有競爭力的（那些是在隨機(jī)預(yù)言模型中被證明是安全的方案）。我們的簽名有三組元素構(gòu)成，簽名過程中不需使用配對，驗(yàn)證過程過程需要用到3個(gè)配對計(jì)算。我們的方案在計(jì)算效率和簽名長度上較在Waters的方案上附加基于證書的結(jié)構(gòu)的那些方案有更大的優(yōu)勢。對比那些由Boneh和Boyen的簽名方案得到的方案，我們的方案大概一半的長度，但驗(yàn)證計(jì)算要花費(fèi)更多的一組配對計(jì)算。但是，Boneh和Boyen衍生出來的方案的安全性依賴于q-SDH問題的硬度假設(shè)，然而我們的方案的安全性是基于可論證的計(jì)算性Diffie-Hellman（CDH）問題硬度假設(shè)。我們的方案存在的唯一一個(gè)缺陷就是公共參數(shù)占據(jù)一個(gè)相對較大的尺寸。但是，我們展示了 一個(gè)如何在方案中使用Naccachehe Chatterjee-Sarkar的技術(shù)來減少公共參數(shù)尺寸的方法，代價(jià)是損失了安全性。2. 基于身份的簽名一個(gè)基于身份的簽名方案可以被描述為以下四個(gè)算法步驟初始化. 這個(gè)算法在可靠安全實(shí)體上執(zhí)行，輸入一個(gè)秘密參數(shù)，生成一個(gè)公共的參數(shù)，和一個(gè)可靠秘密參數(shù)?？煽堪踩珜?shí)體公布保留可靠秘密參數(shù)。提取. 給定一個(gè)身份，可靠秘密參數(shù)和，這個(gè)算法生成私鑰的一個(gè)私鑰?？煽堪踩珜?shí)體將會(huì)用這個(gè)算法為所有參與方案的實(shí)體生成私鑰并且通過安全渠道分配這些私鑰到每一個(gè)所有者。簽名. 給定一條消息，一個(gè)身份，私鑰和，這個(gè)算法生成對的一個(gè)簽名。使用身份的實(shí)體將使用這個(gè)算法來簽名。驗(yàn)證. 給定簽名，消息，身份和，如果是對有效簽名算法輸出，否則輸出。2.1 存在的不可偽造性Goldwasser，Micali和Rivest定義了一個(gè)存在的不可偽造性在一個(gè)有適應(yīng)能力的選擇消息攻擊下的安全性模型，這個(gè)模型可以自然的延伸到基于身份的方案中。我們將在下面給出的挑戰(zhàn)者和對手的游戲中確定基于身份簽名的安全性：初始化. 挑戰(zhàn)者啟動(dòng)簽名方案中的初始化得到公共參數(shù)和可靠秘密數(shù)字。對手獲得但是可靠秘密數(shù)字由挑戰(zhàn)者保存。提問. 對手有適應(yīng)性的編造出許多不同的問題交給挑戰(zhàn)者。每一個(gè)問題可以是一下的其中一個(gè)。l 提取問題。對手可以詢問到任何一個(gè)身份的私鑰。挑戰(zhàn)者通過執(zhí)行回答詢問，并發(fā)送私鑰給對手。l 簽名問題。對手可以詢問任意身份對消息的簽名。挑戰(zhàn)者通過運(yùn)行得到的私鑰，然后運(yùn)行得到簽名，簽名有挑戰(zhàn)者發(fā)送給對手。偽造. 對手輸出一條消息，一個(gè)身份和一串簽名。以下內(nèi)容有效的話表明對手偽造成功：a)b) 對手沒有對做出抽取提問.c) 對手沒有對做簽名提問.以上游戲中對手的有利因素定義為其中，這個(gè)概率是挑戰(zhàn)者和對手游戲中所有成功事件都發(fā)生的概率。定義 1. 在一個(gè)基于身份的簽名方案中一個(gè)對手被認(rèn)為是一個(gè)偽造者如果在上述游戲中有至少存在、最長運(yùn)行時(shí)間為，分別制造出最多為和個(gè)抽取問題和簽名問題。一個(gè)方案被認(rèn)為是安全的如果偽造者不存在。以上的游戲可以很容易的延伸覆蓋強(qiáng)不可偽造性，這要在偽造這一步驟中改變第三個(gè)要求為“不是作為一個(gè)簽名響應(yīng)而得到”。但是，我們確定的方案在這種強(qiáng)條件下并不安全，因?yàn)閿呈挚梢暂p易的更改一個(gè)已經(jīng)存在對某信息的簽名是指成為一條同樣信息的新簽名。3. 復(fù)雜性假設(shè)我們的簽名方案的安全性在簽名被建立以后將被規(guī)約為計(jì)算性Diffie-Hellman問題的解決困難性。我們簡要的回顧一下CDH問題的定義：定義 2. 給出一個(gè)階為群并含有生成元和元素，其中是從均勻隨機(jī)選擇出的兩個(gè)數(shù)。則中的CDH問題就是計(jì)算。定義3. 我們說中的假設(shè)成立，如果沒有算法在時(shí)間內(nèi)解決CDH問題的可能性至少為。4. 構(gòu)造我們新的基于身份的簽名方案是建立于Waters提出的基于身份加密方案分等級延伸。但是，如第5節(jié)指出的，我們的安全性減少到CDH問題的困難性，而Waters的方案依托于強(qiáng)雙線性Diffie-Hellman假設(shè)。我們的方案是基于雙線性映射?，F(xiàn)在簡要的介紹這個(gè)映射的一些基本性質(zhì)。令和為一個(gè)階為的群，令為的一個(gè)生成元。映射被認(rèn)為是合格映射如果滿足一下三條條件：a) 是雙線性映射，即對所有都成立.b) 是非退化性的，即.c) 是有效可計(jì)算的.查閱Gal05以便了解更多關(guān)于這個(gè)映射的信息。在第7節(jié)中，我們簡略闡述了需求的改變，以便于允許我們的方案在更加普遍的狀態(tài)下操作，即其中.以下所有身份和消息將被假設(shè)為長度分別為和比特流。建立一個(gè)滿足任意長度的身份和消息的更加靈活的方案就需要定義沖突抵制的散列函數(shù)，和，這兩個(gè)散列函數(shù)用來創(chuàng)建指定長度的身份和消息。我們將用記號作為從集合中隨機(jī)選擇出的簡稱。我們新的簽名方案由以下算法定義出來：初始化. 選擇階為的群和，一個(gè)合格的配對運(yùn)算：，構(gòu)造的一個(gè)發(fā)生器。現(xiàn)在，選擇一個(gè)秘密數(shù)字，計(jì)算，選取。并且選擇長度分別為和的元素，向量，向量的分量從中隨機(jī)選取。公共參數(shù)即，秘密數(shù)字為。提取. 令為一串長度為的比特流，它表示一個(gè)身份，令為的第位上的比特字。定義為所有滿足的指數(shù)的集合。構(gòu)造私鑰身份為的實(shí)體的私鑰，選取并計(jì)算：注意用戶可以很容易的在從絕對安全實(shí)體上獲得私鑰以后把私鑰隨機(jī)化。簽名. 令為一串長度為的比特流，它表示一個(gè)身份，令為一串表示消息的比特流。類似于在提取算法中定義為所有滿足的指數(shù)的集合，定義為所有滿足的指數(shù)的集合。提取并計(jì)算即為對消息的簽名。驗(yàn)證. 給定待驗(yàn)證的簽名為身份對消息的簽名。如果滿足：則驗(yàn)證者接受消息。顯然簽名算法得出的簽名可以被驗(yàn)證者接受。因此這個(gè)方案是正確的。4.1 方案效率方案中私鑰和簽名的尺寸大小分別是2和3組元素。但是要注意簽名元組的第2個(gè)值將在給定相同用戶的情況下保持不變。因此，如果單一用戶要對多條消息進(jìn)行簽名，或者單一驗(yàn)證者要驗(yàn)證多條同一個(gè)用戶簽名的多條消息時(shí)，只要包含在其中一條信息的簽名中。公共參數(shù)包括，對群的描述信息，配對和組的元素。在實(shí)際的方案中，公共參數(shù)的大小與具體執(zhí)行有關(guān)系，我們在第6節(jié)中討論了怎樣減少中群元素的需求數(shù)量。為了構(gòu)造一個(gè)簽名，簽名者需要計(jì)算最多次上的乘法（平均次），并且執(zhí)行2次上的乘冪運(yùn)算。驗(yàn)證過程最多需要次上的乘法運(yùn)算（平均次）和四次配對運(yùn)算。但是，可以預(yù)先計(jì)算出來并暫時(shí)存儲(chǔ)，這樣可以減少驗(yàn)證過程中配對運(yùn)算的花銷。如果一個(gè)驗(yàn)證者驗(yàn)證同一簽名人的多個(gè)消息簽名，更進(jìn)一步的配對運(yùn)算也可以省略了。因此，我們的方案就稍微比目前的IBS方案的花銷要大些（查閱Hes02中的表格可以獲得更多例子），但是，正如下一節(jié)要展示的，我們的方案在標(biāo)準(zhǔn)模型下是安全的，而那些方案是在隨機(jī)預(yù)言模型中被證實(shí)是安全的。我們也已經(jīng)在簡介在應(yīng)用于標(biāo)準(zhǔn)模型下安全方案時(shí)比較了我們這個(gè)方案和源于基于證書的IBS方案。5. 安全性證明我們將在標(biāo)準(zhǔn)模型下證明我們的方案在選擇性消息攻擊下是存在性不可偽造的。這個(gè)結(jié)論是建立在計(jì)算性Diffie-Hellman問題難以解決的基礎(chǔ)之上的。定理1. 假設(shè)假設(shè)在中成立，且則第4節(jié)的基于身份簽名方案是安全的，其中分別是中進(jìn)行乘法和乘冪運(yùn)算的時(shí)間。證明：假設(shè)方案中存在一個(gè)偽造者。由這個(gè)偽造者，我們可以建立算法，該算法可以在最多的時(shí)間內(nèi)以大于的概率解決CDH問題，這與假設(shè)相悖。我們的方法是基于Wat05中所言。算法需要被給出群，一個(gè)生成元和元素。如果要使得能夠計(jì)算出，那么必須能夠模仿的一個(gè)挑戰(zhàn)者。這個(gè)模仿過程如下所示：開始. 置，隨機(jī)選取兩個(gè)整數(shù)，。給定和時(shí)我們假設(shè)。模擬器則選擇一個(gè)整數(shù)和一個(gè)長度為向量，其中對于任意。類似的選擇另一個(gè)整數(shù)，長度為的向量，。最后選擇兩個(gè)整數(shù)，再分別選擇長度分別為和的向量，其中。為了表達(dá)式的簡潔，分別對于身份和消息定義下面兩對函數(shù)：現(xiàn)在完成下面的任務(wù)來建立IBE方案中的公共參數(shù)集合：注意這些公共參數(shù)與挑戰(zhàn)者和的游戲是同分布的。并且，這些步驟表示主密鑰將是，對于任意，等式成立。所有的公共參數(shù)傳遞給。詢問. 對手算法運(yùn)行時(shí)，抽取問詢和簽名問詢都有可能發(fā)生。按照如下方式回答問詢l 抽取問詢。假設(shè)提問是為了得到身份的私鑰。不知道主密鑰，但是假設(shè)可以通過選取并計(jì)算而建立私鑰。記，可以驗(yàn)證以這種方式產(chǎn)生的是一個(gè)有效的私鑰。因?yàn)椋翰⑶乙虼藢τ趯κ謥碚f，所有由計(jì)算得到的私鑰和真正挑戰(zhàn)者生成的私鑰是難以區(qū)分的。另一方面，假如說，則以上的計(jì)算不能進(jìn)行，模擬器將因此被抑制。為了簡化分析模擬，一旦我們強(qiáng)制抑制模擬器。假設(shè)，則必有且。很顯然可以推出，因此，推出。所以以上的情況必定保證的私鑰可以被建立。l 簽名詢問。考察對的一次問詢（不失一般性，可以假設(shè)還沒有對做抽取問詢）。若，就可以在一次抽取問詢中建立的私鑰，并使用算法得到對的簽名。如果，將嘗試用與在抽取問詢中構(gòu)造私鑰類似的方法建立簽名。假設(shè)。同上面結(jié)論，這表示。不妨設(shè)。選取計(jì)算對的簽名：其中。這個(gè)等式表示回應(yīng)的簽名問詢是分散的，因?yàn)樗麄円c真正的挑戰(zhàn)者配合。如果，模擬器被抑制。偽造. 如果在以上每個(gè)問詢中都沒有被抑制，會(huì)以至少的可能性返回身份，消息和對有效偽造簽名。如果或那么將被抑制。另一方面，如果且，計(jì)算并輸出這是給定CDH問題的解。下面完成對模擬過程的描述。我們還需要分析的就是不被抑制的概率。為了使模擬過程不被抑制，必須使所有的抽取問詢中對身份有，所有簽名詢問中要么滿足，要么滿足，并且。但為了簡化分析，我們要給出這個(gè)事件的子事件的概率范圍。更確切的說，我們要把簽名詢問分成兩類涉及的詢問和涉及的提問。然后我們考察所有身份滿足，排除簽名詢問中滿足且也會(huì)應(yīng)答的情況。這樣，我們將給出不被抑制的一個(gè)削弱的概率范圍。令是抽取問詢和簽名問詢中出現(xiàn)的非挑戰(zhàn)身份，令簽名問詢中不涉及挑戰(zhàn)身份的消息。顯然，且。定義事件和為從以上的分析中得出，不被抑制的概率是容易看出事件和是相互獨(dú)立的。本質(zhì)上是因?yàn)楹瘮?shù)和確定了這些事件是選擇性獨(dú)立的而且對于敵手是隱藏起來的。由以上可以看出，假設(shè)可以推出。而且，這個(gè)假設(shè)給出如果，則存在唯一的滿足，其中。因?yàn)楹蜁r(shí)隨機(jī)選取的，我們有也可以得到置模擬過程中得到類似的分析簽名詢問得到如下結(jié)論也可以得到如果模擬過程沒有被抑制，就能夠以至少產(chǎn)生一個(gè)有效的偽造簽名。算法可以從以上結(jié)果中計(jì)算出。算法的時(shí)間復(fù)雜度受到抽取和簽名詢問中乘冪運(yùn)算，和的大小，乘法運(yùn)算的影響。因?yàn)樵诔槿『秃灻儐栔蟹謩e存在和的乘法運(yùn)算和和的乘冪運(yùn)算，所以時(shí)間復(fù)雜度為因此，定理證明完畢。6. 用安全性換取效率在一個(gè)實(shí)際的方案中，的身份和的消息大部分是由可抵抗沖突的散列函數(shù)產(chǎn)生的。這使得和最小為160，也就是說我們方案中的公共參數(shù)將包含最少325個(gè)中群元素。當(dāng)選定的使得其上的CDH問題被認(rèn)作是困難的，那么公共參數(shù)的大小將上升到不適合環(huán)境存儲(chǔ)容量的大小。但是，Naccache Nac05和Chatterjee-Sarkar SC05獨(dú)立提出了一個(gè)對Waters的方案改進(jìn)，這個(gè)改進(jìn)將減少公共參數(shù)的大小。這個(gè)改進(jìn)也適合我們的簽名方案。.. Naccache和Chatterjee-Sarkar的技術(shù)在我們的方案中，當(dāng)一個(gè)實(shí)體簽名了某條消息，他便計(jì)算產(chǎn)物其中是滿足第位為1的指數(shù)的集合。這個(gè)技術(shù)的想法就是把消息認(rèn)作是連接在一起的整數(shù)集合而不是連串的二進(jìn)制位集合。例如：其中且，則以此代替上面的產(chǎn)物得到這將以因子減少的大小并且公共參數(shù)中包含的群元素的個(gè)數(shù)將變小到。類似的，一個(gè)身份被人做是一連串的整數(shù)，并用上面類似的方法替換中的元素。的大小將以因子減小。同時(shí)使用兩種改進(jìn)，公共參數(shù)將被減小到6.2. 改進(jìn)方案的安全性如果使用上述改進(jìn)，我們方案的安全性分析與第5節(jié)十分類似。但是，需要對函數(shù)和改進(jìn)以保證這些函數(shù)還具有在第5節(jié)中需要的性質(zhì)。我們可以假設(shè)與第5節(jié)同樣的開始步驟，集中考察對我們改進(jìn)方案的安全性分析有效的更改。如前面所敘述的，我們將分別假設(shè)由和的整數(shù)組成的身份和消息。第一個(gè)更改是模擬過程中開始緩解和的選擇范圍，范圍擴(kuò)張到和模擬過程開始階段的其他所有選擇值和步驟都與原方案一樣。我們假設(shè)且重新定義和為：其中和指示的 位和位的整數(shù)分別組成了和。顯然這些更改使得以下結(jié)論成立：l 且l 推出且推出。l 若，那么存在一個(gè)唯一的，使得。類似的，若，那么存在唯一使得，。有了這些性質(zhì)，模擬過程其他的階段就和第5節(jié)敘述的內(nèi)容一樣的進(jìn)行了。對模擬過程成功概率的分析與第5節(jié)分析的基本一致，因?yàn)橹挥泻椭档淖兓秶ɡ缟厦媪谐龅淖詈笠粭l性質(zhì)）影響了對應(yīng)概率。這改變了事件和在更新的函數(shù)和，我們可以得到因?yàn)槭录偷母怕什灰驗(yàn)楹瘮?shù)的改變而改變，成功的概率是成功的概率大約以因子低于第5節(jié)中模擬過程成功概率。時(shí)間復(fù)雜度保持為其中是敵手花費(fèi)的時(shí)間，是中一次乘法運(yùn)算花費(fèi)的時(shí)間，是中一次乘冪運(yùn)算花費(fèi)的時(shí)間。6.3. 在大小，計(jì)算量和安全性之間權(quán)衡以上的結(jié)果表明我們可以減少公共參數(shù)中的元素個(gè)數(shù)到，但相比原方案安全性喪失了比特。對一個(gè)較小的和，以安全性交換更高的執(zhí)行效率是可以接受的。這就是Naccache提出的方法。但是，用提高方案的計(jì)算性花費(fèi)來阻止損失安全性是可能的。這個(gè)想法是由Chatterjee-Sarkar提出的，他提出可以通過提高的大小從而提高其上CDH問題的困難度的方法，這個(gè)方法可以彌補(bǔ)因?yàn)榻o定和的選擇值來引起的安全性丟失。但是，當(dāng)這個(gè)方法使用時(shí)有多個(gè)因數(shù)需要考慮。第一，上的CDH問題所提供的安全性需要顧及。目前，最有名的解決CDH問題的方法是靠解決離散對數(shù)問題（DLP）。上的DLP問題可以很容易的被規(guī)約到上的DLP問題，因此解決和上的DLP問題最熟知的方法要在選擇群的時(shí)候被考慮到。第二，需要考慮選擇適當(dāng)?shù)臋E圓曲線類的可行性，合適的橢圓曲線要滿足能夠建立一個(gè)的配對其中和滿足上述要求。我們注意到SC05的作者沒有注意到這一點(diǎn)。最后，和增大將導(dǎo)致單個(gè)群元素的存儲(chǔ)空間增大，而且算法復(fù)雜度也相應(yīng)的提高。所有的論文中都很重視在公共參數(shù)減少的情況下評價(jià)方案的效率和安全性。但我們沒有對這個(gè)細(xì)節(jié)的分析。7. 應(yīng)用常規(guī)曲線的方案構(gòu)造目前，唯一已知的建立雙線性映射的方法是在橢圓曲線上使用一個(gè)Weil或者Tate配對。此外，若我們的方案中假設(shè)，那么我們就必須選擇超奇異橢圓曲線，這是一類限制很強(qiáng)的曲線。但是，我們的方案可以很容易推廣到使用形如的雙線性映射，允許使用更加一般的橢圓曲線。這個(gè)靈活性遇到特定明確的安全級別時(shí)實(shí)施和選擇參數(shù)時(shí)很重要。對廣義的方案的安全性證明，我們要求存在一個(gè)有效可計(jì)算的同構(gòu)映射，而且滿足的生成元對應(yīng)的生成元。這個(gè)同構(gòu)映射只是在安全性證明中用到，并不是方案的一部分。而且，方案的安全性也將被減小到上的co-Diffie-Hellman問題BLS04。PS02中可以找到完整細(xì)節(jié)。8. 結(jié)論我們給出了第一個(gè)直接建立基于身份的簽名方案，而且在標(biāo)準(zhǔn)模型下被驗(yàn)證是安全的。我們基本的方案計(jì)算效率高，而且我們給出了改進(jìn)提高空間需求和提高參數(shù)的選定范圍的技術(shù)。很容易看出我們方案可以推廣到產(chǎn)生一個(gè)分等級的IBS（HIBS）方案。但是，建立一個(gè)效率高而且在便準(zhǔn)模型下安全的HIBS方案依然是個(gè)開放性問題，這個(gè)方案必須有一個(gè)牢靠的安全規(guī)約。致謝我們感謝Jonathan Katz，Eike Kiltz和一個(gè)不知名的評論者點(diǎn)出了傳統(tǒng)基于證書的方案應(yīng)用于基于身份的簽名。參考文獻(xiàn)ADR02 J. H. An, Y. Dodis, and T. Rabin. On the security of joint signatureand encryption. In L. R. Knudsen, editor, EUROCRYPT, volume 2332 ofLNCS, pages 83107. Springer, 2002.Bar P. S. L. M. Barreto. The pairing-based crypto lounge..br/informatica/paulobarreto/pblounge.html.BB04a D. Boneh and X. Boyen. Efficient selective-ID secure identity-based encryptionwithout random oracles. In Cachin and Camenisch CC04, pages223238.BB04b D. Boneh and X. Boyen. Secure identity based encryption without randomoracles. In M. K. Franklin, editor, CRYPTO 2004, volume 3152 of LNCS,pages 443459. Springer, 2004.BB04c D. Boneh and X. Boyen. Short signatures without random oracles. InCachin and Camenisch CC04, pages 5673.BBP04 M. Bellare, A. Boldyreva, and A. Palacio. An uninstantiable randomoracle-model scheme for a hybrid-encryption problem. In Cachin andCamenisch CC04, pages 171188.BF01 D. Boneh and M. K. Franklin. Identity-based encryption from the Weilpairing. In J. Kilian, editor, CRYPTO 2001, volume 2139 of LNCS, pages213229. Springer, 2001.BLMQ05 P. S. L. M. Barreto, B. Libert, N. McCullagh, and J. Quisquater. Efficientand provably-secure identity-based signatures and signcryption frombilinear maps. In B. Roy, editor, ASIACRYPT, volume 3788 of LNCS,pages 515532. Springer, 2005.BLS04 D. Boneh, B. Lynn, and H. Shacham. Short signatures from the Weilpairing. J. Cryptology, 17(4):297319, 2004.BNN04 M. Bellare, C. Namprempre, and G. Neven. Security proofs for identitybasedidentification and signature schemes. In Cachin and CamenischCC04, pages 268286.BR93 M. Bellare and P. Rogaway. Random oracles are practical: a paradigm fordesigning efficient protocols. In Proc. of CCS 1993, pages 6273. ACMPress 1993.CC03 J. C. Cha and J. H. Cheon. An identity-based signature from gap Diffie-Hellman groups. In Desmedt Des02, pages 1830.CC04 C. Cachin and J. Camenisch, editors. Proc. of EUROCRYPT 2004, volume3027 of LNCS. Springer, 2004.CGH98 R. Canetti, O. Goldreich, and S. Halevi. The random oracle methodology,revisited (preliminary version). In STOC, pages 209218, 1998.Coc01 C. Cocks. An identity based encryption scheme based on quadraticresidues. In B. Honary, editor, IMA Int. Conf., volume 2260 of LNCS,pages 360363. Springer, 2001.Des02 Y. Desmedt, editor. Proc. of PKC 2003, volume 2567 of LNCS. Springer,2003.DKXY03 Y. Dodis, J. Katz, S. Xu, and M. Yung. Strong key-insulated signatureschemes. In Desmedt Des02, pages 130144.Gal05 S. D. Galbraith. Pairings. In G. Seroussi I.F. Blake and N.P. Smart, editors,Advances in Elliptic Curve Cryptography, pages 183212. CambridgeUniversity Press, 2005.GMR88 S. Goldwasser, S. Micali, and R.L. Rivest. A digital signature schemesecure against adaptive chosen-message attacks. SIAM J. Comput.,17(2):281308, 1988.GS02 C. Gentry and A. Silverberg. Hierarchical ID-based cryptography. In Y.Zheng, editor, ASIACRYPT 2002, volume 2501 of LNCS, pages 548566.Springer, 2002.Hes02 F. Hess. Efficient identity based signature schemes based on pairings.In K. Nyberg and H. M. Heys, editors, Selected Areas in Cryptography,volume 2595 of LN