0
$\begingroup$

I'm learning cryptography recently. I read that for game-based formal security analysis, it is important to embed the hard instance during reduction. Does "hard instance" mean hard-to-solve problems like DDH (Decisional Diffie Hellman) assumption? If so, my understanding of "embedding the "hard instance" during reduction" is to calculate the adversary's advantage by including the probability of breaking the assumption.

Many thanks!

$\endgroup$

1 Answer 1

1
$\begingroup$

Does "hard instance" mean hard-to-solve problems like DDH (Decisional Diffie Hellman) assumption?

Basically yes, it means a specific instance of a hard problem - in the DDH case, for example, it means one particular challenge $(g^a, g^b, g^c)$.

Reductions work by showing that if you have a method/algorithm for solving one problem (usually, breaking a protocol), then you can use the same algorithm to solve the hard problem like DDH. This proves that breaking the protocol is at least as hard as breaking DDH. And by the converse, if DDH is hard, then the protocol is secure.

Reductions usually start by obtaining an instance of the hard problem, for example, the DDH problem. Then you'd say something like "suppose $\mathcal{A}$ is an adversary/algorithm that can break XXX protocol with advantage $\epsilon$". Next, you'd show how you can turn your instance of the DDH problem $g^a, g^b, g^c$ into values that you could give to $\mathcal{A}$, so that whatever $\mathcal{A}$ returns, you'd learn the answer to the DDH instance (maybe with some lower probability than $\epsilon$, which is known as a "loss of tightness"). It is this way of somehow turning the DDH instance into something you can give to $\mathcal{A}$ that is referred to as "embedding" an instance of the DDH problem into your protocol.

But you'd work out the probabilities, and if you could show that your advantage in solving the DDH problem using $\mathcal{A}$ is non-negligible if $\epsilon$ is, then you've successfully shown a reduction to the security of your protocol from DDH.

$\endgroup$
3
  • $\begingroup$ Thanks a lot. I'm more clear about the concept now. Could you also recommend me some related papers/examples about embedding hard instances during reduction for security proof? $\endgroup$
    – Chandler
    Feb 22, 2022 at 2:51
  • $\begingroup$ Perhaps a proof of security for the ElGamal encryption scheme? For example, the first page of this PDF: people.eecs.berkeley.edu/~daw/teaching/cs276-s06/l19.pdf $\endgroup$ Feb 22, 2022 at 3:19
  • $\begingroup$ Thank you. this is really helpful. Besides, I've found a youtube video (youtube.com/watch?v=ITrvnH8pfPw) and a blog (medium.com/oxbridge-inspire/…) that also provides some explainations about reduction proof. Hope it could be helpful to whom has same confusions with me. $\endgroup$
    – Chandler
    Feb 25, 2022 at 12:28

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.