### 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.

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.

Available format(s)
Category
Foundations
Publication info
Published elsewhere. MINOR revision.Information Security and Cryptography, Springer, 2021
Keywords
hybrid argumentproof
Contact author(s)
marc fischlin @ cryptoplexity de
mail @ arno-mittelbach de
History
Short URL
https://ia.cr/2021/088

CC BY

BibTeX

@misc{cryptoeprint:2021/088,
author = {Marc Fischlin and Arno Mittelbach},
title = {An Overview of the Hybrid Argument},
howpublished = {Cryptology ePrint Archive, Paper 2021/088},
year = {2021},
note = {\url{https://eprint.iacr.org/2021/088}},
url = {https://eprint.iacr.org/2021/088}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.