On 12/3/05, Victor Duchovni <[EMAIL PROTECTED]> wrote: > Actually, this is inaccurate, proving the strength of AES or factoring is > difficult, and may never happen, we may even prove AES to be not secure > (in a broad sense) some day. Proving an RNG secure is *impossible*.
I'm not sure it's impossible, but you certainly have to restrict the scope from "unconditional security", which is an impossibility anyway. By analogy, an attacker may have encrypted some plaintext with your key and gotten your ciphertext before. Here is a reasonable security model: An attacker has access to all outputs of this PRNG x_0 .. x_n and nothing else of relevance. Can he guess x_(n+1) with probability greater than chance? Even if you allow the attacker to have seen the sequence before, using assumptions such as "the bounded storage model" may prevent him from completely compromising the PRNG: http://www.crypto.ethz.ch/research/itc/samba/ Part of the problem is that we just don't know what the attacker has access to, and that the implicit goal (prove that there is no algorithm for predicting x_(n+1) better than y) is a universal, akin to cipher design's goal of proving that there is no algorithm for decrypting ciphertext without the key that is more efficient than y. There are other possible goals; one might want an observer to be unable to distinguish it from a stream of numbers drawn from a uniform distribution, that re-seeding recover from state compromise, that the smallest program which generates the output x_0..n be of length O(n), that predicting the next output implies being able to solve a hard problem. There are some examples of the latter, for example the blum-blum shub (BBS) generator: http://en.wikipedia.org/wiki/Blum_Blum_Shub I believe that it has been proven that if one-way functions exist, then secure PRNGs exist. If I am not mistaken, lack of one-way functions would prevent effective encryption. After all, conventional encryption is just a one-way permutation based on a secret input k. It is not even necessary that *trapdoor* one-way functions exist, which is a common assumption in public-key systems. For more information, see "Pseudorandomness and Cryptographic Applications", ISBN 0-691-02546-0, by Michael Luby. Warning: theory-intensive. -- http://www.lightconsulting.com/~travis/ -><- Knight of the Lambda Calculus "We already have enough fast, insecure systems." -- Schneier & Ferguson GPG fingerprint: 50A1 15C5 A9DE 23B9 ED98 C93E 38E9 204A 94C2 641B --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
