10
$\begingroup$

Can anyone explain (or point to a reference for) what a hybrid argument is in a security proof, and when it's convenient or preferable to use it?

Among some of the places where I've seen it mentioned, there is the paper Boneh, Sahai, Waters - Functional Encryption: Definitions and Challenges. The term standard hybrid argument is mentioned in the proof sketch of Theorem 1 within section 4.1.

$\endgroup$
7
$\begingroup$

Quoting from "On beating the hybrid argument" (by Bill Fefferman, Ronen Shaltiel, Christopher Umans and Emanuele Viola; 2012):

The hybrid argument allows one to relate the distinguishability of a distribution (from uniform) to the predictability of individual bits given a prefix. The argument incurs a loss of a factor $k$ equal to the bit-length of the distributions: $\epsilon$-distinguishability implies $\epsilon/k$-predictability.

As you're looking for a more in-deep and more practical explanation of "hybrid argument", I would like to recommend diving into the PDF "The hybrid argument", which includes a whole bunch of examples to walk through so you can wrap your head around it completely.

|improve this answer|||||
$\endgroup$
  • 5
    $\begingroup$ Thanks for your recommendation, although I was looking for some text, rather than some slides without any written explanation. I have found, though, a place where they seem to explain the hybrid argument a bit more in-depth: the book "Foundations of Cryptography: Volume 1, Basic Tools", from Oded Goldreich. $\endgroup$ – LRM Sep 10 '13 at 15:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.