如何在這個單比特 PKE 方案中進行解密？

考慮一個循環群 $ G $ 有秩序的 $ q $ ， 然後讓 $ g $ 成為發電機 $ G $ . 認為 $ (G, q, g) $ 是公開的。考慮以下 1 位公鑰加密方案。

至 $ generate (pk,sk) $ :

1. $ x \xleftarrow{$} {1, , 2, . . . , q} $
2. $ h ← g^x $
3. $ pk ← h, sk ← x $
4. 返回 $ (pk, sk) $

加密消息 $ M = 0 $ ，我們定義 $ E_{pk}(0) $ 作為：

1. $ y\xleftarrow{$} {1, 2, . . . , q} $
2. 返回 $ (g^y, h^y) $

加密消息 $ M = 1 $ ，我們定義 $ E_{pk}(1) $ 作為：

1. $ y\xleftarrow{$} {1, 2, . . . , q} $
2. $ z\xleftarrow{$} {1, 2, . . . , q} $
3. 返回 $ (g^y, g^z) $

定義 $ D_{sk}(C) $ 並證明這個 1 位公鑰加密方案是 $ IND-CPA $ 如果 DDH 假設成立，則安全 $ (G, g) $ . （要清楚，這意味著做一個歸約。）（為什麼沒有人在實踐中真正使用這個方案？）

我還沒有想出正確的解密方法。我想證明它是 $ IND-CPA $ 安全將遵循 ElGamal 安全證明。我說得對嗎？

實際上，我認為這用得併不多，因為 1 位加密所涉及的工作乘以消息中的位數將比使用多位加密的替代選項大得多。我是對的嗎？

要解密，您基本上採用 $ g^y $ 組件並將其提升為密鑰，獲得 $ g^{yx} $ . 現在，如果這個值等於密文的第二部分，你可以看到 $ M $ 必須為 0，因為 $ g^{yx} = h^y $ ; 否則， $ M $ 是 1。

關於證明：是的，它與 ElGamal 非常相似，因為您必須使用 DDH 元組構造挑戰密文。

引用自：https://crypto.stackexchange.com/questions/34029