[Cryptography] Universal security measures for crypto primitives

[Jerry Leichter]

On Oct 7, 2013, at 1:43 AM, Peter Gutmann <pgut001 at 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