BU CAS CS 538.
Discussion 3 Solution
Definition 3 from Homework 3. A distribution ensemble is an infinite sequence of distributions 𝒟 = {𝐷𝑛}𝑛∈𝑁, where each 𝐷𝑛 is a distribution. Ensemble 𝒟 is effectively samplable if the size of 𝐷𝑛 (as a Boolean circuit) is polynomial in 𝑛. If there exists a polytime algorithms 𝐷 such that 𝐷(1𝑛, 𝑟) = 𝐷𝑛(𝑟) for all 𝑟 then 𝒟 is efficiently samplable. In this case we say that 𝒟 is generated by 𝐷.
Definition 5 from Homework 3. Distribution ensembles 𝒳 = {𝑋𝑛}𝑛∈𝑁 and 𝒴 = {𝑌𝑛}𝑛∈𝑁 have computational distance at most 𝛿(𝑛) if for any feasible distinguishing algorithm 𝒜 = {𝐴𝑛}𝑛∈𝑁, and for all large enough 𝑛 ∈ 𝑁, we have
Copyright By PowCoder代写 加微信 powcoder
Pr[𝑠←$ 𝑋𝑛,𝐴𝑛(𝑠)=1]−Pr[𝑠←$ 𝑌𝑛,𝐴𝑛(𝑠)=1]<𝛿(𝑛). If 𝛿(𝑛) is a negligible function then we say that ensembles 𝒳 , 𝒴 are computationally indistinguishable, denoted 𝒳 ≈𝑐 𝒴. Problem 1. Prove the transitivity for computational indistinguishability. i.e. Prove that if 𝒳 ≈𝑐 𝒴 and 𝒴 ≈𝑐 𝒵, then 𝒳 ≈𝑐 𝒵 for any distribution ensembles 𝒳,𝒴,𝒵. Solution. For any feasible distinguishing algorithm 𝐴𝑛 and large enough 𝑛, let 𝜀1(𝑛):=Pr[𝑠←$ 𝑋𝑛,𝐴𝑛(𝑠)=1]−Pr[𝑠←$ 𝑌𝑛,𝐴𝑛(𝑠)=1] 𝜀2(𝑛):=Pr[𝑠←$ 𝑌𝑛,𝐴𝑛(𝑠)=1]−Pr[𝑠←$ 𝑍𝑛,𝐴𝑛(𝑠)=1] Since 𝒳 ≈𝑐 𝒴 and 𝒴 ≈𝑐 𝒵, we have that 𝜀1(𝑛) and 𝜀2(𝑛) must be smaller than 𝜈(𝑛) for all large Pr[𝑠←$ 𝑋𝑛,𝐴𝑛(𝑠)=1]−Pr[𝑠←$ 𝑍𝑛,𝐴𝑛(𝑠)=1]=𝜀1(𝑛)+𝜀2(𝑛) enough 𝑛, where 𝜈(𝑛) is a negligible function. Thus: Pr[𝑠←$ 𝑋𝑛,𝐴𝑛(𝑠)=1]−Pr[𝑠←$ 𝑍𝑛,𝐴𝑛(𝑠)=1]≤2𝜈(𝑛). Since 2𝜈(𝑛) is negligible, 𝒳 ≈𝑐 𝒵 by the definition of computational indistinguishability. Definition 11 from Homework 3. A triple of algorithms (𝐺𝑒𝑛,𝐸𝑛𝑐,𝐷𝑒𝑐) is a stateful 𝑡-time se- mantically secure encryption scheme against chosen plaintext attacks (𝑡-SS-CPA) with respect to message domain 𝑀 if: Correctness: For any feasible adversary 𝒜 = {𝐴𝑛}𝑛∈𝐍 and any 𝑛 ∈ 𝐍 we have ⎡⎤ 𝑘1 ←$ Gen(1𝑛);𝑚1 ←𝐴𝑛 ⎥ (𝑘2, 𝑐1) ← 𝐸𝑛𝑐(𝑘1, 𝑚1); 𝑚2 ← 𝐴𝑛(𝑐1); ...; 𝑚𝑡 ← 𝐴𝑛(𝑐1, ..., 𝑐𝑡−1); (𝑐𝑡; 𝑘𝑡+1) ← 𝐸𝑛𝑐(𝑘𝑡, 𝑚𝑡) ⎥⎦ : ∀𝑖, if𝑚𝑖 ∈𝑀 then 𝐷𝑒𝑐(𝑘1,𝑐𝑖)=𝑚𝑖 BU CAS CS 538. 2 Secrecy: There is a negligible function 𝜈(𝑛) such that for any feasible adversary 𝒜 = {𝐴𝑛}𝑛∈𝐍 and all large enough 𝑛 we have: ⎡⎤ ⎢$$⎥ ⎢ 𝑏←{0,1} ; 𝑘1 ←𝐺𝑒𝑛(1𝑛) ;𝑚0,𝑚1 ←𝐴𝑛 ⎥ Pr⎢ ⎥< 2+𝜈(𝑛). ⎢⎣ (𝑘2,𝑐1)←𝐸𝑛𝑐(𝑘1,𝑚𝑏1);𝑚02,𝑚12 ←𝐴𝑛(𝑐1);...;𝑚0𝑡,𝑚1𝑡 ←𝐴𝑛(𝑐1,...,𝑐𝑡−1);(𝑘𝑡+1,𝑐𝑡)←𝐸𝑛𝑐(𝑘𝑡,𝑚𝑏𝑡) ⎥⎦ : 𝐴𝑛(𝑐1, ..., 𝑐𝑡) = 𝑏 Problem 2. Consider the following encryption scheme which is a combination of PRG and the one-time pad. It is defined over (𝒦, M, 𝒞) where |𝒦| = |M|. 𝐺 is a secure PRG. 𝑘1←$ 𝐺𝑒𝑛(1𝑛) Enc(𝑘𝑖, 𝑚𝑖) = [(𝑘𝑖+1, 𝑟𝑖) ← 𝐺(𝑘𝑖); 𝑐𝑖 ← (𝑟𝑖 ⊕ 𝑚𝑖, 𝑖)] Dec(𝑘1, (𝑐′, 𝑖)) = [(𝑘2, 𝑟2) ← 𝐺(𝑘1); ...; (𝑘𝑖+1, 𝑟𝑖) ← 𝐺(𝑘𝑖); 𝑚𝑖 ← 𝑟𝑖 ⊕ 𝑐′] Prove that this encryption scheme is CPA secure. Solution. Assume for contradiction that this encryption scheme is not CPA secure. This means there exists some feasible adversary 𝒜 = {𝐴𝑛}𝑛∈𝐍 such that ⎡⎤ ⎢$$𝑛01 ⎥ ⎢ 𝑏←{0,1} ; 𝑘1 ←𝐺𝑒𝑛(1 ) ;𝑚1,𝑚1 ←𝐴𝑛 ⎥ Pr⎢ (𝑘2,𝑟1) ← 𝐺(𝑘1);𝑐1 ← (𝑟1 ⊕𝑚1,1);𝑚2,𝑚2 ← 𝐴𝑛(𝑐1);...;𝑚𝑡,𝑚𝑡 ← 𝐴𝑛(𝑐1,...,𝑐𝑡−1); ⎥ ≥ 2 +𝜈(𝑛). ⎢ (𝑘𝑡+1,𝑟𝑡)←𝐺(𝑘𝑡);𝑐𝑡 ←(𝑟𝑡 ⊕𝑚𝑏𝑡,𝑡) ⎥ ⎣⎦ : 𝐴𝑛(𝑐1, ..., 𝑐𝑡) = 𝑏 where 𝜈(𝑛) is a negligible function. We first introduce a sequence of 𝑡 + 1 hybrid games, called Hybrid 0, Hybrid 1,..., Hybrid 𝑡. For 𝑗 = 0,1,...,𝑡, Hybrid 𝑗 is a game played between 𝒜 and a challenger that prepares a tuple 𝑡 ciphertexts; the first 𝑗 of which are prepared using truly random pairs of (𝑘𝑖,𝑟𝑖), whereas the remaining 𝑡 − 𝑗 of which are prepared using (𝑘𝑖, 𝑟𝑖) pairs generated by 𝐺. 𝒜 outputs one bit 𝑏′ at the end of the game. Let 𝐻𝑗 denote the probability that 𝒜 outputs the bit same as 𝑏 in Hybrid 𝑗 (i.e. 𝐻𝑗 := Pr[𝑏′ = 𝑏|Hybrid 𝑗]). Note that 𝐻0 is equal to the probability that 𝒜 outputs the correct bit in the original CPA game against the encryption scheme, so 𝐻0 ≥ 21 + 𝜈(𝑛) by our assumption; and 𝐻𝑡 is equal to the probability that 𝒜 outputs the correct bit in a game where each ciphertext is prepared through one-time pad with truly random keys, so 𝐻𝑡 = 12 . We next define a PRG adversary B that tries to distinguish between the output of 𝐺 and a truly random string with non-negligible probability. B is constructed as follows: B receives an input string (𝑘,𝑟) (which B needs to distinguish to be either generated by 𝐺 or truly random). B then uniformly randomly selects 𝑗 ←$ {1,2,...,𝑡}, and runs the CPA game with 𝐴𝑛. For 𝑖 ∈ {1,2,...,𝑡}, ⎧⎪⎨←$ 𝒦 × R (freshly), (𝑘𝑖+1,𝑟𝑖) ← (𝑘,𝑟), ⎪⎩← 𝐺(𝑘𝑖), otherwise (if 𝑖 > 𝑗)
BU CAS CS 538. 3
After submitting 𝑡 message pairs 𝑚0𝑖,𝑚1𝑖 and receiving 𝑡 ciphertexts 𝑐𝑖, 𝐴𝑛 sends a bit 𝑏′ to B. B outputŝ𝑏=1if𝑏′ =𝑏,and̂𝑏=0if𝑏′ ̸=𝑏. BbreaksthesecurityofPRG𝐺ifitcandistinguish between strings generated by 𝐺 and truly random strings with non-negligible probability, i.e. if
Pr[̂𝑏 = 1|(𝑘, 𝑟) ← 𝐺()] − Pr[̂𝑏 = 1|(𝑘, 𝑟) ←$ 𝒦 × R] is non-negligible.
Pr[̂𝑏 = 1|(𝑘,𝑟) ← 𝐺()] − Pr[̂𝑏 = 1|(𝑘,𝑟) ←$ 𝒦 × R] 𝑡
=𝔼 ∑︁Pr[𝑗]Pr[𝑏′ =𝑏|𝑗,(𝑘,𝑟)←𝐺()]−Pr[𝑗]Pr[𝑏′ =𝑏|𝑗,(𝑘,𝑟)←$ 𝒦×R] 𝑗
= ∑︁𝑡 1𝑡 Pr[𝑏′ = 𝑏|𝑗,(𝑘,𝑟) ← 𝐺()] − 1𝑡 Pr[𝑏′ = 𝑏|𝑗,(𝑘,𝑟) ←$ 𝒦 × R]
= ∑︁Pr[𝑏′ =𝑏|𝑗,(𝑘,𝑟)←𝐺()]−Pr[𝑏′ =𝑏|𝑗,(𝑘,𝑟)←$ 𝒦×R] 𝑡 𝑗=1
Observe that if 𝑗 ∈ {1,…,𝑡} is chosen and (𝑘,𝑟) is generated by 𝐺, then the game is the same as Hybrid 𝑗 − 1, where the first 𝑗 − 1. On the other hand, if 𝑗 ∈ {1,…,𝑡} is chosen and (𝑘,𝑟) is truly random, the game is the same as Hybrid 𝑗. Therefore, Pr[𝑏′ = 𝑏|𝑗,(𝑘,𝑟) ← 𝐺()] = 𝐻𝑗−1 and
Pr[𝑏′ = 𝑏|𝑗, (𝑘, 𝑟) ←$ 𝒦 × R] = 𝐻𝑗 . We can rewrite the above equation as: 1𝑡
∑︁Pr[𝑏′ =𝑏|𝑗,(𝑘,𝑟)←𝐺()]−Pr[𝑏′ =𝑏|𝑗,(𝑘,𝑟)←$ 𝒦×R] 𝑡 𝑗=1
= 1𝑡(𝐻0 −𝐻1 +𝐻1 −𝐻2 +…+𝐻𝑡−1 −𝐻𝑡)
= 1𝑡 ( 𝐻 0 − 𝐻 𝑡 ) ≥ 21 + 𝜈 ( 𝑛 ) − 21
Under this construction, B can distinguish between strings generated by 𝐺 and truly random strings with non-negligible probability, which is a contradiction that 𝐺 is secure. Therefore, the proposed encryption scheme must be CPA secure.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com