沒有多線性映射的專用見證加密
在見證加密及其應用中， Garg 等人描述了“見證加密”，它允許將一些指定的數據加密到 NP 問題，這樣另一方就可以在他們提供 NP 問題的見證時解密。
他們使用基於從 CNF 謂詞到子集和問題的 NP 減少的多線性映射給出一般構造。
在沒有多線性映射的情況下，是否存在可證明安全的較小類問題（例如，內積、點函式的原像或離散對數）的見證加密範例？
見證加密本質上與雜湊證明系統（有些人稱之為“平滑投影雜湊函式”）相同，所以我們知道很多例子。
最著名的可能是 Cramer-Shoup SPHF，它可以看作是關於 Diffie-Hellman 對的 NP 語言的見證加密方案。準確地說，我們有一個循環群 $ G $ 並考慮語言 $ L\subset G\times G $ 對 $ (g^w, h^w) $ ， 在哪裡 $ g,h $ 是兩個給定的生成器 $ G $ . 然後可以定義一個加密 $ m\in G $ 關於任意對 $ (u,v)\in G^2 $ 作為 $ (c_0,c_1)=(g^rh^s,m\cdot u^rv^s) $ 對於隨機指數 $ r,s $ . 如果 $ (u,v)\notin L $ 並且 DDH 假設成立 $ G $ , 很容易驗證 $ (g^rh^s, u^rv^s) $ 是均勻隨機的 $ G^2 $ ， 所以 $ m $ 在統計上是隱藏的。另一方面，如果 $ (u,v)\in L $ 並且有人知道這一事實的證人，即 $ (u,v)=(g^w,h^w) $ 並且知道 $ w $ ，那麼很容易解密：可以簡單地恢復 $ m $ 作為 $ c_1/c_0^w $ . 所以我們有一個需要的見證加密方案。
還有更多範例：SPHF 用於某些合適的承諾方案中的有效承諾語言等。
這是 Victor Shoup 本人關於這個主題的精彩演講：https ://www.youtube.com/watch?v=2aX-0E07Fpg