Cryptography Reference
In-Depth Information
The above result involves some approximation and does not associate a
desired success probability with the required number of samples. We formulate
this connection in a general setting of statistical hypothesis testing.
Consider an event A with P(A) = p, while observing samples of keystream
words of a stream cipher. Let X
r
= 1, if the event A occurs in the r-th sample;
X
r
= 0, otherwise. In other words, P(X
r
= 1) = p for all r. Thus,
X
r
∼Ber(p).
If we observe n many samples, then
n
X
r
∼B(n,p).
r=1
When X
r
's are independent and identically distributed (i.i.d.) random vari-
ables and n is large enough,
n
X
r
∼N (np,np(1−p)).
r=1
We are interested in testing the null hypothesis
H
0
: p = p
0
(1 + ǫ),
ǫ > 0,
against the alternative hypothesis
H
1
: p = p
0
.
The objective is to find a threshold c in [np
0
,np
0
(1 + ǫ)] such that
n
P
X
r
≤c | H
0
≤α
r=1
and
n
P
X
r
> c | H
1
≤ β.
r=1
For such a c to exist, we need
np
0
(1 + ǫ)−np
0
> κ
1
σ
1
+ κ
2
σ
2
,
where
σ
1
= np
0
(1 + ǫ) (1−p
0
(1 + ǫ)),
σ
2
= np
0
(1 −p
0
),
Φ(−κ
1
)
= α
and
Φ(κ
2
)
=
1−β.
