Cryptology ePrint Archive: Report 2021/088

An Overview of the Hybrid Argument

Marc Fischlin and Arno Mittelbach

Abstract: The hybrid argument is a fundamental and well-established proof technique of modern cryptography for showing the indistinguishability of distributions. As such, its details are often glossed over and phrases along the line of "this can be proven via a standard hybrid argument" are common in the cryptographic literature. Yet, the hybrid argument is not always as straightforward as we make it out to be, but instead comes with its share of intricacies. For example, a commonly stated variant says that if one has a sequence of hybrids $H_0,...,H_t$, and each pair $H_i$, $H_{i+1}$ is computationally indistinguishable, then so are the extreme hybrids $H_0$ and $H_t$. We iterate the fact that, in this form, the statement is only true for constant $t$, and we translate the common approach for general $t$ into a rigorous statement.

The paper here is not a research paper in the traditional sense. It mainly consists of an excerpt from the book "The Theory of Hash Functions and Random Oracles - An Approach to Modern Cryptography" (Information Security and Cryptography, Springer, 2021), providing a detailed discussion of the intricacies of the hybrid argument that we believe is of interest to the broader cryptographic community. The excerpt is reproduced with permission of Springer.

Category / Keywords: foundations / hybrid argument, proof

Original Publication (with minor differences): Information Security and Cryptography, Springer, 2021

Date: received 23 Jan 2021

Contact author: marc fischlin at cryptoplexity de,mail@arno-mittelbach de

Available format(s): PDF | BibTeX Citation

Note: Contains an excerpt from "The Theory of Hash Functions and Random Oracles-An Approach to Modern Cryptography" (Information Security and Cryptography, Springer, 2021); reproduced with permission.

Version: 20210127:132719 (All versions of this report)

Short URL: ia.cr/2021/088


[ Cryptology ePrint archive ]