Score:0

What does hard instance mean in cryptography?

cn flag

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!

Score:1
gb flag

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.

Chandler avatar
cn flag
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?
meshcollider avatar
gb flag
Perhaps a proof of security for the ElGamal encryption scheme? For example, the first page of this PDF: https://people.eecs.berkeley.edu/~daw/teaching/cs276-s06/l19.pdf
Chandler avatar
cn flag
Thank you. this is really helpful. Besides, I've found a youtube video (https://www.youtube.com/watch?v=ITrvnH8pfPw) and a blog (https://medium.com/oxbridge-inspire/hard-problems-in-cryptography-cf0394cf8e79) that also provides some explainations about reduction proof. Hope it could be helpful to whom has same confusions with me.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.