The idea of a flood cryptosystem

Thread View: sci.crypt

4 messages

[T] Back to Threads [V] Tree View [G] Group Articles

4 total messages Started by Dan Bernstein Thu, 09 Apr 1992 04:10

#568

Author: Dan Bernstein
Date: Thu, 09 Apr 1992 04:10

29 lines
1973 bytes

What follows is a rather obvious generalization of a well-known idea by
Sloane on how to foil an eavesdropper who has a noisy channel. Save this
article---this will prevent anyone from patenting the idea in the
future.

In tomorrow's high-speed networks it will be possible to overwhelm a
typical listener's expected ability to record a lengthy message. So
imagine two parties, X and Y, sharing some information. X and Y exchange
a large amount of data, more than an listener can be expected to record;
both X and Y compute on the fly a function of the data which depends on
the shared information. Unless the listener has enough knowledge of the
shared information to attack the system by brute force, he will never be
able to figure out any information about the value of the function,
provided of course that the data and function are cryptographically
strong. X and Y can exchange any amount of data this way, perhaps for
later use as a one-time pad, subject only to the capacity of the
network.

Notice that the initial shared information need not be perfectly secure.
It could even be publicized after it's used! The listener can, at best,
attempt to compute the function of the data simultaneously for all
possible values of the shared information, and if the shared information
comes from a sufficiently large space then this will be impractical. The
shared information could even have been transmitted by a weak
cryptosystem, provided that the listener is not able to break that
system before being flooded. So flooding can turn a weak cryptosystem
into a strong cryptosystem.

---Dan

Re: The idea of a flood cryptosystem

#569

Author: Carl Ellison
Date: Thu, 09 Apr 1992 16:49

18 lines
1444 bytes

In article <14871.Apr904.10.5392@virtualnews.nyu.edu> brnstnd@nyu.edu (Dan Bernstein) writes:
>In tomorrow's high-speed networks it will be possible to overwhelm a
>typical listener's expected ability to record a lengthy message.
 ^^^^^^^^^^^^^^^^

This is a wonderful idea.  Since the NSA isn't a typical listener (and
would probably be delighted to get the extra budget allocation to
cover the necessary intercept and recording ability), they should have
no objection to this method of operation.

So -- you end up with an algorithm labelled: "secure against IBM PC
clones with less than 800 MB of hard disk storage", for example, and you
can prove security without having to resort to complexity arguments.

Of course, all this depends on the shared function of the two streams
being secret -- or the eavesdropper could compute the function on the
fly just as the real recipients do.  If the function is secret and
shared, is this not just another private key system?

Re: The idea of a flood cryptosystem

#576

Author: Rick Smith
Date: Fri, 10 Apr 1992 19:52

11 lines
834 bytes

brnstnd@nyu.edu (Dan Bernstein) writes:

>In tomorrow's high-speed networks it will be possible to overwhelm a
>typical listener's expected ability to record a lengthy message. 

Shouldn't we expect tomorrow's high speed networks to arrive at
about the same time as tomorrow's multi-gigabit removable floppies
and streaming tape, etc?

Rick.
smith@sctc.com       arden hills, minnesota

Re: The idea of a flood cryptosystem

#605

Author: brnstnd
Date: Thu, 16 Apr 1992 04:17

24 lines
1581 bytes

In article <2058@transfer.stratus.com> cme@ellisun.sw.stratus.com (Carl Ellison) writes:
> So -- you end up with an algorithm labelled: "secure against IBM PC
> clones with less than 800 MB of hard disk storage", for example, and you
> can prove security without having to resort to complexity arguments.

Yep.

> Of course, all this depends on the shared function of the two streams
> being secret -- or the eavesdropper could compute the function on the
> fly just as the real recipients do.  If the function is secret and
> shared, is this not just another private key system?

It's different---the ``key'' is the initial shared information, but (1)
unlike normal keys it doesn't have to come from a very large space, (2)
it can be transmitted by a relatively weak cryptosystem, and (3) it can
be published immediately after the flooding.

Note on (1): If the initial shared information comes randomly from a
space of one million possibilities, then the attacker can, in principle,
compute all one million functions simultaneously, but in practice this
will be impossible---even though one million can't be considered a large
enough key space for most applications.

---Dan

Thread Navigation

This is a paginated view of messages in the thread with full content displayed inline.

Messages are displayed in chronological order, with the original post highlighted in green.

Use pagination controls to navigate through all messages in large threads.

Back to All Threads