Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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}$.
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}$
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.
(Strangely, this definition has vanished in the latest draft.)
when talking about TRNG health tests.
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.
ID Quantique's Technical Paper on Randomness Extractor, Version 1.0, September 2012 has mention of them achieving $\epsilon < 2^{-100}$.
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:-
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.
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
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.
