Amount of simple operations that is safely out of reach for all humanity?

Question

Cryptographic primitives usually assert some security level given as number of operations to mount an attack. Hash functions, for example, give different security levels for collision attacks, preimage attacks and second preimage attacks. From these, "safe" key sizes are derived for different primitives.

There are many different recommendations for safe key sizes and many different means of estimating future capabilities in performing computation. For example, www.keylength.com has a lot of these recommendations combined.

What I'm looking for, however, is the amount of simple operations that can be obviously seen as out of reach for all humanity for the foreseeable future - or actually, the lowest such value that is still believable.

It is very obvious that 2^256 simple operations is something that will never be reached. It is also very obvious that 2^64 simple operations can be reached as it already has been. Many of the recommendations seem to calculate 2^128 as a number that would be safe for 30 years or more. So the value I am looking for is likely between 2^128 and 2^256. I am guessing 2^160 or 2^192 might be safely out of reach.

But I want concrete arguments that can be easily reasoned about. I'd love to see arguments that are based on simple laws of physics or relations to concrete constants about the universe. For example, Landauer's principle could be used.

Note: the actual simple operations used are not relevant here - they might be operations on a quantum computer, or hash invocations, or whatever.

Answer 1

As a starting point, we will consider that each elementary operation implies a minimal expense of energy; Laundauer's principle sets that limit at 0.0178 eV, which is 2.85*10^-21 J. On the other hand, the total mass of the Solar system, if converted in its entirety to energy, would yield about 1.8*10⁴⁷ J (actually that's what you would get from the mass of the Sun, according to this page, but the Sun takes the Lion's share of the total mass of the Solar system). This implies a hard limit of about 6.32*10⁶⁸ elementary computations, which is about 2^225.2. (I think this computation was already presented by Schneier in "Applied Cryptography".)

Of course this is a quite extreme scenario and, in particular, we have no idea about how we could convert mass to energy -- nuclear fission and fusion converts only a tiny proportion of the available mass to energy.

Let's look at a more mundane perspective. It seems fair to assume that, with existing technology, each elementary operation must somehow imply the switching of at least one logic gate. The switching power of a single CMOS gate is about C*V² where C is the gate load capacitance, and V is the voltage at which the gate operates. As of 2011, a very high-end gate will be able to run with a voltage of 0.5 V and a load capacitance of a few femtofarads ("femto" meaning "10^-15"). This leads to a minimal energy consumption per operation of no less than, say, 10^-15 J. The current total world energy consumption is around 500 EJ (5*10²⁰ J) per year (or so says this article). Assuming that the total energy production of the Earth is diverted to a single computation for ten years, we get a limit of 5*10³⁶, which is close to 2¹²².

Then you have to take into account technological advances. Given the current trend on ecological concerns and the peak oil, the total energy production should not increase much in the years to come (say no more than a factor of 2 until year 2040 -- already an ecologist's nightmare). On the other hand, there is technological progress in the design of integrated circuits. Moore's law states that you can fit twice as many transistors on a given chip surface every two years. A very optimistic view is that this doubling of the number of transistor can be done at constant energy consumption, which would translate to halving the energy cost of an elementary operation every two years. This would lead to a grand total of 2¹³⁸ in year 2040 -- and this is for a single ten-year-long computation which mobilizes all the resources of the entire planet.

So the usual wisdom of "128 bits are more than enough for the next few decades" is not off (it all depends on what you would consider to be "safely" out of reach, but my own paranoia level is quite serene with 128 bits "only").

A note on quantum computers: a QC can do quite a lot in a single "operation". The usual presentation is that the QC performs "several computations simultaneously, which we filter out at the end". This assertion is wrong in many particulars, but it still contain a bit of truth: a QC should be able to attack n-bit symmetric cryptography (e.g. symmetric encryption with a n-bit key) in 2^n/2 elementary quantum operations. Hence the classic trick: to account for quantum computers (if they ever exist), double the key length. Hence AES with a 256-bit key, SHA-512... (the 256-bit key of AES was not designed to protect against hypothetical quantum computers, but that's how 256-bit keys get justified nowadays).

Answer 2

Note: the actual simple operations used are not relevant here - they might be operations on a quantum computer, or hash invocations, or whatever.

Well, a quantum computer is the reason no one can tell you the "amount of simple operations that can be obviously seen as out of reach for all humanity for the forseeable future". By definition a quantum computer performs the opposite of "actual simple operations"; it allows one to bypass some large portion of "simple operation" space through quantum sleight-of-hand. Once the computer that bypasses portions of that simple operation space exists, then your question about "how big does the space need to be" becomes unpredictably irrelevant.

That's the theory, anyway. We haven't reached the level of future where quantum computers can do what we think they should be able to do. Although I'm comfortable saying that such a quantum computer does and does not exist in a box somewhere.