# [IBE] Identity-Based Cryptosystems and Signature Schemes

###### tags: `節點`
###### [:Link:論文連結 Identity-Based Cryptosystems and Signature Schemes](https://link.springer.com/content/pdf/10.1007/3-540-39568-7_5.pdf)
###### [:Link:論文連結 Efficient Identity-Based Encryption Without Random Oracles (standard model IBE)](https://eprint.iacr.org/2004/172.pdf)

## 名稱: Identity-Based Cryptosystmes and Signature Schemes

### 1. 簡介
公開金鑰密碼學(Public Key Cryptography, PKE)，是一種為了解決對稱式金鑰加密系統(Symmetric Key Encryption, SKE)的金鑰問題而誕生的一種機制。

在這樣的一個PKE機制中，我們主要是透過**公開金鑰(public key)加密，使用私密金鑰(secret key)解密**。在這樣的機制中，我們可以以一對欲通訊的Sender-Alice和Reciever-Bob來說明機制是如何運作的。
- 首先，Reciever-Bob的公鑰通常是一段由亂碼組成的字串並公開於網路上，方便Sender-Alice取得以進行對明文訊息的加密。
- 當Sender-Alice使用這把公鑰加密好的密文送達Reciever-Bob手上後，Reciever-Bob便可以用這把公鑰對應到的唯一一把私鑰解開這篇密文以獲得訊息明文。

這樣的過程中，我們會發現一個問題-「對於Sender-Alice而言，要怎麼確保在網路上取得的公鑰真的是屬於通訊另一端的Reciever-Bob的呢?」這麼說，可能還沒辦法讓讀者深切地感受到這個問題的痛點。我們更進一步地敘述這個問題-「今天可能有惡意的第三方聲稱自己有Bob的公鑰並發布於
::: info
1. 欲解決的問題:
- 最乾淨的PKE架構裡，取得的公鑰可能會有「無法確認其所屬人的身分」的問題
- 搭配PKI架構的PKE，利用第三方的授權及驗證單位(CA)頒布的憑證去證明公鑰真的屬於其所屬人
- 在上述的機制中，我們每次的加密動作都需先經過跟第三方確認才能安全的進行加解密
3. 角色
:::spoiler
1. Sender
2. Receiver
3. KGC (Key Generation Center)
:::
3. 演算法
:::spoiler

:::

4. 圖
[IBE 圖解]
5. 應用及未來展望
:::spoiler

:::
6. 缺點
:::spoiler

:::
:::

## 名稱: Efficient Identity-Based Encryption Without Random Oracles

### 介紹
::: info
1. 欲解決的問題:
- 原本IBE是在random oracle下完成安全性證明，但是random oracle model並不能取代真正的random function，其安全性相較於沒有使用random oracle model的架構更低，因此本篇是Boneh基於上一篇IBE，在不使用random oracle的條件下完成安全性證明
2. 角色
:::spoiler
1. Sender
2. Receiver
3. KGC (Key Generation Center)
:::
3. 演算法
:::spoiler

:::

4. 圖
[IBE 圖解]
5. 應用及未來展望
:::spoiler

:::
6. 缺點
:::spoiler

:::
:::

##
##
### 難題假設
:::info

:::
##
### 常見安全模型
:::info

:::

## 問題集
:::info
1. Adi Shamir提出的IBE，為什麼RSA不符合他所提出的兩項特性?
>[name=煒甯] Shamir的兩項重要特性是，知道系統sk的人可以做出使用者sk；不知道系統sk的人，就算同時有使用者pk和sk也無法回推系統sk。在RSA中，我們將其改寫成IBE的模式的話需要先定義其system secret key。分成兩種可能改寫的case。case 1是將兩個質數p、q相乘所得的N當作system secret key。則此N是經由random function產生。如此一來，即便是KGC得到了N也會因為無法拆解其p、q而導致無法製造出使用者的sk。case 2是N公開，p、q當作系統sk，能得到N、sk、pk的狀況下可以回推出p、q。故RSA不符合Shamir提出的兩項特性。
2. 在adi shamir的IBE還會有ID無法驗證其來源的問題嗎?(ABE欲解決的問題)
3. 為什麼Standard model下的IBE的ID要以vector來表示?
>[name=育靜] 論文p.2第一段提到Canetti[CHK03, CHK04]建構selective identity IBE without the random oracle model，但是這個架構下的ID使用bit string來表示ID，使得在做bilinear map computation的時候要對每一個bit做運算，比較沒有效率，因此Boneh這篇的ID用vector表示
>這篇給我的感覺是Boneh想做without random oracle model的IBE，然後他找到Canetti的證明符合他的這個期待，但是運算上又太沒有效率，於是他又找到HIBE是運算比較有效率的系統，於是他就結合Canetti的想法跟HIBE，做出一個有效率又是without random oracle model的IBE :+1:

4. 什麼是 Decision BDHI?

5. 什麼是fully secure?
>[name=敏傑] 去追[[BB04]](https://eprint.iacr.org/2004/173.pdf?fbclid=IwAR3FSkH3yYlc79qo-78h9PMBtJhTt7TMjZWC8BrSrA-c0mFx-dcTNQqrNu8)
>We present a fully secure identity based encryption scheme whose proof of security does not rely on the random oracle heuristic.

6. 補充裡面Decrypt演算法的$e(d_1, c_1)/e(d_2, c_2)=e(g_1, g_2)^t$怎麼推?
>[name=丁哥] $e(d_1, c_1)/e(d_2, c_2)$
>$=e(g_2^\alpha(g_1^vh)^r, g^t)/e(g^r, (g_1^vh)^t)$
>$=e(g_2^\alpha,g^t)e((g_1^vh)^r,g^t)/e(g^r, (g_1^vh)^t)$
>$=e(g_2^\alpha, g^t)=e(g^\alpha, g_2)^t=e(g_1, g_2)^t$
>
>加法群和乘法群的拆解結果是相同的，只是群的運算子不同
>$e(AB, C)=e(A, C)e(B, C)$
>$e(A+B, C)=e(A, C)e(B, C)$
:::

## 5/10補充
1. 討論為什麼需要做三方的秘密交換及如何做?
很簡單的 Diffie-Hellman Key Exchange 的延伸
Diffie-Hellman: Alice 挑選 x, 公開 g^x, Bob 挑選 y，公開 g^y
然後兩個人就可以共享 g^(xy) 這個祕密

Joux:
Alice 挑選 x, 公開 g^x, Bob 挑選 y, 公開 g^y, Carol 挑選 z, 公開 g^z
然後三個人就可以共享 e(g,g)^(xyz) 這個祕密
Alice: e(g^y, g^z)^x = e(g,g)^(xyz)
Bob: e(g^x, g^z)^y = e(g,g)^(xyz)
Carol: e(g^x, g^y)^z = e(g,g)^(xyz)
有這樣的方法之後我們可以用它來交換三方(系統、sender、Reciever)的祕密值

投影片裡想要講的東西是：
Sender 想要和 Receiver 交換資料，當然需要像是 ElGamal 一樣交換祕密，但是 ElGamal 中 Receiver 的 public key 是 g^x，Receiver 自己知道祕密 x，所以交換祕密很簡單
在 IBE 中 Receiver 的 public key 是 H(ID)， 如果把他當成 g^x 當然就可以像 ElGamal 一樣交換祕密了，但是這是不能運作的概念，因為這個時候 Receiver 不知道 H(ID) 對應的 x

所以換一個想法，因為 PKG 是一個太上皇，他知道所有的祕密，所以 Sender 和 PKG 交換祕密吧，這樣子只需要 Diffie Hellman 就夠了，也不需要 pairing，而且資料要交給誰也沒有指定

進一步的想法就是 Sender, Receiver, PKG 來交換祕密吧，這個祕密是 e(H1(ID), g^s)^r 這個時候 Sender 和 PKG都可以算出祕密，而且也有指定 Receiver，問題是 Receiver 自己算不出這個祕密，還好 PKG 可以把這個計算祕密的能力委託給他，也就是 H1(ID)^s，Receiver 就可以計算 e(H1(ID)^s,g^r) 來得到隱藏訊息的祕密 e(H1(ID), g^s)^r 了

2. 繼續討論Standard model的部分
老師投影片 P38-40頁。