Cryptography Reference
In-Depth Information
the other hand it is relatively straightforward to see that p
n
≤
1
|M|
(recall that
M denotes the plaintext space). Hence there must be at least one 0 < s ≤ n for
which|p
s−1
−p
s
|≥
σ−1/|M
n
by the triangular inequality. Now if the parameters
have been chosen so that
σ−1/|M|
n
> 10ε
p
, this can lead to the accusation of
the user possessing k
s
.
We will discuss this in the following basic lemma, which we will also refer
to it as the tracing lemma.
Lemma 3.18. For N,K ∈ N, consider a sequence of N+1 independent exper-
iments each one repeated K times. Let p
i
the probability of success of the i-th
experiment for i ∈{0,...,N} and ρ
i
∈{0,...,K} the number of times the i-th
experiment succeeds. Then, with probability 1−ε, there is an s ∈{1,...,N} for
which it holds |ρ
s
−ρ
s−1
|≥
5
·K(p
0
−p
N
)/N and the smallest such s satisfies
that |p
s
−p
s−1
|≥
5
·(p
0
−p
N
)/N provided that K ≥ 75·N
2
ln(8/ε)(p
0
−p
N
)
−2
.
Proof. Note that the case p
0
≤ p
N
is trivial thus we will only consider the
proof of the lemma for p
0
> p
N
.
Let µ
i
= K ·p
i
for i = 1,...,N, i.e., µ
i
is the expected number of suc-
cesses of the i-th experiment. We apply a two-tailed Chernoff bound due to
Equation
1.2
for any i = 0,...,N and for 0 < δ we have:
Prob[|ρ
i
−µ
i
|≥ δµ
i
] ≤ 2e
−µ
i
δ
2
/(2+δ)
Substituting δ =
µ
i
for some γ and µ
i
= K ·p
i
, we obtain:
Prob[|ρ
i
−µ
i
|≥ γ] ≤ 2e
−γ
2
/(2µ
i
+γ)
≤ 2e
−γ
2
/(2Kp
i
+γ)
≤ 2e
−γ
2
/3K
where the last inequality follows from p
i
≤ 1 and γ ≤ K. Substituting
γ =
K(p
0
−p
N
)
5N
to the inequality we obtain:
2e
−γ
2
/3K
= 2e
−
K
2
(p
0
−p
N
)
2
1
3K
·
25N
2
≤ 2e
−
75N
2
·ln(8/ε)
(p
0
−p
N
)
2
·
(p
0
−p
N
)
2
75N
2
≤ 2e
− ln(8/ε)
≤
4
The above analysis shows that for any i ∈{0,1,...,N}, we have |ρ
i
−µ
i
|≤
γ with probability at least 1−ε/4.
Claim 1. consider any s ∈ {1,...,N} for which it holds that |ρ
s
−ρ
s−1
| ≥
3
5
·K(p
0
−p
N
)/N. We will prove that with probability at least 1−ε/2 it holds
that |p
s−1
−p
s
|≥ (p
0
−p
N
)/5N.
By applying the triangular inequality for the equations |µ
s−1
−ρ
s−1
|≤ γ
and |µ
s
−ρ
s
|≤ γ, we have that it holds:
