Tag Info

New answers tagged

0

$F'_k(x)$ is not necessarily pseudo-random. Proof: Changing one output does not affect PRGness, so if there is a PRG that stretches by a factor of 2 then there is a PRG that stretches by a factor of 2 and sends all-zero strings to all-zero strings. For all $n$ and $k$ and $x$, if $G$ is such a PRG then $F'_k(x)$ is the string of $n$ zeros. For all $n$, ...


3

The general way to answer questions like this in the affirmative (i.e. prove that some transformation of a certain type of thing gives you another of that type of thing) is to assume that your transformed version doesn't have the property you need, and use that to prove that the original also doesn't have that property. Then if the original does have the ...



Top 50 recent answers are included