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 .
 
Search WWH ::




Custom Search