Sol 4

CS290G — Introduction to Modern Cryptography
Homework 4
Stefano Tessaro
Posted: Mar 3, Due: Mar 11 (Note unusual due date!)
Task 1 — Public-Key Encryption
Let PKE = (Kg, Enc, Dec) be a public-key encryption scheme with message space M = {0, 1}, i.e.,
PKE can only encrypt one-bit messages. We want to use PKE to encrypt longer messages – say
`-bit long. To this end, we consider the construction PKE = (Kg, Enc, Dec) which encrypts `-bit
messages bit-by-bit using PKE. More precisely, it behaves as follows. (Here, M [i] denotes the i-th
bit of a string M and v[i] the i-th component of a vector v.)
Procedure Kg:
For i = 1 to ` do
$
(SKi , PKi ) ← Kg
PK ← [PK1 , . . . , PKn ]
SK ← [SK1 , . . . , SKn ]
Return (PK, SK)
Procedure EncPK (M ): // M ∈ {0, 1}` Procedure DecSK (C):
For i = 1 to ` do
For i = 1 to ` do
$
$
C[i] ← EncPK[i] (M [i])
M [i] ← DecSK[i] (C[i])
Return C
Return M [1]k . . . kM [`]
In particular, ciphertexts C for PKE are `-dimensional vectors whose components are ciphertexts
for PKE.
a) [5 pts] Prove that PKE is not IND-CCA secure.
Hint: Give a concrete attack breaking IND-CCA-security.
Assume that ` ≥ 2. Moreover, we assume that PKE is perfectly correct, i.e., decryption is
always correct with probability one. (This is the only assumption we need to make to disprove
the claim, and it is not really necessary, but makes the presentation somewhat easier.)
We consider the following adversary A which operates as follows, given access to LRb and
DEC, as well as the public key PK.
Adversary ALRb ,DEC (PK):
$
C ← LRb (0` , 1` )
$
C 0 ← EncPK[1] (1)
C0 [1] ← C 0
For i = 2 to ` do C0 [i] ← C[i]
M 0 ← DEC(C0 )
If M 0 = 10`−1 then
Return 1
Else return 0
In particular, A replaces the first component of C with a fresh encryption of 1, and then submits
the resulting ciphertext C0 for decryption. Note that the query C0 does not return ⊥ if C 6= C0
(or equivalently, C[1] 6= C 0 ), and in particular if b = 0, whenever C 6= C0 , A gets the answer
M 0 = 10`−1 . Overall, this means that
h
i
$
Pr (PK, SK) ← Kg : ALR0 ,DEC (PK) = 1 = 1 − Pr C 0 = C[1] .
(1)
1
CS290G — Introduction to Modern Cryptography
Stefano Tessaro
Recall however that we have assumed that PKE is perfectly correct and never decrypt incorrectly, and thus since C 0 encrypts 1, yet C[1] encrypts 0 when b = 0, we must have C 0 6= C[1], for
otherwise decryption for PKE would be incorrect on C 0 or C[1]. Therefore, Pr [C 0 = C[1]] = 0,
and the above probability is always one.
In contrast, if b = 1, A always receives either M 0 = ⊥ (when C 0 = C[1]) or M 0 = 1` (when
C 0 6= C[1])), and thus M 0 6= 10`−1 no matter what. Hence,
h
i
$
Pr (PK, SK) ← Kg : ALR1 ,DEC (PK) = 1 = 0 .
(2)
To conclude, combining (1) and (2) yields
-cca (A) = 1 .
Advind
PKE
b) [15 pts] Assume that PKE is IND-CPA secure. Prove that PKE is also IND-CPA secure.
Hint: Proceed as follows:
- Formally describe a sequence of games G0 , G1 , . . . , G` where the adversary A asks a single
query (M0 , M1 ) to the LRb oracle, for M0 , M1 ∈ {0, 1}` . For this query, Game Gi returns C
such that
$
C[j] ← EncPK[j] (M0 [j])
for all i < j ≤ `, and
$
C[j] ← EncPK[j] (M1 [j])
for all 1 ≤ j ≤ i.
ind-cpa
- Prove that AdvPKE
(A) = Pr [G0 ⇒ 1] − Pr [G` ⇒ 1].
- For all 1 ≤ i ≤ `, prove that there exists an adversary Bi such that
-cpa
Advind
PKE (Bi ) = Pr [Gi−1 ⇒ 1] − Pr [Gi ⇒ 1] .
- Conclude IND-CPA security of PKE from the above.
To prove the claim, we fix an adversary A against IND-CPA security of PKE issuing exactly
one query to its LRb oracle. We are going to prove that there exist adversaries A1 , . . . , A` such
that
`
X
ind-cpa
(A) =
Advind-cpa (A ) ,
Adv
PKE
PKE
i
i=1
and moreover, A1 , . . . , A` are all PPT when A is PPT. This implies the claim, because all advan-cpa
tages Advind
PKE (Ai ) are all negligible when A is PPT by our assumption that PKE is IND-CPA
secure, and moreover, ` is small (i.e., polynomial in the security parameter) for PKE to be efficient. (The latter assumption was somewhat implicit, but the scheme does not make sense
otherwise if it cannot be executed.)
We start by defining the games G0 , G1 , . . . , G` as requested:
2
CS290G — Introduction to Modern Cryptography
Game Gi : // i ∈ {0, 1, . . . , `}
$
(PK, SK) ← Kg
$
b ← ALRb (PK)
Return b
Stefano Tessaro
Procedure LRb (M0 , M1 ): // M0 , M1 ∈ {0, 1}`
For j = 1 to ` do
If j ≤ i then
$
C[j] ← EncPK[j] (M1 [j])
Else
$
C[j] ← EncPK[j] (M0 [j])
Return C
It is easy to verify that
h
i
$
Pr [G0 ⇒ 1] = Pr (PK, SK) ← Kg : ALR0 = 1
as well as
h
i
$
Pr [G` ⇒ 1] = Pr (PK, SK) ← Kg : ALR1 = 1 .
In other words, we can rewrite A’s advantage as
-cpa (A)
Advind
PKE
= Pr [G0 ⇒ 1] − Pr [G` ⇒ 1] =
`
X
Pr [Gi−1 ⇒ 1] − Pr [Gi ⇒ 1] .
i=1
To conclude the proof, we now give the adversaries Ai explicitly. Note that these adversaries
live in the IND-CPA experiment for PKE. The idea, as usual, is that we let Ai use the underlying
experiment to simulate either of Gi−1 or Gi to A depending on whether b = 0 or b = 1. In
particular, the adversaries Ai internally run an execution of A with some simulate public key
PK, and access to a simulated LR0b oracle which is obtained by using, as a sub-routine, the
actual LRb oracle Ai is given access to. Formally:
b
Adversary ALR
i (PK): // i ∈ {0, 1, . . . , `}
For j = 1 to ` do
If j = i then
PK[j] ← PK
Else
$
(PK[j], SK[j]) ← Kg
0
$
b ← ALRb (PK)
Return b
Procedure LR0b (M0 , M1 ): // M0 , M1 ∈ {0, 1}`
For j = 1 to ` do
If j < i then
$
C[j] ← EncPK[j] (M1 [j])
Else if j = i then
$
C[j] ← LRb (M0 [j], M1 [j])
Else
$
C[j] ← EncPK[j] (M0 [j])
Return C
It is not hard to check by inspection that
-cpa
Advind
PKE (Ai ) = Pr [Gi−1 ⇒ 1] − Pr [Gi ⇒ 1] ,
which concludes the proof. (The fact that Ai is PPT if A is PPT is obvious.)
3

Download Report