Tag Info

New answers tagged


I assume you're already familiar with pseudorandom generators. A PRG takes a short random seed and generates a long pseudorandom string. You can extend a PRG using a simple output-feedback construction, to achieve a PRG with any polynomial output length. But can you ask for even more? Can you take a short random seed and generate an exponentially long ...


The main conceptual point is: Ideally, in cryptography, one would often like to use a random function as a building block. However, these are very unhandy (as the text you copied elaborates), since generally, the only way to store an arbitrary function is as a lookup table, which becomes huge very quickly. Therefore, one tries to find a more practical method ...


Random function -- function $F$, that is selected randomly from the set $Func$ of all possible functions (with given domain and range). Pseudo-random function --- family $\{F_k\}$ of functions, that is indexed by the parameter $k$ (which serves as a number). It is pseudo-random, because if someone picks $k$ secretly and lets you interact with $F_k$, it ...


Random function: (Pseudo)randomly pick a function from the set of all possible functions mapping an input to an output, where the input and output are the lengths/types you want.

Top 50 recent answers are included