Cryptography Reference
In-Depth Information
unique bitstring. This type of assignment gives rise to the concept of finger-
printing codes where not only different strings correspond to different users,
but also it is possible to identify a user who contributes to the production
of a valid object sequence that is produced as a combination of a number of
assigned user sequences. Fingerprinting codes will prove to be an invaluable
tool for digital content distribution. In this chapter we will provide a formal
treatment of this primitive and we will put forth a number of constructions.
1.1 Preliminaries
In this chapter and throughout the topic we use standard notation. For n ∈ N
we denote by [n] the set {1,...,n}. Vectors are denoted by x,y,z,... and we
write x = hx
1
,...,x
`
i for a vector x of dimension `.
We next introduce some preliminary facts about random variables and
probability distributions that will be frequently used in this chapter and else-
where. Unless noted otherwise we use capital letters X,Y,Z,... to denote
random variables. We use the notation Prob[R(X)] to denote the probability
the event R(X) happens where R(·) is a predicate that has domain equal to
the range of X.
We will frequently utilize the exponentially decreasing bounds on the tails
of a class of related distributions commonly referred to as Chernoff bounds.
We will skip the proofs of these inequalities as they are out of the scope of
this topic and we refer the reader to e.g., Chapter 4 of [
85
] for a detailed
discussion.
Theorem 1.1 (The Chernoff Bound). Let X
1
,...,X
n
be independent
Poisson trials such that Prob(X
i
) = p
i
. Let X =
P
i=1
X
i
and µ = E[X],
then the following hold:
1. For any δ > 0, Prob[X ≥ (1 + δ)µ] <
µ
e
δ
(1+δ)
1+δ
2. For any 0 < δ ≤ 1, Prob[X ≥ (1 + δ)µ] ≤ e
−µδ
2
/3
3. For any R ≥ 6µ, Prob[X ≥ R] ≤ 2
−R
4. For any 0 < δ < 1, Prob[X ≤ (1−δ)µ] ≤
e
−δ
(1−δ)
1−δ
µ
5. For any 0 < δ < 1, Prob[X ≤ (1−δ)µ] ≤ e
−µδ
2
/2
Often, the following two-tailed form of the Chernoff bound, which is
derived immediately from second and fifth inequalities above, is used for
0 < δ < 1:
Prob[|X−µ|≥ δµ] ≤ 2e
−µδ
2
/3
(1.1)
More generally it holds for δ > 0,
Prob[|X−µ|≥ δµ] ≤ 2e
−µδ
2
/(2+δ)
(1.2)
It is possible to obtain stronger bounds for some special cases:
