基於身份的密碼體制是什麼？

01-25

網路安全中基於身份的密碼體制可以進行哪些領域的研究？

0 矯情一小下

手機刷知乎，看到這個問題的第一反應是邀請我師弟來回答，不過又想了想，基於身份的密碼體制這個題目看起來可以很簡單的回答，但是要都答全了可是有點難度。所以最後還是爬起來用電腦好好回答一下吧，嗯…

===============================分割線==================================

1 什麼叫做基於身份的密碼體制

公鑰密碼體制（Public Key Cryptosystem）想必大家都已經很清楚了，在公鑰密碼體制中，有兩個密鑰：公鑰和私鑰。其中，公鑰是可以公開給任何人的，任何人只要獲得了公鑰，就可以使用公鑰對消息進行加密，隨後可以通過公開信道將加密後的密文發送給接受者。只有擁有公鑰所對應私鑰的接受者才能夠正確地解密密文，恢復出明文信息。典型的公鑰加密體制有我們很熟悉的RSA體制，ElGamal體制，以及具有很高安全性的Cramer-Shoup體制。

公鑰加密體制雖然很好，但是也有很多潛在的問題。一個最大的問題就是，每個人的公鑰都是無意義的一串類似隨機數的東西，在加密的時候，加密者怎麼知道一個公鑰就是接受者的公鑰呢？如果加密過程中公鑰使用錯誤，密文就不能被正確的接收者所解密。同時，這很可能就將信息透露給了錯誤的用戶，甚至透露給惡意用戶。實際上，現實生活中確實存在這樣的攻擊方法：惡意用戶欺騙加密者，將接收者的公鑰替換為自己的公鑰並告知加密者，同時加密者無法得知收到的公鑰是否為接收者的。

解決這個問題的方法是引入一個可信第三方（有點類似於證書裡面的CA）。第三方維護一個大的表格，表格中存放各個用戶的身份，以及其所對應的公鑰信息。這樣一來，加密者可以在加密之前首先向可信第三方進行公鑰查詢，這就可以正確進行加密了。這種解決方法雖然好，但是也有一個問題：當用戶數量過多，這個表格的維護就變得很困難。首先，大量加密者都可能請求公鑰查詢，頻繁的公鑰檢索可能會使得可信第三方服務能力下降，甚至可能遭受拒絕服務攻擊（Deny of Service，DoS）。其次，即使不進行DoS攻擊，可信第三方本身也需要極佳的計算和網路通信能力，才有可能負擔得起如此大規模用戶的服務請求。這在網路通信還不是很好的情況下尚且可以忍受，但在現今社會，這種人人有網的時代，每個人都擁有一個公鑰的話，可以想像公鑰的總數量將是一個多麼龐大的數字！這對於可信第三方的存儲能力，查詢能力等等都帶來了巨大的挑戰。

那麼，有沒有一種可能，可以讓公鑰就是用戶的身份呢？所謂身份，就是指一串跟用戶相關的有意義的數字，比如身份證號，姓名，郵箱地址等等。加密者在加密的過程中，不需要使用一堆無意義的數字組作為公鑰了，而是使用接收者的身份進行加密。舉個例子，比如我的郵箱是footman_900217@126.com（這真是我郵箱…），有人想給我發送加密密文的話，就用footman_900217@126.com作為公鑰進行加密。這樣一來，加密者就不需要像可信第三方詢問接收者的公鑰了，這為公鑰信息的管理提供了極大的便利。1984年，Shamir（沒錯，就是RSA加密體制中的那個S）[1]提出了身份基密碼體制的思想（Identity-Based Cryptosystem），並且構造了身份基簽名體制（Identity-Based Signature，IBS）。即，簽名體制中的公鑰是用戶的身份，驗證簽名時，驗證者使用簽名者的身份作為公鑰進行驗證。

===============================分割線==================================

2 身份基加密體制的定義以及構造

雖然已經提出了安全的IBS體制，但是如何構造身份基加密體制（Identity-Based Encryption，IBE）成為了困擾理論界的難題。為何構造IBE如此重要呢？因為幾乎所有可用的體制都可以通過加密體制轉化而來（實際上，我們可以基於任意一個安全的IBE體制，構造安全的IBS體制，同樣也可以構造安全的身份基簽密體制（Identity-Based SignCrypt），很多其他的安全協議也需要通過加密體製作為原型函數構造）。

研究者們大概用了20年的時間才成功構造了IBE。2001年，Boneh和Franklin[2,3]正式給出IBE的定義，安全模型，並應用雙線性對（Bilinear Map）構造了一個安全的IBE方案。在此我不太想闡述方案，因為涉及到了一定的數學知識。安全模型我也不準備詳細闡述，因為這需要一定的密碼學知識。我只闡述IBE的定義。為了不引起歧義，並尊重Boneh的成果，我使用英文原文[2]進行描述。

An identity-based encryption scheme is specified by four randomized algorithms: Setup, Extract, Encrypt, Decrypt:

$extbf{Setup}$ : takes a security parameter $k$ and returns $params$ (system parameters) and $master ext{-}key$ . The system parameters include a description of a nite message space $mathcal{M}$ , and a description of a finite ciphertext space $mathcal{C}$ . Intuitively, the system parameters will be publicly known, while the $master ext{-}key$ will be known only to the "Private Key Generator" (PKG).

$extbf{Extract}$ : Extract: takes as input params, master-key, and an arbitrary $IDin{0,1}^*$ , and returns a private key $d$ . Here $ID$ is an arbitrary string that will be used as a public key, and $d$ is the corresponding private decryption key. The $extbf{Extract}$ algorithm extracts a private key from the given public key.

$extbf{Encrypt}$ : takes as input $params$ , $ID$ , and $Minmathcal{M}$ , It returns a ciphertext $C in mathcal{C}$ .

$extbf{Decrypt}$ : takes as input $params$ , $ID$ , $C in mathcal{C}$ , and a private key $d$ , It returns $M in mathcal{M}$ .

從定義上我們也可以看出，IBE體制引入了一個新的實體，叫做PKG（Private Key Generator），這個PKG可以理解為公鑰加密體制中的那個可信第三方。實際上，我用一個接收者的身份進行加密的話，我怎麼確定誰能夠解密呢？這個確定者就是PKG了。但是，與前面說到的可信第三方不同，PKG現在變成了私鑰的產生者，而非公鑰的管理者。這是IBE構造的一個比較核心的變化，如果我們用一個表格來描述的話，與一般的公鑰體制相比，IBE中各個參與方的能力具有一定的變化：

Public Key Encryption Identity-Based Encryption

私鑰產生接收者 PKG

公鑰管理可信第三方無

Boneh在他們的論文中也給出了一個可證明安全的IBE方案，具體構造有興趣的朋友們可以參考[2,3]。

===============================分割線==================================

3 身份基加密體制的發展

3.1 高安全性的IBE方案

Boneh和Franklin構造的IBE雖然好，但是其安全性沒有達到理想的狀態。實際上，BF01方案只能在隨機預言模型（Random Oracle Model）下證明安全，而理想的狀態是能夠在標準模型（Standard Model）下證明安全。因此，理論界開始嘗試在標準模型下面構造IBE。

在2004年，Boneh和Boyen[4]提出了一個標準模型下可證明安全的IBE方案。然而，他們所用的攻擊模型並非是全安全的攻擊模型(Full/Adaptive Security Model)，而是選擇安全的攻擊模型(Selective Security Model)。這裡必須指出，選擇安全攻擊模型的提出者是Canetti等人[5]。同年，Boenh和Boyen[6]提出了一個全安全的IBE方案，但是其效率比較低，不適於實際使用。2005年，Waters[7]提出了第一個高效的全安全IBE方案，效率很高，唯一的缺點是需要比較多的公開常數（就是params）。2006年，Gentry[8]提出了一個特別高效的IBE方案，基本上解決了IBE中所涉及到的全部問題。至此，對於IBE構造的進一步研究基本上是基於這幾個方案展開的。IBE剩下的問題基本上是純密碼學的問題了，如：如何構造安全性更緊的（Tightly Secure）IBE方案[9]；如何構造函數隱藏的IBE方案（Functional-Private IBE）[10]等等。

3.2 IBE的擴展

IBE中有一個比較有趣的問題：從密文中，我們能否得到用戶的身份信息呢？也就是說，只從密文中，我們能不能判斷這個密文具體是給誰發送的呢？如果密文中不泄露有關接收者的任何身份信息，我們認為這種IBE為匿名IBE(Anonymous IBE, AIBE)。雖然沒有直接證明，但是BF01方案是匿名的，Gentry06的方案也是匿名的。相反地，BB04方案，以及Waters05方案不是匿名的。AIBE的研究進一步可以擴展為關鍵字可搜索加密方案（Public Key Encryption with Keyword Search, PEKS）。因此，研究者研究AIBE的目的後面本質上變成了PEKS的研究，在此就不展開說了。

另一個IBE本身的問題是：身份雖然是一個有意義的字串，但是如果加密時候身份信息輸入錯誤，也可能導致接收者解密失敗。比如說，本來一個文件是要加密給Alice的，但是如果把身份錯誤地輸入成了Aliec，那麼Alice本身就不能解密信息了。那麼，能不能構造一種方案，只要身份類似，就能正確解密呢？換句話說，只要身份中正確字元的個數超過了規定的閾值範圍，就能夠正確的解密。這種IBE方案稱為模糊IBE（Fuzzy IBE, FIBE），這個概念由Sahai和Waters提出。值得注意的是，FIBE現在已經擴展為了更厲害的屬性基加密方案（Attribute-Based Encryption），並且在雲存儲中得到了廣泛的應用。

下一個問題是效率問題。現今的IBE方案基本都是基於雙線性群（Bilinear Group），而雙線性群的乘法和指數運算實際上是比較慢的。我曾經嘗試過，如果在三星S2的手機上運行雙線性群的指數運算，大概需要40ms的時間。那麼，如果加密過程是在移動終端完成的，那麼加密的時間就會非常的長。一種減少加密時間的方法叫做Online/Offline技術。這種技術的基本原理是，在設備空閑時，我們先在未給定接收者（也就是不知道接收用戶身份）時把所有涉及到的乘法和指數運算算完，生成一個中間密文（intermediate ciphertext）。在給定接收者後，我們可以利用這個中間密文快速算出最終密文，計算過程不涉及指數運算和乘法運算。這樣一來，加密的時間就會大大減少。這種IBE方案稱為Online/Offline IBE（OO-IBE）。這個方案的提出者是中國學者Guo等人[12]。這種Online/Offline技術現在也被用在了ABE中[13]。

當然了，IBE中還有很多其他的問題，如Revocable IBE（RIBE），Selective Opening Secure IBE，CCA2-secure IBE等等。在下方參考文獻中的Related Work部分，對上面的內容都有大概的介紹，有興趣的朋友們可以進一步了解和學習。

===============================分割線==================================

4 IBE的應用

Boneh和Franklin的論文[2,3]中已經詳細寫明了IBE的應用。既然題注關注IBE在Email中的應用，我也在此把Boneh和Franklin論文的一部分原文粘貼在此處。值得注意的是，Boneh最近有個剛完成的Project，就是Identity Based Encryption email system (IBE secure email)。Boneh的主頁為Dan Boneh，感興趣的朋友們可以關注一下。

Shamir"s original motivation for identity-based encryption was to simplify certificate management in e-mail systems. When Alice sends mail to Bob at bob@hotmail.com, she simply encrypts her message using the public key string "bob@hotmail.com". There is no need for Alice to obtain Bob"s public key certificate. When Bob receives the encrypted mail he contacts a third party, which we call the Private Key Generator (PKG). Bob authenticates himself to the PKG in the same way he would authenticate himself to a CA and obtains his private key from the PKG. Bob can then read his e-mail. Note that unlike the existing secure e-mail infrastructure, Alice can send encrypted mail to Bob even if Bob has not yet setup his public key certi cate. Also note that key escrow is inherent in identity-based e-mail systems: the PKG knows Bob"s private key.

以上…

===============================分割線==================================

參考文獻

[1] Shamir, A.: Identity-based cryptosystems and signature schemes. In: Blakely, G. R., Chaum, D. (eds.) CRYPTO 1984. LNCS, vol. 196, pp. 47-53. Springer, Berlin, Heidelberg (1985)

[2] Boneh, D., Franklin, M.: Identity-based encryption from the Weil pairing. In: Kilian J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 213-229. Springer, Berlin, Heidelberg (2001)

[3] Boneh, D., Franklin. M.: Identity-based encryption from the Weil pairing. In: Journal on Computing. Vol. 32(3), pp. 586-615. (2003)

[4] Boneh, D., Boyen, X.: E cient selective-ID secure identity-based encryption without random oracles. In: Cachin C., Camenisch, J. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 223-238. Springer, Berlin, Heidelberg (2004)

[5] Canetti, R., Halevi, S., Katz, J.: A forward-secure public-key encryption scheme. In: Biham E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 255-271. Springer, Berlin, Heidelberg (2003)

[6] Boneh, D., Boyen, X.: Secure identity-based encryption without random oracles. In: Franklin M. (ed,) CRYPTO 2004. LNCS, vol. 3152, pp. 443-459. Springer, Berlin, Heidelberg (2004)

[7] Waters, B.: E cient identity-based encryption without random oracles. In: Cramer R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 114-127. Springer, Berlin, Heidelberg (2005)

[8] Gentry, C.: Practical identity-based encryption without random oracles. In: Vaudenay S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 445-464. Springer, Berlin, Heidelberg (2006)

[9] Chen, J., Wee, H.: Fully, (Almost) Tightly Secure IBE and Dual System Groups. In: Canetti, R. Garay, J.A. (eds.) CRYPTO 2013. LNCS, vol. 8043, pp. 435-460. Springer, Berlin, Heidelberg (2013)

[10] Boneh, D., Raghunathan, A., Segev, G.: Function-Private Identity-Based Encryption: Hiding the Function in Functional Encryption. In: Canetti, R. Garay, J.A. (eds.) CRYPTO 2013. LNCS, vol. 8043, pp. 461-478. Springer, Berlin, Heidelberg (2013)

[11] Sahai, A., Waters, B.: Fuzzy identity-based encryption. In: Cramer R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 457-473. Springer, Berlin, Heidelberg (2005)

[12] Guo, F., Mu Y., Chen Z.: Identity-based online/offline encryption. In: Tsudik, G. (ed.) FC 2008. LNCS, vol. 5143, pp. 247-261. Springer, Berlin, Heidelberg (2008)

[13] Hohenberger, S., Waters, B.: Online/o ine attribute-based encryption. Accepted in PKC 2014. In: Cryptology e-Print Archive 2014. Available at: http://eprint.iacr.org/2014/021.pdf.

@劉巍然大哥不厚道啊，哈。我先過來拋磚引玉吧。

以下回答假設題主的目的是研究IBE的密碼學性質，而不是部署IBE。

在Boneh的這篇paper里

http://crypto.stanford.edu/~dabo/papers/bbibe.pdf

$extbf{IBE} = (Setup, Extract, Encrypt, Decrypt)$

An Identity-Based Encryption system (IBE) consists of four algorithms: Setup,
Extract, Encrypt, Decrypt. The Setup algorithm generates system parameters, denoted by params, and a master key mk. The Extract algorithm uses the master key to extract a private key corresponding to a given identity. The encryption algorithm encrypts messages for a given identity (using the system parameters) and the decryption algorithm decrypts ciphertexts using the private key.

具體來說，在BB-IBE里，僅滿足IND-sID-CPA安全性的整個加密/解密過程是這樣的：(圖片來自我自己做的Seminar Handout)，dID為解密用的私鑰。

若套進傳統的公鑰語言，則IBE可以表述為下面這個樣子 (不嚴謹，輕拍)

$(params, sk) leftarrow Gen(ID, mk) \ C leftarrow Enc(m,params, ID)\ m leftarrow Dec(C, params, sk)$

，Gen起的作用就是Setup和Extract，其中C是密文，m是明文，params中包含空開信息和公鑰， mk是指master key。

如果結合郵件系統使用IBE，則可選擇郵件地址作為ID，然後向密鑰分配伺服器申請針對這個ID的公、私鑰。

生成密鑰的過程中可能需要用到prf, elliptic curve, pairing等密碼學數學模型或概念。

這個問題的確很大，每一個primitive都可以深挖，每一個安全假設都可以考慮變換，每個安全性(CPA等)都能改進。

但驗證此ID使用者的身份和傳遞此密鑰不是IBE的內容。

另，google books上面可以找到Identity Based Encryption這本書，會有各種方案的完整敘述。

IBE的確不新了，但是最近幾年（截止到2014年初吧，因為後來就沒怎麼接觸了），隨著雲計算和移動設備的計算能力的普及，還是比較火的。

我來拓展一下劉巍然-學酥的答案和回答一下「網路安全中基於身份的密碼體制可以進行哪些領域的研究？」吧

2005 Sahai 和 Water 提出了 Fuzzy Identity-based Encryption [1]。引出了很多新的發展， Attribute-based Encryption （ABE）也是其中之一。ABE是基於屬性的加密，加密的文件會被一些屬性給標識，一個Attribute Authority（AA）負責issue private key 給用戶。一個用戶向AA申請私有秘鑰，私有秘鑰包含（用戶擁有的屬性和一個秘鑰）。所以ABE解密數據的過程包括兩個部分1，驗證屬性 2. 解密被加密的數據。

隨後ABE 朝著兩個方向發展Key-Policy ABE (KP-ABE) [2]和 Ciphertext-Policy ABE ( CP-ABE)[3]

1. KP-ABE ------ 加密數據，數據包括被加密的數據和 DO所要求標識的 attributes

------ 秘鑰，包括屬於申請者的一個 access policy 和一個秘鑰

a) 數據擁有者 DO - -〉加密數據，數據包括被加密的數據和 DO所要求標識的 attributes

b）數據請求者向 AA 申請自己的秘鑰

c）當數據請求者秘鑰的 access policy 和加密數據所標識的屬性 match後滿足

d）請求者可以解密數據

2. CP-ABE 和KP-ABE剛好相反。

------ 加密數據，數據包括被加密的數據和一個 access policy

------ 秘鑰，包括屬於申請者的所擁有的屬性集和一個秘鑰

a) 數據擁有者 DO - -〉加密數據，數據包括被加密的數據和 access policy

b）數據請求者向 AA 申請自己的秘鑰

c）當數據請求者秘鑰的屬性集和加密數據的 access policy match後滿足

d）請求者可以解密數據

所以你可以看到接下來的方向大部分是對這兩個方案的優化和完善。

1. AA 是被加密者和請求者信任的。容易成為被攻擊的對象所以Multy-Authority 多授權中心方案兩個很有代表性的文獻

a) Chase 的 Multi-authority attribute based encryption [4]， N個多授權中心合作，當最多有N-2個AA為真AA時，可以保證安全。但是每增加一個 AA，整個系統需要重啟，因為交互的秘鑰需要更新

b) Lewko he Waters [5] 的 decentralizing ABE 是個更靈活的解決方案， AA可以隨時加入和退出而不需要整個範圍的重啟，但是太慢，現在應該已經更新並提高速度了

2. AA的存在使得Attributes多為靜態數據， dynamic attributes 的引入也是一個方向

3. 因為技術多用於雲環境，所以匿名技術的代入（access policy 的匿名和 attributes的匿名）

4. 因為Pairing-based Computing 其實還是挺重的計算，所以優化計算，以及在移動環境的應用都是方向

5. 複雜靈活的access policy。其餘的回答提到的認真身份「只要身份中正確字元的個數超過了規定的閾值範圍」這個方法是基於Sahai和Waters的policy evaluation 是基於searet shareing來解決的「how to share a secret」 [6]，比較簡單的與門操作，不安全。基於PBC 計算的複雜policy 的高效實現也是一個方向（二次修改）

6. 除了雲環境， IBE 在車聯網裡的研究也是很廣泛的，可以關注

7. ABE 的秘鑰回收一個一個大問題

回答的太晚了，可能樓主已經不需要了。也算是對自己知識的一些大概回顧，希望能幫到有需要的朋友。

以上，歡迎指正

References：

[1]Sahai A, Waters B. Fuzzy identity-based encryption[M]//Advances in Cryptology–EUROCRYPT 2005. Springer Berlin Heidelberg, 2005: 457-473.

[2]Goyal V, Pandey O, Sahai A, et al. Attribute-based encryption for fine-grained access control of encrypted data[C]//Proceedings of the 13th ACM conference on Computer and communications security. Acm, 2006: 89-98.

[3]Bethencourt J, Sahai A, Waters B. Ciphertext-policy attribute-based encryption[C]//Security and Privacy, 2007. SP"07. IEEE Symposium on. IEEE, 2007: 321-334.

[4]Chase M. Multi-authority attribute based encryption[M]//Theory of cryptography. Springer Berlin Heidelberg, 2007: 515-534.

[5]Lewko A, Waters B. Decentralizing attribute-based encryption[M]//Advances in Cryptology–EUROCRYPT 2011. Springer Berlin Heidelberg, 2011: 568-588.

[6]Shamir A. How to share a secret[J]. Communications of the ACM, 1979, 22(11): 612-613.

咳咳咳，終於可以謝邀一把！來的有點晚。發現樓上大神已經回答的相當豐富和nice。

從理解的角度：IBC（ID-based Cryptography）就是把用戶自定義的一個字元串（在這裡可以是ID/email/IP address等）當成公鑰的密碼學，這樣避免了傳統的公鑰密碼學使用的方法：即用證書把公鑰和身份做綁定。

從學習的角度：要區分基於配對運算的密碼學和基於身份的密碼學的關係，個人感覺：基於對的密碼學包括基於身份的，基於身份的加密演算法和簽名演算法都有固定的、已證明安全的步驟，所以大多數的學習都是。。。。。。按部就班。。。