為什麼對 Naor-Yung 方案的簡化版本的這種攻擊不適用於原始方案？
tl;dr：我們得到了一個作業，我們應該在其中討論在 Naor-Yung 方案中加密兩次是否真的有必要。我可以通過在只加密一次的方案上建構攻擊者來證明它是。但是，在我看來，好像這種攻擊也可以在原始版本上起作用。這顯然是錯誤的。我想知道我錯在哪裡。
我們目前正在一次講座中討論Naor-Yung 方案，並獲得了以下作業：
考慮 CPA 安全的 PKE $ \Pi_1 := (\mathsf{Gen}_1, \mathsf{Enc}_1, \mathsf{Dec}_1) $ , 語言 $$ \begin{align*} \mathcal{L} := \left{ (\mathsf{ek},c) \mid \exists m,s : \mathsf{Enc}_1(\mathsf{ek},m;s) = c \right} \in \mathcal{NP} \end{align*} $$ （在哪裡 $ s $ 是隨機磁帶）和 NIZK $ (\mathsf{V}, \mathsf{P}) $ 為了 $ \mathcal{L} $ .
我們定義一個新的 PKE $ \Pi = (\mathsf{Gen}, \mathsf{Enc}, \mathsf{Dec}) $ 如下：
- $ \mathsf{Gen}(1^n) $ :
+ $ (\mathsf{dk}’, \mathsf{ek}’) \leftarrow \mathsf{Gen}_1(1^n) $ + $ r \leftarrow \left{ 0,1 \right}^{\mathsf{poly}(n)} $ + $ \mathsf{ek} := (\mathsf{ek}’, r) $ + $ \mathsf{dk} := (\mathsf{ek}’, \mathsf{dk}’, r) $ + 返回 $ (\mathsf{ek}, \mathsf{dk}) $
- $ \mathsf{Enc}(\mathsf{ek}, m) $ + $ s \leftarrow \left{ 0,1 \right}^{\mathsf{poly}(n)} $ + $ c’ \leftarrow \mathsf{Enc}_1(\mathsf{ek’}, m; s) $ + $ \pi \leftarrow \mathsf{P}(r,(\mathsf{ek}’,c’),(m,s)) $ + 返回 $ c:=(c’, \pi) $
- $ \mathsf{Dec}(\mathsf{dk}, c) $ + 返回 $ \left{ \begin{array}{ll} \mathsf{Dec}_1(\mathsf{dk}’,c’) & \textrm{if } \mathsf{V}(r, (\mathsf{ek}’,c’), \pi) = 1 \ \bot & , \textrm{else} \ \end{array} \right. $
是 $ \Pi $ CCA1-安全？
所以基本上，問題是，加密兩次（如在 Naor-Yung 中）是否真的有必要。
我想出了以下解決方案：
我們採用 CPA 安全的 PKE $ \Pi_0 := (\mathsf{Gen}_0, \mathsf{Enc}_0, \mathsf{Dec}_0) $ 並定義 $ \Pi_1 := (\mathsf{Gen}_0, \mathsf{Enc}_1, \mathsf{Dec}_1) $ 和：
- $ \mathsf{Enc}_1(\mathsf{ek}, m) $
- $ t \leftarrow \left{0,1\right}^n $
- 返回 $ (c,t) := (\mathsf{Enc}_0(\mathsf{ek}, m),t) $
- $ \mathsf{Dec}(\mathsf{dk}, (c,t)) $
- 返回 $ \left{ \begin{array}{ll} \mathsf{dk} & \textrm{if } t = 0^n \ \mathsf{Dec}_0(\mathsf{dk},c)& , \textrm{else} \ \end{array} \right. $
很明顯，這種結構也是 CPA 安全的，因此我們可以在 $ \Pi $ .
使用 NIZK $ (\mathsf{V}_0, \mathsf{P}_0) $ 對於語言 $$ \begin{align*} \mathcal{L}_0 := \left{ (\mathsf{ek},c) \mid \exists m,s : \mathsf{Enc}_0(\mathsf{ek},m;s) = c \right} \in \mathcal{NP} \end{align*} $$ 我們為 NIZK 找到了一個簡單的結構 $ (\mathsf{V}, \mathsf{P}) $ 為了 $ \mathcal{L} $ . （簡而言之：我們可以簡單地省略隨機字元串 $ t $ 然後使用 $ \mathsf{V}_0 $ ， 分別 $ \mathsf{P}_0 $ .)
現在出現以下問題：如果 $ \pi $ 證明 $ (\mathsf{ek}, (c,t)) \in \mathcal{L} $ ， 然後 $ \pi $ 也證明 $ (\mathsf{ek}, (c,t’)) \in \mathcal{L} $ 對於任何 $ t’ \in \left{0,1\right}^n $ . 這允許 CCA1 攻擊者完全破壞 $ \Pi $ :
- 選擇隨機消息 $ m $ 併計算 $ ((c’,t),\pi) \leftarrow \mathsf{Enc}(\mathsf{ek},m) $
- 使用解密預言機計算 $ \mathsf{dk} \leftarrow \mathsf{Dec}(\mathsf{dk},((c’,0^n),\pi)) $
因此， $ \Pi $ 不是 CCA1 安全的。
現在我的問題。這不是作業的一部分，但它確實讓我感興趣：我認為，這種技術可以類似地應用於 Naor-Yung 方案，因為我無法弄清楚它會失敗的點。然而，我很清楚，它當然會失敗，因為我們已經在講座中證明了該方案是 CCA1 安全的。
那麼，我的技術在哪裡失敗了？
如果我不得不猜測，我會說，我的構造 $ (\mathsf{V}, \mathsf{P}) $ 也許不是ZK。
但是，我已經嘗試從區分器構造一個歸約 $ (\mathsf{V}_0, \mathsf{P}_0) $ 一個區分器 $ (\mathsf{V}, \mathsf{P}) $ ，以證明它實際上是一個 ZK 並且看不到，我可能會犯錯誤。（減少只是將隨機字元串附加到密文中。）
如果 $ \pi $ 證明 $ (ek,(c,t)) \in \cal L $ ， 然後 $ \pi $ 也證明 $ (ek,(c,t’)) \in \cal L $ .
的確如此 $ (ek,(c,t)) \in \mathcal L \implies (ek,(c,t’)) \in \mathcal L $ . 所以第一個表達式的證明也應該讓你相信第二個表達式。但這並不意味著在 NIZK方案中，第一個表達式的有效證明實際上也可以作為第二個表達式的證明。通常證明需要與被證明的特定語句緊密綁定，並且不能用於多個語句。
更一般地說，假設我們正在處理一種語言 $ \mathcal{L} $ 我們知道 $ x \in \mathcal L \iff f(x) \in \mathcal L $ 對於某些功能 $ f $ . （在我們的例子中 $ f $ 翻轉密文中的一些位。）您聲稱 $ \textsf{Ver}(x,\pi) =1 \implies \textsf{Ver}(f(x),\pi) $ 在 NIZK 方案中。如果這是真的，假設 NIZK 方案具有“雙重責任證明”屬性。
雙重責任證明會違反 NIZK 方案的標準屬性，稱為模擬健全性。模擬可靠性表明，即使在看到虛假陳述的模擬證明之後，對手也無法計算虛假陳述的證明。
假設攻擊者請求模擬證明 $ \pi $ 虛假陳述的 $ x \not\in \mathcal L $ . 然後 $ f(x) \not\in \mathcal{L} $ 要麼，但雙重責任證明屬性意味著 $ \pi $ 也驗證為（錯誤）陳述的證明 $ f(x) $ . 所以攻擊者可以很容易地找到一個虛假陳述的證據，違反了模擬的健全性。
所以即使我們看到一個證明 $ x \in \mathcal L $ , 我們知道這意味著 $ f(x) \in \mathcal L $ 而且，應該仍然很難拿出一個證明 $ f(x) \in \mathcal L $ . 這是因為證人 $ f(x) $ 與見證人有關 $ x $ . We should only be able to come up with a proof of $ f(x) \in \mathcal L $ by knowing the witness.
I don’t remember all the gory details of Naor-Yung right now, but I would not be surprised if it required some kind of simulation-soundness. The security proof has to give out proofs of false statements (when the two ciphertexts encrypt different things) while still preventing the attacker from decrypting bogus ciphertexts.