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).
By Tim May, see README
HTML by Jonathan Rochkind