This question concerns the security of the sender in the Naor Pinkas OT. The protocol can be found here.

We can reduce the security to the DDH assumption. How exactly is this done? Can someone construct an adversary that shows this reduction?

To simplify the question. Working with the simulation based definitions the real and simulated views leave us with the job of showing $(g^a, g^b, g^c, g^{a\cdot b})$ and $(g^a, g^b, g^{a\cdot b}, g^c)$ are indistinguishable.

Let us assume that $D$ can distinguish these two distributions (can distinguish with probability that is non negligible).

That is, $$|\mathsf{Pr}[(D (g^a, g^b, g^c, g^{a\cdot b}) = 1] - \mathsf{Pr}[(D (g^a, g^b, g^{a\cdot b}, g^c)) = 1]|$$ is non negligible.

What adversary can be constructed that breaks the DDH assumption? That is we must construct $A(D)$ (it takes in $D$, as an input) such that $$|\mathsf{Pr}[(A(D) (g^a, g^b, g^{a\cdot b}) = 1] - \mathsf{Pr}[(A(D) (g^a, g^b, g^c) = 1]|$$ is non negligible.



1 Answer 1



Due to DDH we have that $(g^a, g^b, g^{a\cdot b}, g^c)$ and $(g^a, g^b, g^{c'}, g^c)$ are indistinguishable (where $c'$ is uniformly random and independent of $c$). By the same reason, $(g^a, g^b, g^c, g^{a\cdot b})$ and $(g^a, g^b, g^{c}, g^{c'})$ are indistinguishable.

Can you see how to put things together?


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.