public random numbers

[JMKELSEY@delphi.com]

-----BEGIN PGP SIGNED MESSAGE-----

>Date: Fri, 03 Nov 1995 00:44:02 -0800
>From: tcmay@got.net (Timothy C. May)
>Subject: Re: video as a source of public randomness
>
>At 6:23 AM 11/3/95, JMKELSEY@delphi.com wrote:
>
>>This seems like a potential source of a stream of public random
>>bits.  If these can be authenticated and matched, this kind of thing
>>can be useful in a lot of protocols.  For example, if there is some
>
>I'm not sure what you mean by "public random bits"...I don't plan to share
>my random bits with anyone, nor do I see any need for "public" random bits
>(except for some well-known situations involving statistical testing, for
>which certain PRNGs are actually preferable to "real" random numbers).

Imagine there is a stream of totally random bits over which neither
Alice nor Bob has any control.  We can use this to make a lot of
interactive protocols non-interactive.

Suppose we have a protocol where we need a random challenge from
Bob.  Alice sends a message to Bob starting the protocol, stating
that the public random bit stream is currently at bit i, and
committing to use the n-bit string starting at position (i+t) as the
challenge.  The t parameter here needs to be large enough to ensure
that Bob receives and logs the message before the public random bit
stream outputs bit i+t.  Alice proceeds with the protocol, using the
n-bit string starting at bit (i+t) as the challenge.  She sends the
resulting message to Bob.  No interaction was required of Bob--he
merely had to log the times of the messages, and keep track of the
public random bits.  This could be really useful implementing
noninteractive digital cash schemes, I think, because the merchant
wouldn't have to send anything back.  (The merchant can also be very
hard to track down by following the messages, since these messages
of Alice's can be encrypted under his public key and posted to a
newsgroup or something, though this implies really large values of
t.)

Naturally, this only works if Alice and Bob get the same random
string, and if it's not possible for anyone to alter the public
random bit string either one receives.  For large-scale
applications, the way to do this is probably to put a hardware RNG
into a communications satellite, and devote one channel to
continuous digitally-signed packets of random data.  For
smaller-scale or underground applications, it might be sufficient to
use some digitized transmission that would probably not be worth the
trouble for an attacker to alter, even if one could.  For example,
if we used the entire digital video feed off some major satellite,
it would be enormously expensive to take control of that for any
length of time, to attack some protocol.  To prevent simple attacks,
we can hash the digitized input, and we can make each shared random
packet dependent on previous packets by some relation like

random_packet[i+1] = SHA1(random_packet[i],SHA1(digital_video_packet[i])).

>And so there's no confusion, when I said "like a noisy channel (t.v.
>channel, for example)" I meant a snowy, noisy picture such as one gets with
>rabbit ears on top of the set, especially when the channel is an unused
>one. It is unlikely in the extreme that any attacker could deduce the snowy
>pixel values used in the distillation of entropy.

I was just thinking of the unintended entropy in the stuff going on
on the screen.  Static would mess this idea up, though there are
some ways to recover.

>But back to the subject of "public random bits." Could you elaborate on
>what you mean by this? (I assume you don't mean a one time pad that Alice
>and Bob share, since that is really a separable issue from video as a
>source of randomness. Only one of them will generate the pad, and will then
>securely communicate it to the other.)

No, of course not.  Public random bits can be used in the derivation
of a shared key, to prevent replay attacks in key-exchange
protocols, but you certainly wouldn't want to use the public random
bits directly as key material!

>--Tim May

Note:  Please respond via e-mail as well as or instead of posting,
as I get CP-LITE instead of the whole list.

   --John Kelsey, jmkelsey@delphi.com
 PGP 2.6 fingerprint = 4FE2 F421 100F BB0A 03D1 FE06 A435 7E36

-----BEGIN PGP SIGNATURE-----
Version: 2.6.2

iQCUAwUBMJqtkUHx57Ag8goBAQGWRgP1HES4nQiWRx0P31bi94g5MI8pSEwf5CZu
0RlWLyCl5CLB6PKu7bJDqiyHIBBJ90qqvJvZB740QHVxoRKycOD459nMWjiQXcnA
70Aq8gR+ZYCivsJLJfhKxoxuT+s/VyYVMB7mSfqGIGHHErbXHR4oA2T+Owmm8POi
WDr4w3OjyQ==
=3QHQ
-----END PGP SIGNATURE-----