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."