Dedicated Conventional Cryptographic Primitives - A Classical Introduction to Cryptography: Applications for Communications Security - page 73

one common number in the two sequences with probability

e − θ 1 θ 2

p −→

N →+∞

1 − .

Proof. Let N 1 = θ 1 √ N , N 2 = θ 2 √ N , and let us consider the independent random
variables with uniform distribution X 1 ,..., X N 1 , Y 1 ,..., Y N 2 in { 1 ,..., N } .Wewant

to compute

p = Pr[ ∃ i , jX i = Y j ] .

Let C be the cardinality of { X 1 ,..., X N 1 } .Wehave

c ] 1

N 2 N 1

c
N

1 − p = Pr[ C = − .

c = 1

Since c is always less than N 1 ,wehave

1 N 2

N 1
N

e − θ 1 θ 2 1 − p ≥ − −→

N →+∞

.

o ( √ N ). We truncate

On the other hand, let α N be such that α N −→ +∞ and α N =

the above sum to c = N 1 − α N .Wehave

1 N 2

N 1 − α N
N

1 − p ≤ − + Pr[ C < N 1 − α N ] .

o ( √ N ). It remains to prove that The first term tends toward e − θ 1 θ 2

since α N =

<

N 1 − α N ] is negligible.

Pr[ C

Let

D = 1 X i = Y j .

i < j

N 1 ( N 1 − 1)

We have Pr[ C < N 1 − α N ] ≤ Pr[ D >α N ]. Obviously we have E ( D ) = .

2 N

Since all 1 X i = X j are pairwise independent, we can also compute the variance

1

N 1 ( N 1 − 1) 1

N

V ( D ) = − .

2 N

Now from the Chebyshev Inequality we have

V ( D )

Pr[ D >α N ] ≤

E ( D )) 2 . ( α N −