6
$\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$
12
$\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$

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.