Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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!
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.
