Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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
    
could you give me this paper to look at? –  Nax Sep 6 '13 at 14:18

1 Answer 1

up vote 3 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
2  
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

 
discard

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.