Witness Encryption 中可以使用一個 NP 語言 L（對應一個關係 R）的一個實例 x 加密一段訊息，對於知道某個 w 使 R(x, w) 成立的人可以解密，而若某 x 不存在於 L 中，則沒有多項式時間的攻擊者可以分辨任兩個具有相同長度原文的密文。值得注意的是，加密者不一定知道 x 是否存在於 L 中。[1] 以更白話的說法，我們可以找到一個 NP 問題，但不必要知道這個問題是否有解，而利用這個問題對某段訊息加密，接著交給可能知道的人解密。例如在 Goyal and Goyal[2] 中利用某筆紀錄對於某個 PoS 區塊鏈的存在條件中作為 NP 問題並對某電路進行加密，因此這個電路只有在區塊鏈將某筆紀錄上鏈後才可執行，也只能執行一次。
範例
考慮 NP 語言 L = \{ (a, b): A = g^a, B = g^b, T = g^{ab} \}。
使用 (g, A, B, T, G) 加密：
- 獨立隨機選擇
r_1, r_2 \in \Z_p^* - 計算
c_1 = A^{r_1}g^{r_2}, c_2 = g^mT^{r_1}B^{r_2}，其中m \in {0, 1}是要加密的訊息 - 輸出
c = (c_1, c_2)
解密時使用 \frac{c_2}{c_1^b}，展開得 \frac{g^mg^{abr_1}g^{br2}}{g^{(ar_1)b}g^{(r_2)b}}，消去得 g^m。
這裡的 a 是一個實例，b 是一個 witness，如果知道就可以用來解密。可以對照 ELGamal 加密法看，相當於 b 作為接收者的私鑰，a*r_1+r_2 作為發送者的隨機秘密。
在 Witness Encryption 中，我們需要確保如果 witness 不存在的狀況（即沒有一個 b 可以解開密文），攻擊者無法取得原文。從前面的 c_1, c_2 可以得到其對數 s_1, s_2 與：
ar_1 + r_2 = s_1 \\
m + rr_1 + br_2 = s_2而對於任意 m，若沒有 r = ab（前面提到沒有這個 witness）則有無窮多組解，因此無法取得原文。
也是範例，不過是 NP 完全
Exact Cover Problem
Exact Cover Problem 是一個 NP 完全問題，概念上是選定一集合 S 與一個由其子集合組成的集合 Z，尋找 T \subset Z 且所有 T 的成員互不重疊且完全涵蓋 S。形象化的範例是打亂兩組以上的撲克牌，並從選取牌數不定的數疊（Z = (Z_1, Z_2, ... ,Z_l)），從這些疊中找出一個組合（T = (Z_a, Z_b, ...)）可以還原成一組撲克牌（S = Z_a + Z_b + ...）。在知道 S, Z 的狀況下，找到 T 屬於 NP 完全問題。
多重線性映射與 m-MDDH 假設
多重線性映射定義為一組 \overrightarrow{\mathbb{G}} = (\mathbb{G_1}, \mathbb{G_2}, ..., \mathbb{G_n}) 且都具有夠大且為質數的階，這邊假設存在一組 Bilinear maps \{e_{i,j} : \mathbb{G_i} \times \mathbb{G_j} \rightarrow \mathbb{G_{i+j}} | i,j \geq 1; i+j \leq n\}且e_{i,j}(a_i^a, a_j^b) = g_{i+j}^{ab}。
m-MDDH 假設則說明對於一個任意元素 g_n^r，沒有輕易分辨是否等於 g_n^{s\Pi_{j\in[1, n]}c_j}。這個屬性使前面提及「攻擊者無法分辨密文」的特性得以落實在接下來的步驟。
Exact Cover 與 m-MDDH
現在我們使用前面的 Exact Cover Problem 的撲克牌範例作為 NP 語言，選定一個實例（l 疊撲克牌(Z_1, Z_2, ... ,Z_l)）以及一個多重線性映射的設定，其中階為質數 p，並對所有牌隨機選取一個在 \Z_p 上的數（因此總共選取 n = 54 個），再對於每一疊撲克牌計算 c_i = g_{|Z_i|}^{\Pi_{j\in Z_i}a_j}，就可以將兩者結合。
加密
有了這些東西後，我們可以隨機選擇一個 \Z_p^* 的數 r，並設計一個函數 d(m)，當 m = 1 時輸出 g_n^{\Pi_{j\in [n]} a_j}，m = 0 時輸出 g_n^r。把 (d, c_1,...,c_l) 傳出即可。
解密
拿到 (d, c_1, ..., c_l) 後，選擇可以形成 Exact Cover 的組合相乘，可以得到 \displaystyle \prod_{i\in T}g_{|S_i|}^{\prod_{i\in S_j}a_j}。展開並運算 Bilinear Map 運算後 |S_i| 部分會變成 n（由於是 Exact Cover，會等於所有疊的牌數的總和），上面則剛好是所有牌的相乘。（如果看不懂，手算一次就懂了 XD）
因為知道解的人可以比對算出的值與 d，從而分辨原始訊息應該是 0 或 1 來進行解密。
後記
原本想說當初沒看懂，想說來看一下，結果最後是把論文和別人的上課筆記[3]翻譯啊？但確實這個加密法相當有趣，有機會再把原論文讀深一點好了。（原諒我實在累了。）
Reference
- Garg, Sanjam, et al. “Witness Encryption and Its Applications.” Proceedings of the 45th Annual ACM Symposium on Symposium on Theory of Computing – STOC ’13, ACM Press, 2013, p. 467. DOI.org (Crossref), https://doi.org/10.1145/2488608.2488667.
- Goyal, Rishab, and Vipul Goyal. “Overcoming Cryptographic Impossibility Results Using Blockchains.” Theory of Cryptography, edited by Yael Kalai and Leonid Reyzin, vol. 10677, Springer International Publishing, 2017, pp. 529–61. DOI.org (Crossref), https://doi.org/10.1007/978-3-319-70500-2_18.
- Sanjam Garg, and Fotis Iliopoulos. 2014. lecture notes, CS 276 – Cryptography, UC Berkeley. https://people.eecs.berkeley.edu/~sanjamg/classes/cs276-fall14/scribe/lec18.pdf