52 Things: Number 31: Game Hopping Proof

52件事：數字31：游戲跳躍證明

This is the latest in a series of blog posts to address the list of '52 Things Every PhD Student Should Know To Do Cryptography': a set of questions compiled to give PhD candidates a sense of what they should know by the end of their first year. In this post we give an example of a proof that uses the 'game hopping' technique.
這是一系列博客文章中的最新一篇，旨在解決“每個博士生在做密碼學時應該知道的52件事”：這是一組問題，旨在讓博士生在第一年結束時了解他們應該知道什么。在這篇文章中，我們給出了一個使用“游戲跳躍”技術的證明例子。

Note, this blog post is based on Section 3.3 of 'An Introduction to Provable Security' by Douglas Stebila, downloadable via this link.
請注意，這篇博客文章基于Douglas Stebila的“可驗證安全簡介”第3.3節，可通過此鏈接下載。

Recall the definition of IND-CCA security for a public key encryption scheme, described by Ana here. If one removes the decryption oracle from the adversary, we obtain the IND-CPA (indistinguishability under chosen-plaintext attacks) security notion. Note that removing the encryption oracle does not change the adversary's view since it holds the public key and can therefore produce its own encryptions.
回想一下Ana在這里描述的公鑰加密方案的IND-CCA安全性的定義。如果從對手那里移除解密預言符，我們就獲得了IND-CPA（在選擇的明文攻擊下的不可區分性）安全概念。請注意，刪除加密預言機不會改變對手的觀點，因為它持有公鑰，因此可以產生自己的加密。

In an earlier blog post, we described the Decisional Diffie-Hellman (DDH) problem. In this post, we are going to use a technique called 'game hopping' to show that the ElGamal encryption scheme is IND-CPA secure if DDH is hard. Loosely speaking, we will transform the IND-CPA game against ElGamal into a game against DDH and show that an adversary's advantage in the first game cannot be more than their advantage in the second. So if their advantage in the second game is negligible (which is the assumption that DDH is hard), the advantage in the first game must also be negligible (showing that the encryption scheme is IND-CPA secure).
在之前的一篇博客文章中，我們描述了決策Diffie-Hellman（DDH）問題。在這篇文章中，我們將使用一種名為“游戲跳躍”的技術來表明，如果DDH很難，ElGamal加密方案是IND-CPA安全的。不嚴格地說，我們將把IND-CPA與ElGamal的比賽轉變為與DDH的比賽，并表明對手在第一場比賽中的優勢不能超過他們在第二場比賽的優勢。因此，如果他們在第二場比賽中的優勢可以忽略不計（這是假設DDH是硬的），那么第一場比賽的優勢也必須是可以忽略不計的（表明加密方案是IND-CPA安全的）。

Firstly, let's describe the ElGamal scheme. We work in a cyclic group G of prime order q with generator g. (Implicitly the selection of the group depends on a security parameter λ and when we say that a quantity is negligible, we mean a negligible function of λ, but we'll omit those details here.) Plaintexts and ciphertexts are group elements. The private key is a secret exponent x∈Zq and the public key is X=gx. To encrypt a message M∈G, one selects an exponent y∈Zq uniformly at random, computes c1=gy, c2=MXy and the ciphertext is the pair (c1,c2). To decrypt, notice that c2=MXy=M(gx)y=M(gy)x=Mcx1 so, with the private key x we just compute M=c2c?x1.
首先，讓我們來描述ElGamal方案。我們在素數階為 q 的循環群 G 中與生成器 g 一起工作。（隱含地說，組的選擇取決于安全參數 λ ，當我們說一個量可以忽略不計時，我們指的是#4的一個可以忽略不計的函數，但我們在這里省略這些細節。）明文和密文是組元素。私鑰是秘密指數 x∈Zq ，公鑰是 X=gx 。為了加密消息 M∈G ，隨機均勻地選擇指數 y∈Zq ，計算 c1=gy 、 c2=MXy ，并且密文是對 (c1,c2) 。要解密，請注意 c2=MXy=M(gx)y=M(gy)x=Mcx1 ，因此，使用私鑰 x ，我們只計算 M=c2c?x1 。

Now consider the following game Game0 played by a PPT adversary A.
現在考慮下面由PPT對手 A 玩的游戲 Game0 。

x←$Zq,X←gx (generate the public, private key pair)
x←$Zq,X←gx （生成公鑰、私鑰對）
(M0,M1)←$A(X) (the adversary, in possession of the public key, produces a pair of challenge messages, possibly using a randomised process)
(M0,M1)←$A(X) （擁有公鑰的對手可能使用隨機過程生成一對挑戰消息）
b←${0,1} (a random bit is chosen)
b←${0,1} （隨機選擇一位）
y←$Zq,c1←gy,Z←Xy,c2←MbZ (an encryption of message b is produced)
y←$Zq,c1←gy,Z←Xy,c2←MbZ （生成對消息 b 的加密）
b′←$A(c1,c2) (the adversary, in possession of the ciphertext, produces a bit, possibly using a randomised process)
b′←$A(c1,c2) （擁有密文的對手可能使用隨機過程產生一個比特）
if b=b′ then return 1, else return 0.
如果 b=b′ ，則返回1，否則返回0。

We say A wins Game0 if the game returns 1. From the definition in Ana's blog, it should be clear that the advantage of A against the IND-CPA security of ElGamal (with parameters G, q and g) is 2|Pr[AwinsGame0]?1/2| (1).
如果游戲返回1，我們說 A 贏得 Game0 。根據Ana博客中的定義，應該清楚的是，#2相對于ElGamal的IND-CPA安全性（參數為#3、#4和 g ）的優勢是 2|Pr[AwinsGame0]?1/2| （1）。

Next, consider a new game Game1. This game is exactly as above, except that in Step 4, we replace the command
接下來，考慮一個新游戲 Game1 。這個游戲和上面完全一樣，只是在步驟4中，我們替換了命令

Z←Xy

z←$Zq,Z←gz.

So the new ciphertext is (c1,c2)=(gy,Mbgz) instead of (c1,c2)=(gy,Mbgxy).
所以新的密文是 (c1,c2)=(gy,Mbgz) 而不是 (c1,c2)=(gy,Mbgxy) 。

Again we say A wins this game if it returns 1. What is the probability that this happens? Note that Z is now a totally random group element by the randomness of z∈Zq. So c2 is also a random group element, independent of X, c1 and b. So the adversary gains no information about b from (c1,c2), meaning it outputs the correct bit and wins the game with probability exactly 1/2 (2).
我們再說一次，如果它返回1， A 將贏得這場比賽。發生這種情況的可能性有多大？注意， Z 現在是一個完全隨機的組元素，其隨機性為 z∈Zq 。所以#3也是一個隨機群元素，獨立于#4、 c1 和 b 。因此，對手沒有從 (c1,c2) 中獲得關于 b 的信息，這意味著它輸出了正確的比特，并以恰好1/2（2）的概率贏得了游戲。

Now we bound the difference in probability for an adversary to win each of the games. Since the only difference in the two games is that the group element gxy is replaced by a random group element gz, it is easy to see how this relates to the DDH problem, where an adversary must distinguish between the triples (gx,gy,gxy) and (gx,gy,gz) for a random exponent z∈Zq. To make the link between the games precise, we use the adversary A to build an adversary B against DDH as follows:
現在我們確定了對手贏得每一場比賽的概率差異。由于這兩個游戲中唯一的區別是組元素 gxy 被隨機組元素 gz 取代，因此很容易看出這與DDH問題有何關系，其中對手必須區分隨機指數#4的三元組#2和#3。為了使游戲之間的聯系更加精確，我們使用對手 A 來構建一個對抗DDH的對手 B ，如下所示：

On input (X,Y,Z), run A on input X to receive a challenge pair (M0,M1)
在輸入 (X,Y,Z) 上，在輸入#2上運行 A 以接收挑戰對 (M0,M1)
Select a bit b uniformly at random and compute mbZ
隨機均勻選擇一個比特 b 并計算 mbZ
Give the 'ciphertext' (Y,mbZ) to the A and receive a bit b′
將“密文” (Y,mbZ) 提供給 A ，并接收比特 b′
If b=b′, guess that Z=gxy and return 1, else guess Z is random so return 0.
如果 b=b′ ，則猜測 Z=gxy 并返回1，否則猜測 Z 是隨機的，則返回0。

If B is given a real Diffie-Hellman triple (gx,gy,gxy) then the above is a perfect simulation of A playing Game0, and if B is given a fake triple (gx,gy,gz) then it is a perfect simulation of A playing Game1. Therefore, the difference between the probability of A winning Game0 and A winning Game1 is precisely the difference between the probability that B outputs 1 on input (gx,gy,gxy) and outputs 1 on input (gx,gy,gz), which is exactly the advantage of B against DDH.
如果 B 被給予真實的Diffie-Hellman三元組 (gx,gy,gxy) ，則上述是#2玩#3的完美模擬，并且如果#4被給予偽三元組 (gx,gy,gz) ，則其是 A 玩 Game1 的完美模擬。因此， A 贏得 Game0 和 A 贏得 Game1 的概率之間的差正是 B 在輸入 (gx,gy,gxy) 上輸出1和在輸入 (gx,gy,gz) 上輸出1的概率之間之差，這正是 B 對抗DDH的優勢。

Combining the above with facts (1) and (2) (and using the triangle inequality to take care of the modulus signs), we can easily obtain that the advantage of A against the IND-CPA security of ElGamal is no greater than the advantage of B against DDH. So if DDH is hard for all polynomial time adversaries (meaning their advantage is negligible), ElGamal must be IND-CPA secure.
將以上內容與事實（1）和（2）相結合（并使用三角不等式來處理模符號），我們可以很容易地獲得 A 對抗ElGamal的IND-CPA安全性的優勢不大于 B 對抗DDH的優勢。因此，如果DDH對所有多項式時間的對手都很難（意味著他們的優勢可以忽略不計），那么ElGamal必須是IND-CPA安全的。

posted @ 2024-04-12 21:32 3cH0_Nu1L 閱讀(80) 評論(0) 收藏舉報

刷新頁面返回頂部

3cH0_Nu1L

52 Things: Number 31: Game Hopping Proof

52 Things: Number 31: Game Hopping Proof

52件事：數字31：游戲跳躍證明

公告