Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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

Let $f$ = $\{f_k\}$ be a pseudorandom function family.

Let $G(x)$ be a pseudo-random generator such that: $G(x) = f_x(0^k)f_x(1^k)$ where $k=|x|$.

I don't understand the meaning of $1^n$ and $0^n$, and the differences between them, in that context. What do they represent?

What is the special role / effect they have on the above context? And how?

Why $1^n$ and $0^n$, and not other combinations?

share|improve this question
Related (but, despite what I first assumed, probably not really duplicate) question: What does the expression $1^n$ mean as a function argument? – Ilmari Karonen Apr 30 '15 at 18:15
up vote 4 down vote accepted

Without seeing the entire formal construction: It seems like they wanted different strings. Meaning they needed $f_x(a)||f_x(b)$ where $a≠b$. The easiest way to express this is using the all $0$ and all $1$ strings, but any other pair of distinct strings of that length would yield the same effect.

As to why they wanted this: They're using a PRF twice to construct a PRG. Consider what would happen if they used the same string both times. You'd get $$G(x)=f_x(0^k)||f_x(0^k)$$

And the output string would have the property that the first half of the bits are same as the second half of the bits and this would not be pseudorandom(a distinguisher can just check if the the first half and second half of the bits are the same), so $G$ would definitely not be a PRG.

share|improve this answer
Note that since the strings are each other's complement, the Hamming distance is $k$ / $|x|$ as well. If that matters depends on $f_x$; $f$ is a PRF, but I presume that $f_x$ isn't. Of course you could also define $01^{k/2}$ and $10^{k/2}$ but then $k$ must be dividable by two; $0^k$ and $1^k$ are the easiest choice. – Maarten Bodewes Apr 30 '15 at 20:34

Typically that means a string of either $n$ zeros or $n$ ones.

share|improve this answer
yeah but what is the meaning of those strings inside the above equation? why $0^k$ and not $0^{k-1}$1 ? – Yoni Hassin Dec 28 '12 at 23:34
Why always in cryptography $1^k$ and $0^k$ are used? do they have a symbolic value? that the part that confuses me. – Yoni Hassin Dec 28 '12 at 23:40
@YoniHassin: what are you actually asking? What $0^k$ means, or why that was selected rather than $0^{k-1}1$? As for the former, it (in context) means a bitstring consisting of k zero bits. As for the latter, well, the reason the author of the primitive selected that specific choice probably depends a lot on the context of how the primitive works; without knowing the context, it is unlikely anyone could guess. – poncho Dec 29 '12 at 3:49
I will try to rewrite the question so it will be more clear. – Yoni Hassin Dec 29 '12 at 3:57
In light of the above edit, it seems like they wanted different strings. Meaning they needed $f_x(a)||f_x(b)$ where $a \neq b$. The easiest way to express this is using the all 0 and all 1 strings, but any other unique pair would yield the same effect. – AFS Dec 29 '12 at 23:04

$0^n$ means a string of $n$ zeros (the $n$-bit string that is all zeros). $1^n$ means a string of $n$ ones.

Why were these used? There's nothing special about $0^n$ or $1^n$, in this context. They could have used any pair of two constant $n$-bit strings, as long as the two strings were not the same. $0^n$ and $1^n$ is a convenient choice of two strings that are different, but they could have chosen any other pair (as long as they're not both the same) and that would have worked fine, too.

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.