We’re rewarding the question askers & reputations are being recalculated! Read more.

New answers tagged


It is not necessary, that $G_1$ is a PRG. Let $G_2: \{0,1\}^{n-1} \rightarrow \{0,1\}^n$ be a PRG, define $G_1: \{0,1\}^n \rightarrow \{0,1\}^{n+1}$ as \begin{align*} G_1(s_1||\ldots||s_n) := 1||G_2(s_2||\ldots||s_n). \end{align*} and consider the distinguisher $\mathcal{D}_1$, which returns the first bit $w_1$, when given the $n+1$ bit string $w := w_1||\...


There are many possible constructions but the simplest is probably to initalize a counter with a random seed and hash the counter to produce more random bits and then increment the counter.


Pseudorandom permutation Confusingly, nothing really gets permuted here in the classic definition of a permutation. It's more of a cryptographic twist on the common notion of permutation. The actual input/output behaviour is like:- And each input is mapped to exactly one output value. The above diagram is simplistic in that the size of the inputs and ...


All three are families of functions. For example, $f_k(x) = k \oplus x$, where $\oplus$ is xor and $k$ and $x$ are 256-bit strings, is a family of functions; for any 256-bit string $k$, there is a function $f_k$ which given another 256-bit string $x$ returns the xor of $k$ and $x$. The input and output spaces need not be the same; we could imagine a family ...

Top 50 recent answers are included