Jerry Leichter wrote: >> If current physical theories are even approximately correct, >> there are limits to how many "bit flips" (which would >> encompass all possible binary operations) can occur in >> a fixed volume of space-time.
> The physical arguments to which I was referring say *nothing* > about how the computation is done. It can be a QM computation > as well. "Obvious" assumptions are hardest to trace: they assume that the computation is done by bit flips which flip only constant number of bits. QM computation is done with the whole state, that is a flip in an N-qbit state simultaneously flips 2^N numbers describing this state (if it were simulated by a classical computer). I hope we agree that an exponential speed-up by QM computation *is* possible (unless factoring is in P). That is why if we hear that (1) a "physical limit" says that 2^N bit-flips cannot be done in a one-light-year computer in a year, and we know that (2) the best classical M-bit factoring requires 2^N bit-flips, and we know that (3) this factoring can be done in few minutes on a QM computer, then we must conclude that such "physical limits" are misleading. David Wagner wrote: > for a more nuanced and deep treatment of these issues, > http://www.scottaaronson.com/papers/npcomplete.pdf Thanks, it is great reading! Whether NP is physically computable is an interesting topic, but its applicability to our subject is quite limited: for cryptography it is important to know that none of the puzzles created by a user can be solved in some particular time given reasonable investment in hardware, and thus the fact that hard instances exist as size tends to infinity cannot console a practitioner. Jerry Leichter wrote: > >> All the protocols and standards out there calling for AES-256 - it's > >> obviously "better" than AES-128 because after all 256 is *twice as > >> large* as 128! - were just a bunch of nonsense. And, perhaps, > >> dangerous nonsense. > > > > I see the situation in the positive way: the recent AES attacks > > stress the fact that the key management should be done > > correctly, in particular, keys should be derived thru KDF (not > > a simple xor) and must be authenticated. With this attack in > > hand it is much easier for us now to say why one should not use > > K to encrypt messages of one type and K+1 for another type, or > > why it is a bad idea to encrypt a key in CTR mode and store the > > result without a MAC. I doubt it is possible to find any > > professionally designed protocol or standard that becomes weak > > due to the recent discovery. > > That's a ... bizarre point of view. :-) Should freedom from > related- key attacks be part of the definition of a "secure" > encryption algorithm? We should decide that on some rational basis, > not on whether, with care, we can avoid such attacks. Clearly, a > system that *is* secure against such attacks is more robust. Do we > know how to build such a thing? What's the cost of doing so? But > to say it's an *advantage* to have a weakness seems like some kind > of odd moral argument: If you're hurt by this it's because you > *deserve* to be. There is a set of rules in cryptographic design that are well known to practitioners and are ignored by kibitzers. In many cases it is much easier to do a normal design than to explain why some proposed "improvements" are bad. Consider a situation where some "smart" person comes to you and say that for some reason (say, to save space) they want to use CBC encryption, but keep IV constant; or they want to do CBC encryption and CBC-MAC with the same key (as a bonus they get encryption for free). What options you have once you manage to stop the laughter? In some cases it is enough to say: "No, SP800-38a in Appendix C requires IV for CBC to be unpredictable," but in other cases you also need to show a plausible-looking attack against the "improvement". In this situation it is clearly an advantage to have a known weakness of ignoring rules of sane key management. -- Regards, ASK --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [email protected]
