# What do they mean when saying that a certain value should be “super-logarithmic”?

What do they mean when saying that a certain value should be “super-logarithmic”?

I've found the Wikipedia definition of a “super-logarithm”, but I'm having trouble understanding how a given value can be super-logarithmic (in some security parameter).

As for an example of the use of the terminology, see http://research.microsoft.com/en-us/um/people/yael/publications/2010-Symmetric_Encryption.pdf. It appears right in the abstract.

The term super-logarithmic in the paper you cite has nothing to do with the notion of a super-logarithm in Wikipedia. Rather, the intention is simply a function that is asymptotically larger than the $\log$ function. Formally, $f$ is super-logarithmic if $f(n)=\omega(\log n)$. The formal definition of "little-omega" appears in the Wikipedia entry on big-O notation.
• That would mean the simple $f(x)=x$ function is super-logarithmic, right? – Medinoc Jul 21 '16 at 10:03
• @giddy Typically, when you set some value $v$ to be super-logarithmic, what you are looking for is either that $2^{-v}$ be negligible or $2^v$ be out of the reach for computation. Now, when going concrete, it really depends on what exactly you mean. For example, if you are repeating a zero-knowledge proof with soundness $1/2$ until you get negligible error, then you could set $v=40$ or $v=80$ depending on what probability of error you can live with. When you need a time bound that is beyond the running time of the adversary then it is accepted to take $v=128$ today. – Yehuda Lindell Jul 21 '16 at 18:02