11
$\begingroup$

When proving theorems in crypto we often make use of the concept of negligible functions or, more simply, negligible parameters.

As a rule of thumb, given today (2018) computational power, what is the smallest inverse power of 2 that we can consider negligible? I expect this to be something around $2^{-64}$.

|improve this question
$\endgroup$
  • 2
    $\begingroup$ You are mixing up two concepts: negligible function is precise and well defined. And regarding that definition, no specific power of two is negligible, because no constant is negligible. So, what do you mean by "negligible" in your second paragraph? Could you please elaborate it so that what you want become clearer? Thank you. $\endgroup$ – Hilder Vítor Lima Pereira Aug 25 '18 at 12:13
13
$\begingroup$

Negligible is a human term, not a precise definition. It refers to things which are sufficiently small that one is willing to ignore it in the interests of expediency. The threshold varies from person to person: a NSA mathematician will have a different threshold for a property than a CEO of a startup will). It also varies from topic to topic: $2^{-64}$ solar masses is still a solid quarter of the entire biomass of humans put together!

In my experience, the proof of negligability is often not how small the number is, but how large its inverse is. Its inverse is often highly associated with some real practical number, like how much energy it takes to crack an algorithm, or how many years.

For example, the risk associated with the brute forcing of a 256-bit key is negligibly small. This is because we can calculate how much energy it would take to count that high, much less run the algorithm that many times. I did the numbers once, with ultra-idealized hardware running in the cold of space, it takes about 3/4 of the energy in the galaxy to run that counter from 0 to $2^{255}$

|improve this answer
$\endgroup$
  • 1
    $\begingroup$ Is the answer 256 then? $\endgroup$ – Paul Uszak Aug 24 '18 at 21:16
  • 12
    $\begingroup$ @PaulUszak The risk associated with an attacker brute forcing 256 bit keys is negligible. The risk associated with eating 256 Oreo's in one sitting is not. It's not the number that matters, it's the entire phrase. =) $\endgroup$ – Cort Ammon - Reinstate Monica Aug 25 '18 at 6:43
  • 1
    $\begingroup$ My wife would probably disagree vehemently with your assertion about the dangers of 256 Oreos, but it rings pretty true to me. That's a great way to point out the importance of context, not just words and their definitions. $\endgroup$ – Caleb Aug 25 '18 at 9:48
  • $\begingroup$ Well, could we try the mathematical context of cryptography, rather than a bakery or Star Trek? $\endgroup$ – Paul Uszak Aug 25 '18 at 10:19
  • 1
    $\begingroup$ I appreciate the answer, but let's stick to the number as counting the number of bits. This number should be related to the computational power available to a "reasonably powerful" (no matrioshka brains please :) ) attacker. $\endgroup$ – Rexcirus Aug 25 '18 at 11:03
2
$\begingroup$

It's about 64.

Notwithstanding intergalactic adventures, it's a little akin to grasping a slippery eel. So we only have anecdotal evidence to draw upon. One use of a small $\epsilon$ is in the generation of true random numbers.

  1. A relevant document to TRNG design is DRAFT NIST Special Publication 800-90C, Recommendation for Random Bit Generator (RBG) Constructions, August 2012, which is predicated on good output as $\epsilon \leq 2^{-64}$.

1

(Strangely, this definition has vanished in the latest draft.)

  1. NIST Special Publication 800-90B, Recommendation for the Entropy Sources Used for Random Bit Generation, January 2018 says

2

when talking about TRNG health tests.

  1. A CSPRNG built upon AES in counter mode is currently a standard form. The output sequence stands a good chance of being distinguished after $2^{64}$ blocks. We still accept that risk given the likelihood of generating 2 Zettabytes of data.

  2. ID Quantique's Technical Paper on Randomness Extractor, Version 1.0, September 2012 has mention of them achieving $\epsilon < 2^{-100}$.

  3. Bruno Sanguinetti, Anthony Martin, Hugo Zbinden, and Nicolas Gisin, Quantum Random Number Generation on a Mobile Phone, Group of Applied Physics, University of Geneva, Genève 4, CH-1211, Switzerland state they achieve $2^{-320} \leq \epsilon \leq 2^{-270}$ depending on photosensor technology.

With regard to items 4 & 5: It's trivial to generate a minuscule $\epsilon$ by simply altering the entropy input to output ratio on the extractor algorithm. I would take these values as atypical examples of a negligible number.

Finally this PassMark chart shows the continuation of Moore's Law into the future, especially as new nodes are developed such as IBM's 5nm process, and core scale out:-

4565

So ignoring outliers at $2^{-20}$ and $2^{-320}$, NIST remains of the view that a bias of $2^{-64}$ is still safe. Hence answer = 64.

|improve this answer
$\endgroup$
  • $\begingroup$ A CSPRNG built upon AES in counter mode is currently a standard form. The output sequence stands a good chance of repeating after $2^{64}$ blocks. if the CSPRNG is not doing anything other than $E_k(\text{nonce})$ for unique values of $\text{nonce}$ then it has no chance of repeating (at least until the nonce loops back over to $0$, which means nonces are no longer unique). $\endgroup$ – Ella Rose♦ Aug 26 '18 at 3:30
1
$\begingroup$

Attacks are, leaving out technical and thermodynamic limitations, a financial problem. There's the cost of the attack on one side, and the value of what you can retrieve on the other side.

If the likelihood of encountering something by accident (say, a hash collision) is low enough so you could reasonably assume it will never happen to any living person during their lifetime, and if the cost of an active attack whatsoever (assuming an attacker on the scale of a major industry nation, and several years of time) is more expensive than the most expensive secret that you are protecting, then it may arguably be valid to say "neglegible". Few people will attempt an attack that costs more than it yields in benefit.
Better though, the above assumption should still hold if you assume your secrets are one million times more expensive. Ideally, an attack would be prohibitive by thermodynamics, of course.

|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.