From: gts (gts@optexinc.com)
Date: Fri Sep 27 2002 - 09:44:31 MDT
Charles Hixon and Emyln O'regan,
I believe you two are introducing complications into the problem,
complications which do not in fact exist.
I think we can agree at least that the hotbits device generates truly
random numbers via quantum measurements of beta decay intervals *if* the
measuring device does not introduce bias. This is to say that the
probabilities of 1 or 0 on each successive measurement would be found to
be even for an infinitely long sequence, following a binomial
distribution no different from a series of fair coin flips. Yes?
Now then the question before us is whether the technique used to
eliminate any possible bias works as intended. Assuming there *is* a
bias in the original sequence...
Let us say the probabilities are .55 and .45 for 1's and 0's
respectively for the uncorrected sequence. When we switch the rule on
successive measurements used to determine whether a given time interval
comparison should be recorded as 1 or 0, we correct for that bias
*without determining whether a given position should be a 1 or 0*.
Notice that we are *not* determining the actual number to be recorded at
any given position. We cannot know in advance whether the next beta
particle will be emitted sooner rather than later, and *that*
uncertainty remains a source of genuine randomness underlying the data.
In correcting the sequence we are deciding only the mechanical rule used
to decide 1 or 0, which is *also* the case for the original uncorrected
sequence. We are not removing the underlying indeterminism. Thus our
correction rule is not actually introducing any determinism into the
final recorded sequence. Okay?
Emyln makes the more interesting argument: that *if* there is a security
breach, such that the potential attacker knows the general manner in
which we corrected for bias, then he can uncover the original biased
sequence. That is certainly true. However a little thought will show
that it is not necessary even to know that rule to generate a biased
sequence from the corrected data. For example if we reversed every odd
position in the correction process, then reversing every even position
would also result in another biased sequence. This means there is no
information available in the final unbiased sequence that would allow
for determination of the actual rule for unbiasing the sequence.
Emyln writes:
> 1 - it would seem clear that an analysis of a long enough stream of
these
> bits could uncover the odd/even rule
See my paragraph above. Even if an attacker knew such rule a existed, (a
big if -- it would require a serious breach of security as to the source
of your random numbers), there would still be no information in the
final sequence to allow the attacker to determine whether the rule was
"reverse odds" or "reverse evens". Either rule would look equally
probable, and if exploited neither rule would in itself result in an
actual crack of your cipher. For reasonable estimates of bias (e.g.,
1=.55 and 0=.45), such an attack would allow only for a slightly shorter
number of trials in a brute force attack, from which no cipher is
immune.
I think however that you've hit upon an important point; that is, even a
genuinely random number sequence can be compromised by a breach of
security. You are in effect arguing that security must not breached when
using the hotbits device as source of genuine random numbers, but then
we already knew that.
-gts
This archive was generated by hypermail 2.1.5 : Sat Nov 02 2002 - 09:17:18 MST