Appendix - formal proofs

Proof of Lemma 1:

No adversary can have a greater advantage thanA, defined by:_{opt}This follows from the fact that:

A(_{opt}.guessr_{1}, ...,r)_{N}= 1, if r_{i}S_{1}\S_{0}for somei1..N= 0, otherwise

- when one or more of the
rare in_{i}S_{1}\S_{0}, thenb= 1 with probability 1.- otherwise,
bhas a slightly greater than 1/2 probability of being 0, but the values of thergive no additional information about_{i}b(so no adversary can do better than guessingb= 0 in this case).Therefore Pr[

- When
b= 1:

Pr[ r_{i}S_{1}\S_{0}for somei]= 1 - (| S_{0}| / |S_{1}|)^{N}< 1 - (1- u)^{N}< N.u(because (1-u)^{N}> 1 -N.u)- When
b= 0:- Pr[
r_{i}S_{1}\S_{0}for anyi] = 1A(_{opt}.guessS_{0},S_{1},N) =b] < (1/2.N.u) + (1/2.1)

I.e. Adv( A, S_{opt}_{0}, S_{1},N)< 2.(1/2. N.u+ 1/2) - 1= N.uSo Adv(

A,S_{0},S_{1},N) <N.ufor anyA, becauseAis optimal._{opt}

Proof of Lemma 2:

Proof of security of BRH-DHAES against Chosen Plaintext Attack:

Proof of security of BRH-DHAES against Non-Adaptive Chosen Ciphertext Attack:

Proof of security of BRH-DHAES against Adaptive Chosen Ciphertext Attack:

David Hopwood <hopwood@zetnet.co.uk> |