Re: genetic algorithms for crypto analysis
It has been noted in this thread that a good crypto algorithm would require an attacker to locate a single spike in a problem space, rather than having to climb a hill (which is, of course, much easier). I recall reading (I think in Sci. Am.) that a theory under investigation now as to why nature has sexual reproduction as part of its repertoire is that this gives a solution-seeking population a better opportunity to located spikey solutions. From the point of view of genetic algorithms, sexual reproduction means that each offspring must be generated from two members of the existing population, each of which contributes half the information needed to generate the offspring. In theory, this maintains a population that is spread over a wider terrain, and is thus more likely to find the spike. I don't know if such a strategy would help at all in crypto analysis, or whether any genetic algorithm programs currently in use employ this strategy. __ | (V) | "Tiger gotta hunt. Bird gotta fly. | (^ (`> | Man gotta sit and wonder why, why, why. | ((\\__/ ) | Tiger gotta sleep. Bird gotta land. | (\\< ) der Nethahn | Man gotta tell himself he understand." | \< ) | | ( / | Kurt Vonnegut Jr. | | | | ^ |
HAHN@lds.loral.com:
[makes excellent point that given sexual reproduction, evolution does not need continuous search space] I don't know if such a strategy would help at all in crypto analysis, or whether any genetic algorithm programs currently in use employ this strategy.
Sexual reproduction (aka string crossover) is the fundamental attribute of GAs that distinguish them from hill-climbing algorithms; it has been in all GAs from their invention. One of original works on the subject is now out in reprint: John Holland's _Adaptation in Natural and Artificial Systems_, MIT Press. Crossover doesn't allow magic teleportation directly to the needle in the search space haystack. GA leaps over gaps where the "crossover Hamming distance" is small, but the space need not be continuous. Cryptanalysis where one can gain clues, partial solutions, etc. and compose these into better solutions, might be amenable to GA. If you can say "solution A is better than solution B" with an algorithm, it's a good candidate for solving with GA or GP (genetic programming, which works on trees instead of strings). Nick Szabo szabo@netcom.com
participants (2)
-
Reply to: hahn@lds.loral.com
-
szabo@netcom.com