Cryptography Reference
In-Depth Information
(
=
|
=
)
(
=
)
=
(
=
|
=
)
(
=
)
that Pr
M
m
C
c
Pr
C
c
Pr
C
c
M
m
Pr
M
m
and hence the
scheme has perfect secrecy if and only if:
Pr
(
C
=
c
|
M
=
m
)
=
Pr
(
C
=
c
).
Example 3.1
1. Let
(
Gen
,
Enc
,
Dec
)
be an encryption scheme with
M
=
C
=
K
={
0
,
1
}
and
suppose that the probability distributions on
M
and
K
are given by:
3
1
•
Pr
(
M
=
0
)
=
4
,Pr
(
M
=
1
)
=
4
.
2
1
•
Pr
(
K
=
0
)
=
3
,Pr
(
K
=
1
)
=
3
.
Suppose further that, for each
m
∈
M
and each
k
∈
K
,
Enc
k
(
m
)
=
m
⊕
k
, where
⊕
denotes the Xor operation. In order to check whether this scheme has perfect
secrecy, we compute the probability distribution on
C
M
induced by those on
K
and
. The formula:
Pr
(
C
=
c
)
=
Pr
(
K
=
k
)
Pr
(
M
=
Dec
k
(
c
))
k
∈
K
gives:
•
Pr
(
C
=
0
)
=
Pr
(
K
=
0
)
Pr
(
M
=
Dec
0
(
0
))
+
Pr
(
K
=
1
)
Pr
(
M
=
2
3
1
1
7
Dec
1
(
0
))
=
3
·
4
+
3
·
4
=
12
.
•
Pr
(
C
=
1
)
=
Pr
(
K
=
0
)
Pr
(
M
=
Dec
0
(
1
))
+
Pr
(
K
=
1
)
Pr
(
M
=
2
1
1
3
4
5
12
.
Then we can see that the scheme is not perfectly secure because the condition
Pr
Dec
1
(
1
))
=
3
·
4
+
3
·
=
(
C
=
c
|
M
=
m
)
=
Pr
(
C
=
c
)
does not hold for all
m
∈
M
and all
c
∈
C
:
2
3
=
5
12
.
Pr
(
C
=
1
|
M
=
1
)
=
Pr
(
K
=
0
)
=
Pr
(
C
=
1
)
=
Alternatively, we can directly use the definition of perfect secrecy and check
that the condition Pr
(
M
=
m
|
C
=
c
)
=
Pr
(
M
=
m
)
does not hold either. For
example, let us compute Pr
(
M
=
0
|
C
=
0
)
which, by Bayes' formula, is equal
to
Pr
(
C
=
0
|
M
=
0
)
Pr
(
M
=
0
)
Pr
2
. Since Pr
(
C
=
0
|
M
=
0
)
=
Pr
(
K
=
0
)
=
3
we obtain:
(
C
=
0
)
2
3
4
Pr
(
K
=
0
)
Pr
(
M
=
0
)
3
·
6
7
=
3
4
.
Pr
(
M
=
0
|
C
=
0
)
=
=
=
Pr
(
M
=
0
)
=
Pr
(
C
=
0
)
7
12
2. Let us now consider the same scheme as in 1 except for the fact that we now
assume that the probability distribution on
K
is the uniform distribution. The
distribution induced on
C
is now:
1
3
1
1
4
1
•
Pr
(
C
=
0
)
=
2
·
4
+
2
·
=
2
.