Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. 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

Taken from

Cambridge University Press 0521830842 - Foundations of Cryptography: Basic Applications, Volume 2 CHAPTER FIVE - Encryption Schemes

which can be downloaded here

Notation. In the rest of this text, we write $E_e (\alpha)$ instead of $E(e, \alpha)$ and $D_d (\beta)$ instead of $D(d, \beta)$. Sometimes, when there is little risk of confusion, we drop these subscripts. Also, we let $G_1 (1^n)$ (resp., $G_2 (1^n )$) denote the first (resp., second) element in the pair G(1n ). That is, $G(1n ) = (G_1 (1^n ), G_2 (1^n))$. Without loss of generality, we may assume that $|G_1 (1^n )|$ and $|G_2 (1^n > )|$ are polynomially related to n, and that each of these integers can be efficiently computed from the other. (In fact, we may even assume that $|G_1 > (1^n )| = |G_2 (1^n)| = n$; see Exercise 6.)

share|cite|improve this question

It just means that the functions mentioned in your question can be written as a polynomial in $n$ (the independent variable is $n$). For example, $n^2+3n+4$ or something like that. It cannot be an exponential function or super-polynomial in $n$ or sublinear (i.e. $o(n)$).

share|cite|improve this answer
Why can't it be sub-linear? – Zach Langley Apr 10 '11 at 15:19
I've make a mistake with my words. What I've meant to say was sublinear but logarithmic. It is allowed to have $n^{1/2}$ for example. – Marcos Villagra Apr 10 '11 at 23:50

Your Answer


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