Re: Fractals, Cellular Automata, and Encryption

[tcmay@got.net (Timothy C. May)]

At 11:35 PM 3/9/96, Alan Bostick wrote:

>Howard Gutowitz published and patented in 1992 a symmetric block cipher
>algorithm, based on cellular automata, called CA-1.1 .  There are a
>couple of CA-based hash algorithms.  CA-based PRNGs have been shown to
>be isomorphic to linear feedback shift register RNGs (not linear
>congruential generators, despite what Tim says) and so are subject to
>the same security woes as LFSRs.

Yeah, that sounds like what it is. This is what I get for answering a
question without checking reference sources and/or FAQs, including my own
FAQ, wherein it is written:

  18.6.2. "Can cellular automata, like Conway's "Game of Life," be used
            for cryptography?"
           - Stephen Wolfram proposed use of cellular automata for
              crytography some years back; his collection of essays on
              cellular automata contains at least one such mention. Many
              people suspected that 1D CAs were no stronger than linear
              feedback shift registers (LFSRs), and I recally hearing a
              couple of years ago that someone proved 1D CAs (and maybe
              all CAs?) are equivalent to LFSRs, which have been used in
              crypto for many years.
           - Wolfram's book is "Theory and Applications of Cellular
              Automata," 1986, World Scientific. Several papers on using
              CAs for random sequence generation. P. Bardell showed
              in1990 that CAs produce the outputs of LFSRs.) Wolfram also
              has a paper, "Cryptography with cellular automata," in
              Proc. CRYPTO 85.
           - Intuitively, the idea of a CA looks attractive for "one-way
              functions," for the reasons mentioned. But what's the
              "trapdoor" that gives the key holder a shortcut to reverse
              the process? (Public key crypto needs a trapdoor 1-way
              funtion that is easy to reverse if one has the right
              information).

On the other hand, if more people asking questions about fractals, chaos,
quantum cryptography, etc., would check the usual places, others would not
have to do this searching for them. (To his credit, the guy who asked today
if anyone knew anything about the "index of coincidence" did say that he
first grepped through my FAQ.)

--Tim May


Boycott "Big Brother Inside" software!
We got computers, we're tapping phone lines, we know that that ain't allowed.
---------:---------:---------:---------:---------:---------:---------:----
Timothy C. May              | Crypto Anarchy: encryption, digital money,
tcmay@got.net  408-728-0152 | anonymous networks, digital pseudonyms, zero
W.A.S.T.E.: Corralitos, CA  | knowledge, reputations, information markets,
Higher Power: 2^756839 - 1  | black markets, collapse of governments.
"National borders aren't even speed bumps on the information superhighway."