|
EDIT : I added more context. Let $f$ = {$f_k$} be a pseudo random 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$ , $0^n$ and the differences between them within that context. What do they represent? What is the special role / affect they have on the above context? and how? Why $1^n$ , $0^n$ and not other combinations? |
||||
|
|
|
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. |
|||
|
|
|
Typically that means a string of either $n$ zeros or $n$ ones. |
|||||||||||||
|
|
$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. |
|||
|
|
