Cryptography Reference
In-Depth Information
Theorem 1.2. Let X
1
,...,X
n
be independent variables with Prob(X
i
= 0) =
Prob(X
i
= 1) =
2
for i = 1,...,n. We then have for X =
P
i=1
X
i
:
1. For any a > 0, Prob[X ≥ n/2 + a] ≤ e
−2a
2
/n
.
2. For any 0 < a < n/2, Prob[X ≤ n/2−a] ≤ e
−2a
2
/n
.
Note that in settings where much less information is known about the
distribution of a non-negative random variable X we can still utilize Markov's
inequality to obtain a crude tail bound as follows for any positive constant a,
Prob[X ≥ a] ≤ E[X]/a (1.3)
In a number of occasions we will also use the following handy lemma.
Lemma 1.3 (The coupon collector problem). Suppose that there are
n ∈ N coupons, from which coupons are being collected with replacement. Let
β > 0 and F
β
be the event that in k ≥ βn lnn trials there exists a coupon that
has not been drawn. It holds that Prob[F
β
] ≤ n
1−β
.
Proof. The probability that a certain coupon is not drawn in k trials is (1−
1/n)
k
. It follows that the probability of the event F
β
will be bounded by
n(1 − 1/n)
k
by applying the union bound. Using the inequality 1 + x ≤ e
x
we have that Prob[F
β
] ≤ ne
−β lnn
from which we draw the conclusion of the
lemma.
1.2 Definition of Fingerprinting Codes
A codeword x of length ` over an alphabet Q is an `-tuple hx
1
,...,x
`
i where
x
i
∈ Q for 1 ≤ i ≤ `. We call a set of codewords C ⊆ Q
`
with size n, a
(`,n,q)-code given that the size of the alphabet is q, i.e. |Q| = q.
Given an (`,n,q)-code C, each codeword x ∈ C will be thought of as the
unique fingerprint of a user. The user accesses an object that is somehow
fingerprinted with this codeword. Furthermore, we suppose that any other
object corresponding to an arbitrary codeword in Q
`
is equally useful. Given
those assumptions, we think of an adversary (which is also called a pirate)
that corrupts a number of users (which are sometimes called traitors) and
retrieves their codewords. The pirate then runs a Forging algorithm that
produces a “pirate” codeword p ∈ Q
`
. In the adversarial formalization, the
Forging algorithm will be subject to a marking assumption which forces the
pirate to produce a codeword that is correlated to the user codewords that
the pirate has corrupted. The simplest form of the marking assumption that
will prove to be relevant in many settings is the following :
Definition 1.4 (Marking assumption). We say a Forging algorithm sat-
isfies the marking assumption for a set of codewords C = {c
1
,...,c
n
} where
c
j
∈ Q
`
for j ∈ [n], if for any set of indices T ⊆ [n], it holds that Forging
