7
$\begingroup$

In many cases why going through the security proofs I have seen that some does it using a blackbox reduction to some known hardness assumption DDH and others do it using a hybrid argument by arguing the indistinguishability between the hybrids is equivalent to adversary's advantage in the DDH game.

What I don't understand how to decide when to use blackbox reduction techniques and when to use the hybrid one. Is there any good way to know which one is a good fit while proving security?

$\endgroup$

2 Answers 2

13
$\begingroup$

There is actually no difference between what you are describing. One of the issues with writing proofs, is that a separate reduction must be proven for every element of the construction (you cannot reduce security to a hash function and DDH in one shot). In order to facilitate this, one writes hybrid games and then proves each hybrid via a reduction. In some cases, you only need to reduce to one thing (e.g., DDH), in which case there is no need for any hybrids. However, even in these cases, some people prefer writing very clear hybrid games. The question of how to know what is best is really just experience and more experience. I refer you to Victor Shoup's tutorial on game-based proofs. I also have a tutorial on simulation-based proofs. These can help.

$\endgroup$
0
0
$\begingroup$

Yehuda Lindell's answer is very informative

([Victor Shoup, "Sequences of games: a tool for taming complexity in security proofs", IACR2004/332]: with examples too,

[Yehuda Lindell, "How To Simulate It – A Tutorial on the Simulation Proof Technique", IACR2016/046]).


I just want to menstion some other resources which might be helpful.

  • About hybrid arguments, Oded Goldreich's Books, [Gol04], foundation of cryptography, vol 1: basic tools, section 3.2.2: "Indistinguishability by repeated experiment" is also useful.

  • Also, a rather new report [Marc Fischlin, Arno Mittelbach. "An Overview of the Hybrid Argument", IACR2021/088] is helpfull: General idea of using hybrid arguments (in the below picture) and four version of the hybrid arguments:

    1-section 3.1 Constant Number of Hybrids,

    2-section 3.2 Polynomial Number of Hybrids with a Universal Distinguishing Bound,

    3-section 3.3 Polynomial Number of Hybrids: Non-uniform Variant,

    4-section 3.4 Polynomial Number of Hybrids: Uniform Variant


enter image description here


$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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