1
$\begingroup$

According to Katz Lindell book,

Let Dist be a distribution on l-bit strings. Informally, Dist is pseudorandom if the experiment in which a string is sampled from Dist is indistinguishable from the experiment in which a uniform string of length l is sampled. (Strictly speaking, since we are in an asymptotic setting we need to speak of the pseudorandomness of a sequence of distributions Dist = {$Dist_{n}$}, where distribution $Dist_{n}$ is used for security parameter n. We ignore this point in our current discussion.) More precisely, it should be infeasible for any polynomial-time algorithm to determine (better than guessing) whether it is given a string sampled according to Dist, or whether it is given a uniform l-bit string.

What do they mean here by sequence of distributions?

$\endgroup$
1
$\begingroup$

A sequence of distributions is a definition of a distribution for each $n$. For example, consider the distribution $Dist_n$ to be a string of length $l(n)$ generated using some pseudorandom generator with a seed of length $n$. Then, for each $n$, the distribution is actually different. The reason why technically you need this is because the notion of negligible is asymptotic - it needs to be a function so that for every polynomial, the function is smaller than it for some large enough $n$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.