Computational Indistinguishability

Updated 13 Aug 2026

•
Definition
- •
  two distributions $P_1, P_2$ are computationally indistinguishable (written $P_1 \approx_p P_2$ ) if no efficient Statistical Test has non-negligible advantage in telling a sample of one from a sample of the other
•
Generalizes PRG security
- •
  " $G$ is a secure PRG" is exactly the statement "the distribution of $G(k)$ for random $k$ is computationally indistinguishable from the uniform distribution" — this compact notation is used throughout the rest of the course to define security
•
Related

Linked references 2