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
I would like to know what $O(v(n))$ really means in detailed and simple words please. I found it everywhere in the literature I am reviewing but I cannot find what the intuition of it (especially if it means the Big O Notation, then what it has to do with the Probability here; also what is $v$, it is never defined except in another paper as a constant -but maybe not related directly to v in this formula-).
Many Thanks.
But this notation is defined (informally) in the first paper.
The notation $O(\nu(n))$ is used for any function, $f(n)$, that vanishes faster than the inverse of any polynomial, that is for every polynomial, $\mathrm{poly} (n)$, and $n$ large enough, $f(n) \leq 1/\mathrm{poly}(n)$
Therefore, what it means is no probabilistic polynomial time (PPT) algorithm $A$ can guess the next bit at inverse polynomially decreasing error rate.
Given any PPT algorithm $A$ this error probability decays super-polynomially, for example at a rate $\exp(-\log^2 n)$ which goes to zero faster than any polynomial.
Claim: $\exp(-\log^2 n)$ is less than $n^{-c}$ for any constant $c$ for $n$ large enough.
Proof: Look at the reciprocal. $$\exp(\log^2 n) > n^c$$ if and only if $$\log^2 n > c \log n$$ which will clearly happen as soon as $$\frac{\log^2 n}{\log n}>c$$ i.e., as soon as $\log n>c$.
Note that $\exp(\log^{1+\epsilon} n)$ is superpolynomial for all $\epsilon>0.$
Edit: The superpolynomial convergence is essentially what is referred to as negligibility.
First, that's not the Next Bit Test, which is purely theoretical, but rather an attempt at a practical approximation of it.
From your first citation:
The notation $O(\nu(n))$ is used for any function, $f(n)$, that vanishes faster than the inverse of any polynomial, that is for every polynomial, $poly(n)$, and $n$ large enough, $f (n) < 1/poly (n)$.
So you can think of it as a function that asymptotically approaches 0, very, very quickly. Overall, this means that the probability in question must then be extremely small. Since that probability is |(the chance that an attacker guesses the next bit)-50%| it means the attacker has extremely small advantage.
