On Oct 7, 2013, at 1:43 AM, Peter Gutmann <pgut...@cs.auckland.ac.nz> wrote: > Given the recent debate about security levels for different key sizes, the > following paper by Lenstra, Kleinjung, and Thome may be of interest: > > "Universal security from bits and mips to pools, lakes and beyond" > http://eprint.iacr.org/2013/635.pdf > > From now on I think anyone who wants to argue about resistance to NSA attack > should be required to rate their pet scheme in terms of > neerslagverdampingsenergiebehoeftezekerheid (although I'm tempted to suggest > the alternative tausendliterbierverdampfungssicherheit, it'd be too easy to > cheat on that one).
While the paper is a nicely written joke, it does get at a fundamental point: We are rapidly approaching *physical* limits on cryptographically-relevant computations. I've mentioned here in the past that I did a very rough, back-of-the envelope estimate of the ultimate limits on computation imposed by quantum mechanics. I decided to ask a friend who actually knows the physics whether a better estimate was possible. I'm still working to understand what he described, but here's the crux: Suppose you want an answer to your computation within 100 years. Then your computations must fall in a sphere of space-time that has spatial radius 100 light years and time radius 100 years. (This is a gross overestimate, but we're looking for an ultimate bound so why not keep the computation simple.) Then: "...fundamental limits will let you make about 3*10^94 ~ 2^315 [bit] flips and store about 2^315 bits, in your century / light-century sphere." Note that this gives you both a limit on computation (bit flips) and a limit on memory (total bits), so time/memory tradeoffs are accounted for. This is based on the best current understanding we have of QM. Granted, things can always change - but any theory that works even vaguely like the way QM works will impose *some* such limit. -- Jerry _______________________________________________ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography