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.

  • $\begingroup$ That would mean the simple $f(x)=x$ function is super-logarithmic, right? $\endgroup$
    – Medinoc
    Jul 21 '16 at 10:03
  • $\begingroup$ @Yehuda how would one translate the notion of super-logarithmic to concrete terms. Meaning say you wanted concrete security with 128 bit security. What would be a plausible value of something that needed to be super-logarithmic? $\endgroup$
    – giddy
    Jul 21 '16 at 17:42
  • $\begingroup$ @Medinoc Certainly: a linear function is super-logarithmic. Usually, we refer to this regarding the security parameter. $\endgroup$ Jul 21 '16 at 17:58
  • 1
    $\begingroup$ @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. $\endgroup$ Jul 21 '16 at 18:02
  • 1
    $\begingroup$ The answer is that there is a difference between statistical error and computational hardness. $\endgroup$ Jul 21 '16 at 18:33

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.