Interesting new cipher patent

[Eugene Leitl]

On Fri, 1 Mar 2002 ian at veryfresh.com wrote:

> On Thu, Feb 28, 2002 at 08:54:18AM +0100, Eugene Leitl wrote:
> > A question: assuming, you have a class of random number generators with
> > lots of internal state. (Lots: like >>10^6 bits). Let's say the evolution
> > through state space of that generator is provably reversible (or nearly
> > reversible), and that the Hamiltonian of the system is stochastic (system
> > evolution is a randomwalk in state space). The result is a pseudorandom
> > number generator with a ridiculously long periode, and good randomness of
> > output, obviously. A simple cypher based on it would exchange the
> > pseudorandom generator state (the key) through a secure channel,
> > similiarly to a one time pad.
>
> How is this different than a standard stream cipher?

I thought I mentioned the point of this in the passage you snipped; here
is it again:

* algorithmic construction of PRNGs with provable properties
* lots of internal state, hence bit leakage even for a lot of messages
  buys attacker little
* scalable (add more state as hardware improves)
* directly mappable to hardware, very good parallelism

> Except for the key length, of 2^20 bits (compared to 2^6 to 2^8 in
> conventional stream ciphers), and the mention of reversibility, I
> can't see the difference.

I'm trying to create a scalable class of stream ciphers which at the
extreme end converge towards properties of an one time pad. I want them to
have provable properties (reversible CA, light cone reasoning; network of
cell with virtual connectivity), be algorithmically constructable and be
capable of ~TBps encoding bitrates, if implemented in hardware.

> Of course, having such a large key means that you have 128KB of key
> material to generate and securely distribute (I hope there would not
> have to be a new key for every message,) as you suggest, in the same
> cumbersome manner as a one time pad.

One time pads for TBit rate links are impractical. It would be interesting
whether such a small secret as ~1 MByte bitvector would create sufficient
security against sustained cryptoanalysis for a time window of operation
of about a decade. I haven't specified means of secret distribution, but
for high bit rates links the keys could be exchanged in plain (passive
attack, window of vulnerability during first link setup), via hardware
tokens/sneakernet (secure channel), via public-key methods (active MITM
attack), or installed during manufacturing/network setup (secure channel
again).

> I don't see where your requirement for reversibility comes in. My
> understanding of stream ciphers is that you would not want a reversible
> PRNG, since compromise of the PRNG state would mean that all past
> communications can now be decrypted.

Reversibility allows you to prove that there are no short attractor
cycles. (For near reversibility the proof would have to be probabilistic).

> With regards to the period of this cipher, it would be ridiculously
> long, as you say, but so are much smaller ciphers.. A 2^8-bit PRNG
> already has a period of length 2^2^8, or 10^77, which is a lot of data
> to send using a single key.
>
> I would be interested to know if this conjectured RNG has different
> properties than a conventional PRNG, or if I have misread your
> description, and a stream cipher is not actually what you were
> describing.

I'm describing an extreme case of a stream cypher, yes.


---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at wasabisystems.com