Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|improve this question
up vote 6 down vote accepted

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: ε-distinguishability implies ε/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.

share|improve this answer
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. – LRM Sep 10 '13 at 15:37

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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