Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm currently reading the paper (Leveled) fully homomorphic encryption without bootstrapping , and the following paragraph was near the start:

What is meant by the symbol used? Is it merely to represent polynomial time or something else entirely?

share|improve this question
Thanks for the edit, will make sure I follow proper posting practices in the future. – Masutatsu Jul 18 '13 at 10:30
I added a link to a page about this article, unfortunately it is only available for pay. – Paŭlo Ebermann Jul 20 '13 at 20:31
There is another version of the paper (by the same authors) which goes into the same info - Fully Homomorphic Encryption without Bootstrapping – mikeazo Jul 20 '13 at 20:43

As you probably know $f(\lambda)=O(\lambda^4)$ means that $|f|$ asymptotically upper bounded by some constant times $\lambda^4$. The notation $f(\lambda)=\Omega(\lambda^4)$ corresponds to an asymptotic lower-bound.

Now, the $\tilde O$ and $\tilde \Omega$ are closely related notations, where we not only ignore constants but also values which are polynomial in the logarithm of the argument.

So in your quotation, $\tilde\Omega(\lambda^4)$ refers to a function $f(\lambda)$ which is asymptotically lower bounded by something of the form $K \log(\lambda)^c \lambda^4$, where $K$ and $c$ are some non-specified constants. [I am ignoring the absolute value of $f$ from the definition, since it clear in your context that $f$ takes positive values.]

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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