Cyphernomicon Top
Cyphernomicon 18.6

Loose Ends and Miscellaneous Topics:
Miscellaneous Advanced Crypto Ideas


   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