Hybrid argument

From CRYPTUTOR

The hybrid argument is a proof technique often used in cryptography to show that two distributions are computationally indistinguishable. The name comes from the process of defining several "hybrid" distributions built from the original two distributions.

Outline

Proofs that use the hybrid argument follow this basic pattern:

1. Define a sequence of polynomially many (in the security parameter) distributions (called the hybrid distributions, or simply the hybrids) in the following way:
   • The extreme distributions and are the distributions we wish to show computationally indistinguishable.
   • Any adjacent distributions and differ by only one application of a cryptographic primitive. Often we replace a cryptographic primitive by its idealization between adjacent distributions (for example, replace the output of a pseudorandom generator with a truly random string).
2. Since they differ only in one simple aspect, it is (comparatively) easier to prove that adjacent distributions are computationally indistinguishable (in the security parameter).
3. Since computational indistinguishability is transitive across a polynomial number of distributions, we conclude that the endpoints and are computationally indistinguishable, as desired.

Often the order in which the hybrids are defined is significant, and the proof will not work with a different hybridization of the two distributions.