公鑰在 coNP 中意味著什麼
我正在讀這篇論文。
在第 2 頁上提出了以下聲明：考慮具有確定性加密算法的公鑰加密方案，並假設有效公鑰集在 coNP 中。那麼如果從（密文，公鑰）對中檢索明文是 NP-Hard 則 NP = coNP。
我想我不完全理解的是一組公鑰在 co-NP 中意味著什麼？可能有一個直覺的例子嗎？
- NP是一組可有效驗證的決策問題。給定一個實例 $ x $ 關於決策問題，有一個簡短的“證明” $ w $ 那，給定這對 $ (x, w) $ , 可以有效地驗證 $ x $ 是真的。
- coNP是一組可有效反駁的決策問題。給定一個實例 $ x $ 對於決策問題，有一個簡短的“反證明” $ w $ 那，給定這對 $ (x, w) $ , 可以有效地驗證 $ x $ 是假的。
對於基本上所有已知的公鑰加密方案，公鑰形成一個 NP 集。這是什麼意思？給定一些公鑰 $ pk $ , 還有一些附加資訊 $ sk $ （密鑰），以便人們可以有效地驗證 $ pk $ 是相對於密鑰的公鑰 $ sk $ . 例如
- 對於 RSA， $ N = pq $ . 鑑於一些 $ N’ $ 可能會或可能不會採取這種形式，我們可以通過見證人有效地驗證它 $ (p, q) $ .
- 對於 DLOG 類型假設，給定一些 $ (g, g^s) $ ，我們同樣可以有效地驗證 $ g^s $ 通過見證人採取這種形式 $ s $
- 對於基於格/程式碼的方案，給定一些 $ (A, As + e) $ ，我們可以有效地驗證 $ (As + e) $ 通過見證人採取這種形式 $ (s, e) $ .
這就是說，給定一些 PKE 的密鑰，通常很容易驗證公鑰的結構是否正確（而不僅僅是一些隨機元素）。
現在，如果給定一些“ $ pk $ “這不是公鑰（而只是一些“隨機元素”），可以有效地驗證這一點。例如，對於 RSA，如果有人給你一些 $ N $ 不能寫成_ $ N = pq $ ，您可以通過完全分解來有效地驗證這一點 $ N = \prod_i p_i^{e_i} $ . $ ((p_1, e_1),\dots,(p_k,e_k)) $ 因此作為見證 $ N $ 不是RSA 公鑰，從這個意義上說，RSA 公鑰既是 NP 集又是 coNP 集。
該部分論文的主張是前提條件
加密是確定性的，公鑰集形成一個 conNP 集。
是限制性的。我個人認為第一部分比第二部分更具限制性。例如，在我看來，在我上面提到的所有三個範例中，公鑰都形成了一個 coNP 集。在前兩個例子中很明顯，在第三個例子中，我認為足夠強的基礎減少可以/應該作為見證，特別是如果 $ B $ 是對偶的足夠短的基礎 $ \mathcal{L}(A) $ ， 然後 $ (BAs + Be) $ 對於“真正的 LWE”樣本，將是一個異常短的向量，但對於隨機樣本將是均勻隨機的，例如，將是一個 coNP 見證。