Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$, $0^n$ and the differences between them within that context. What do they represent?

EDIT:
I know it represent a string of zeros or ones but why always in cryptography $1^k$ and $0^k$ are used? Why not other combinations? Do they have a symbolic value? That is the part that confuses me.

share|improve this question
5  
I don't know the context, but in theoretical computer science $0^n$ and $1^n$ quite often (maybe even most often) mean the string consisting of $n$ $0$'s, $1$'s respectively, i.e. $0^n=\underbrace{0\dots0}_{n\text{ times}}$. –  martin.koeberl Dec 28 '12 at 23:17
    
@martin.koeberl's guess is almost certainly correct. This notation is if anything more common in cryptography than in TCS. –  Henning Makholm Dec 28 '12 at 23:23
    
i know it represent a string of zeros or ones but 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:42
    
What exactly is your question then? The special role of $0^k$ and $1^k$ in that question? Or why that notation is used? –  TMM Dec 29 '12 at 1:53
    
The special role of $0^k$ and $1^k$ in that question –  Yoni Hassin Dec 29 '12 at 3:21
show 3 more comments

1 Answer 1

up vote 1 down vote accepted

OK i got the answer from Cryptography Stack exchange: http://crypto.stackexchange.com/questions/5851/what-do-0n-and-1n-mean-in-cryptography/5856#5856

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
add comment

Your Answer

 
discard

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.