  We derive two conditional expectation bounds, which we use to simplify
cryptographic security proofs. The first bound relates the expectation of a
bounded random variable and the average of its conditional expectations with
respect to a set of i.i.d. random objects. It shows, under certain conditions,
that the conditional expectation average has a small tail probability when the
expectation of the random variable is sufficiently large. It is used to
simplify the proof that the existence of weakly one-way functions implies the
existence of strongly one-way functions. The second bound relaxes the
independence requirement on the random objects to give a result that has
applications to expander graph constructions in cryptography. It is used to
simplify the proof that there is a security preserving reduction from weakly
one-way functions to strongly one-way functions. To satisfy the hypothesis for
this bound, we prove a hitting property for directed graphs that are
expander-permutation hybrids.
