  We consider the cryptographic task of bit-string generation. This is a
generalisation of coin tossing in which two mistrustful parties wish to
generate a string of random bits such that an honest party can be sure that the
other cannot have biased the string too much. We consider a quantum protocol
for this task, originally introduced in Phys. Rev. A {\bf 69}, 022322 (2004),
that is feasible with present day technology. We introduce security conditions
based on the average bias of the bits and the Shannon entropy of the string.
For each, we prove rigorous security bounds for this protocol in both noiseless
and noisy conditions under the most general attacks allowed by quantum
mechanics. Roughly speaking, in the absence of noise, a cheater can only bias
significantly a vanishing fraction of the bits, whereas in the presence of
noise, a cheater can bias a constant fraction, with this fraction depending
quantitatively on the level of noise. We also discuss classical protocols for
the same task, deriving upper bounds on how well a classical protocol can
perform. This enables the determination of how much noise the quantum protocol
can tolerate while still outperforming classical protocols. We raise several
conjectures concerning both quantum and classical possibilities for large n
cryptography. An experiment corresponding to the scheme analysed in this paper
has been performed and is reported elsewhere.
