ElGamal变体

Question

我在阅读Katz和Lindell的“现代密码学概论”时遇到了这个问题。我对密码很陌生，我只是试着翻阅这本书，解决这些问题，不幸的是，我被困在了这个问题上。

请考虑以下公钥加密方案。公钥为(G, q, g, h)，私钥为x，与El加密方案完全相同。为了加密位b，发送方执行以下操作：

• 如果b = 0，然后选择一个统一的y ∈ Z_{q}并计算c_{1} := g^{y}和c_{2} := h^{y}。密文是(c_{1} , c_{2}) 。
• 如果b = 1然后选择独立的统一y,z ∈ Z_{q}，则计算c_1 := g^{y}和c_{2} := g^{z}，并将密文设置为(c_{1},c_{2})。

表明有可能有效地解密已知的

x

。

会很感激你的帮助

Answer 1

要确定来自(c_1,c_2)的比特明文，请使用x-th的c_1功能。我们不知道有两种选择

1. (c_1,c_2) = (g^y,h^y)然后(c_1^x,c_2) = (g^{xy},g^{xy})
2. (c_1,c_2) = (g^y,g^z)然后(c_1^x,c_2) = (g^{xy},g^{z})

现在检查一下是否是c_1^x = c_2。

• 如果它们相等，则大于位b=0
• 如果它们不等于位b=1。

我们将g^{xy}=g^{z}作为假b=0的可能性很小。这个事件的概率是1/g。

运算成本:如果我们用从左到右的二进制方法进行模幂，成本是\mathcal{O}(\log(x))，因此它是有效的。