18.6.1. "Why have provably "NP-complete" problems not found uses in crypto?" - One of the great Unresolved Mysteries! Or the Holy Grail, if you will. - The issue is why have provably hard (or NP-complete, to be more accurate) problems not been used? (Factoring is not known to NP-complete...experts can correct my phrasing here if I'm misstating things.) - It would be nice if a provably hard problem, such as the domino tiling problem, or 3SAT, or other such things out of Garey and Johnson's book on NP-Completeness could be used. This would increase confidence in ciphers still further. 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).
Next Page: 18.7 Viruses and Crypto
Previous Page: 18.5 Neural Nets and AI in Crypto
By Tim May, see README
HTML by Jonathan Rochkind