[147549] in cryptography@c2.net mail archive
Re: [Cryptography] Universal security measures for crypto primitives
daemon@ATHENA.MIT.EDU (Jerry Leichter)
Mon Oct 7 11:19:47 2013
X-Original-To: cryptography@metzdowd.com
From: Jerry Leichter <leichter@lrw.com>
In-Reply-To: <E1VT3bL-0006Il-4f@login01.fos.auckland.ac.nz>
Date: Mon, 7 Oct 2013 10:46:49 -0400
To: Peter Gutmann <pgut001@cs.auckland.ac.nz>
Cc: cryptography@metzdowd.com
Errors-To: cryptography-bounces+crypto.discuss=bloom-picayune.mit.edu@metzdowd.com
On Oct 7, 2013, at 1:43 AM, Peter Gutmann <pgut001@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
