On Oct 7, 2013, at 1:43 AM, Peter Gutmann <[email protected]> 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
[email protected]
http://www.metzdowd.com/mailman/listinfo/cryptography
