# Where does the meaning of reduction to a hard problem lie?

Given you a protocol, if we can reduce breaking the protocol to a hard problem, such as DLP or CDH, then we can say that this protocol is secure.

Theoretically speaking, reduction is a good method to prove the security of a protocol. As to key-exchange protocols, if the reduction method uses the adversary as a subroutine, then the simulator will construct an algorithm. If the adversary can break the protocol under a certain model then the simulator can solve a hard problem, say CDH.

But in practice, can the algorithm constructed by the simulator can be realised with a computer program? And does it really work?

-

The algorithm describing the simulation can indeed be "implemented" - thats essentially the proof strategy which the simulator follows.

However, the algorithm implementing the adversary (whom the simulator communicates with) is another story. Since you want the reduction to hold (typically) for any PPT adversary, you do not know how the adversary works.

The reduction simply says that you can nicely give a problem instance to the adversary (without the adversary recognising this, i.e., the simulation is indistinguishable from the real environment from the point of view of the adversary) and then when the adversary halts with a certain output, you solve the respective problem (with a non-negligible probability). However, you do not know how the adversary manages to do this - since there may be different strategies for the adversary. Nevertheless, you do not really care about that, since if your reduction is tight (and the security model is meaningful) you have what you want for proving reductionst security.

Remark: Actually, there are some types of reductions which assume having access to the adversaries internal structure (the code of the adversary). These are non-black box reductions. What one most often encounters in proofs of cryptographic schemes are black box reductions, meaning that the simulator can use the adversary only as a black box without knowledge of the internal workings of the adversary (this is also what I described above).

Another technique which is used in reductionist proofs is rewinding (e.g., in zero knowledge protocols), i.e., the simulator rewinds the adversary to some state when encountering a "bad" state and then starts the adversary from this step again hoping that such a "bad" state will not encounter this time. However, this rewinding techniqe should be used with care.

Sometimes one also encounters that the simulation controls the randomness (random input tape) of the adversary.

Example of a simple reduction (as answer to your comment): Let us suppose the Pedersen commitment scheme working in a group $G$ of prime order $p$. Then we have two generators $g, h$ with $\log_g h$ unknown and the system paramters are $pp=(G,p,g,h)$ (lets write $pp\leftarrow Setup(1^k)$ with $k$ being the security parameter). To commit to a value $m\in Z_p$ one chooses $r\in_R Z_p$ and computes the commitment as $c=g^mh^r$ (lets write this as $(c,d)\leftarrow Commit(m)$, where $d$ is the decomittment value, here $(m,r)$). Opening a commitment is giving away $d=(m,r)$ and checking whether $c\stackrel{?}{=}g^mh^r$ holds (lets write this as $b\leftarrow Open(c,d)$ with $b=true$).

Now, the binding property of a commitment holds if for any PPT adversary $A$ we have that:

$Pr[m\neq m' \land b'=b=true ~~|~~ pp\leftarrow (1^k), (c,d,d')\leftarrow A(pp), b\leftarrow Open(c,d), b'\leftarrow Open(c,d')] \leq negl(k)$

where $negl(\cdot)$ is a negligible function. Essentially, in our Pedersen setting an adversary needs to produce a commitment $c$ such that the opening accepts $(m,r)$ and $(m',r')$ with $m\neq m'$. This, however, means that we have $g^mh^r=g^{m'}h^{r'}$. We will come back to that fact later:

Now we reduce the discrete log problem in $G$ to the binding property of the Pedersen commitment scheme, i.e, if there is an adversary breaking the binding property of Pedersen commitments with non-negligible probability, then we can solve DLP in $G$ with the same probabiltiy. This reduction is very easy, since the simulator has not to simulate any queries (but only to provide parameters to the adversary which are indistinguishable from those in the real attack).

Simulator: Is given an instance $y$ of the discrete logarithm problem in $G$ with respect to generator $g$.

Now the simulator sets $pp=(p,G,g,y)$ and thus embeds the DL instance into the public parameters. Note that for an adversary these parameters are absolutely perfect.

Run the adversary $A$: Now the simulator runs $A(pp)$ and if $A$ manages it to output $(c,d,d')=(c,(m,r),(m',r'))$ with $m\neq m'$, then the reduction applies (note, we do not make any assumption how $A$ manages it produce the output).

Compute solution: Now the simulator has received from $A$ values $(c,(m,r),(m',r'))$ and knows that $c=g^my^r=g^{m'}y^{r'}$ (we have seen this above and come back to that now). This also implies that $r\neq r'$. Furthermore, when taking $\log_g c$ we have $m+r\alpha \equiv m'+r'\alpha \pmod{p}$. This gives when doing a bit arithmetic $\alpha\equiv (m-m')(r'-r) \pmod{p}$. And since the simulator knows $m,m',r',r'$ it can compute $\alpha \in Z_p$. Now, it must hold that $y=g^\alpha$ and the simulator outputs $\alpha$ as solution to the DLP instance $y$.

So what this mean: If there exists an efficient adversary $A$ which is able to break the binding property of the Pedersen commitment with non negligible probability, then we can build a solver to the DLP which uses $A$ as a black box, has the same probability of success and requires a little more runtime (essentially computing $\alpha$ from $m,m',r,r'$).

-
Do you know of any reductions that specifically run the adversary with different randomness? $\hspace{.58 in}$ Everything I've seen either completely ignores the adversary's randomness or has the reduction $\hspace{.77 in}$ fix the adversary's randomness to something chosen randomly and then proceeds from there. $\hspace{.92 in}$ –  Ricky Demer Oct 14 '13 at 7:58
This is for instance used in the meta-reduction for discrete log based signatures here. I've also seen it elsewhere (if I remember right), but I cannot find any paper at the moment. –  DrLecter Oct 14 '13 at 8:12
As far as I can see, that's not "used in" the meta-reduction, it's just "handled by" the meta-reduction. $\:$ (i.e., the meta-reduction works even if the inner reduction does that.) $\:$ Also, I'll make clear now that I'm not talking about the reduction controlling the outputs of a random oracle. $\;\;\;$ –  Ricky Demer Oct 14 '13 at 9:25
it's hard for me to understand the Note, can you illustrate with an example? –  T.B Oct 14 '13 at 11:10
I have edited the answer. Hopefully now it is better understandable. @Ricky Demer: Now I got a bit confused and am no longer sure that I have seen this "running differet copies with different random coins". I never have used such a technique by myself ... but isnt that what here is modeled by the "Launch" operation? –  DrLecter Oct 14 '13 at 11:49

The idea of proofs by reduction is that it should be possible to turn a real adversary into an algorithm doing some "useful" computation. So yes and yes.

However, sometimes, reductions are weak, in the sense that even if the real adversary is feasible (can be run in reasonable time on reasonable computers), the resulting algorithm doesn't have to be feasible. The algorithm can be constructed as a computer program, but it doesn't really work. So that's yes and no.

Sometimes, we also have even weaker proofs, so-called existence proofs. They only prove that if an adversary exists, then an algorithm doing some "useful" computation exists. Which means that even if we are given an adversary, we don't really know how to construct the algorithm doing that "useful" computation. So that's no and no.

Modern cryptography recognizes all of these differences. Reductions that work are best. Weak reductions are considered solid evidence of security, but leaves something to be desired. The even weaker reductions are sometimes considered evidence of security, and sometimes leave a lot to be desired.

-