The security of Enigma depended on the secrecy of the algorithm in addition to the key. This violated Kirchoff's principle, the requirement that a system be secure against an adversary who has everything except the key. This mistake has been repeated many times by amateur cryptographers who thought that keeping the algorithm secret improved security. Such systems are invariably broken. Secure systems are built by publishing the algorithm so that people can try to break them before they are used for anything important. It has to be done this way because there is no provably secure system (regardless of whether P = NP), except the one time pad, which is impractical because it lacks message integrity, and the key has to be as large as the plaintext and can't be reused.
Anyway, my point is that decoding the human genome or natural language is not as hard as breaking encryption. It cannot be because these systems are incrementally updatable, unlike ciphers. This allows you to use search strategies that run in polynomial time. A key search requires exponential time, or else the cipher is broken. Modeling language or the genome in O(n) time or even O(n^2) time with n = 10^9 is much faster than brute force cryptanalysis in O(2^n) time with n = 128. -- Matt Mahoney, [EMAIL PROTECTED] ----- Original Message ---- From: Eric Baum <[EMAIL PROTECTED]> To: agi@v2.listbox.com Sent: Thursday, November 9, 2006 12:18:34 PM Subject: Re: [agi] Natural versus formal AI interface languages Eric Baum <[EMAIL PROTECTED]> wrote: >Matt wrote: >Changing one bit of the key or plaintext affects every bit of the cipherte= xt. >That is simply not true of most encryptions. For example, Enigma.=20 Matt: Enigma is laughably weak compared to modern encryption, such as AES, RSA, S= HA-256, ECC, etc. Enigma was broken with primitive mechanical computers an= d pencil and paper. Enigma was broken without modern computers, *given access to the machine.* I chose Enigma as an example, because to break language it may be necessary to pay attention to the machine-- namely examining the genomics. But that is more work than you envisage ;^) It is true that much modern encryption is based on simple algorithms. However, some crypto-experts would advise more primitive approaches. RSA is not known to be hard, even if P!=NP, someone may find a number-theoretic trick tomorrow that factors. (Or maybe they already have it, and choose not to publish). If you use a mess machine like a modern version of enigma, that is much less likely to get broken, even though you may not have the theoretical results. Your response admits that for stream ciphers changing a bit of the plaintext doesn't affect many bits of the ciphertext, which was what I was mainly responding to. You may prefer other kinds of cipher, but your arguments about chaos are clearly not germane to concluding language is easy to decode. Incidentally, while no encryption scheme is provably hard to break (even assuming P!=NP) more is known about grammars: they are provably hard to decode given P!=NP. ----- This list is sponsored by AGIRI: http://www.agiri.org/email To unsubscribe or change your options, please go to: http://v2.listbox.com/member/?list_id=303 ----- This list is sponsored by AGIRI: http://www.agiri.org/email To unsubscribe or change your options, please go to: http://v2.listbox.com/member/?list_id=303
