CAS CS538: Cryptography. Spring 2023 Instructor: , Ran Canetti
Equivalence between Shannon and semantic secrecy of perfect encryption schemes
February 17, 2023
This note proves the equivalence between the semantic formulation and the Shannon formulation of perfectly secure encryption schemes.
Copyright By PowCoder代写 加微信 powcoder
Recall the definitions:
Definition 1 (Correctness). An encryption scheme (Enc,Dec) for message domain M and key domain K has perfect correctness if for all m ∈ M and all k ∈ K we have Dec(k,Enc(k,m)) = m. That is, if c = Enc(k,m) then Dec(k, c) = m.
Definition 2 (Shannon secrecy). Encryption scheme (Enc, Dec) for message domain M and key domain K has Shannon secrecy if for any two messages m0 , m1 ∈ M and any string c we have
Prob[k ←$ K : Enc(k,m0) = c] = Prob[k ←$ K : Enc(k,m1) = c]. (1) Definition 3 (Semantic secrecy). Encryption scheme (Enc, Dec) for message domain M and key domain K has
perfect semantic secrecy if for any algorithm A and any two messages m0 , m1 ∈ M we have
Prob[b←$ {0,1}; k←$ K; c←Enc(k,mb) : A(c)=b]=21. (2)
Claim 1. Let (Enc,Dec) be an encryption scheme for message domain M and key domain K. If (Enc,Dec) has Shannon secrecy then (Enc,Dec) has semantic secrecy.
Proof. Informally, since every ciphertext c is equally likely to be the result of encrypting m0 as it is likely to be the result of encrypting m1, no ciphertext c can help A to obtain any advantage over a random guess. To make this intuition more formal, we will consider the success probability of A separately on each ciphertext, and then sum up these probabilities. Specifically, let C be the domain of ciphertexts for the scheme, i.e. C = {c : ∃m ∈ M,k ∈ K s.t. Enc(k,m) = c}. Then:
Prob[b←$ {0,1}; k←$ K ; c←Enc(k,mb) : A(c)=b] (3) Prob[b←$ {0,1}; k←$ K ; c←Enc(k,mb) : A(c)=b&c=c∗] (4)
Prob[b←$ {0,1}; k←$ K : A(c∗)=b&Enc(k,mA(c∗))=c∗] (5)
Prob[b←$ {0,1} : A(c∗)=b]·Prob[k←$ K : Enc(k,mA(c∗))=c∗] (6)
12Prob[k←$ K : Enc(k,mA(c∗))=c∗] (7)
12·Prob[k←$ K:Enc(k,m0)=c∗]=12 (8)
In step (6) we observe that, for any fixed c∗, the event where A(c∗) = b is independent of the event where
Enc(k,mA(c∗)) = c∗ (in particular the former event depends only on the choice of b, whereas the latter event depends only on the choice of k). The crucial step is (7), where we use (1) to replace Prob[k ←$ K : Enc(k, m1) = c∗] with Prob[k ←$ K : Enc(k, m0) = c∗] for those c∗ where A(c∗) = 1.
Claim 2. Let (Enc,Dec) be an encryption scheme for message domain M and key domain K. If (Enc,Dec) has semantic secrecy then (Enc,Dec) has Shannon secrecy.
Proof. Assume that there exists a ciphertext c∗ and two messages m0,m1 such that
Prob[k ←$ K : Enc(k,m0) = c] < Prob[k ←$ K : Enc(k,m1) = c]. (9)
We show an algorithm Ac∗ such that
Prob[b←$ {0,1}; k←$ K; c←Enc(k,mb) : A(c)=b]>21. (10)
Ac∗ proceeds as follows, on input c: If c = c∗ then Ac∗ outputs 1. Else, Ac∗ outputs a random bit b′. We analyze the success probability of Ac∗ . We know that
It follows that:
Prob[b←$ {0,1}; k←$ K; c←Enc(k,mb) : A(c)=b|c=c∗]>12, Prob[b←$ {0,1}; k←$ K; c←Enc(k,mb) : A(c)=b|c̸=c∗]=21.
Prob[b←$ {0,1}; k←$ K ; c←Enc(k,mb) : A(c)=b] (11) = Prob[b←$ {0,1}; k←$ K ; c←Enc(k,mb) : A(c)=b|c=c∗]·Prob[c=c∗]+ (12) Prob[b←$ {0,1}; k←$ K ; c←Enc(k,mb) : A(c)=b|c̸=c∗]·Prob[c̸=c∗] (13)
> 21(Prob[c = c∗] + Prob[c ̸= c∗]) = 12.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com