6
$\begingroup$

I am currently reading Yehuda Lindell's amazing tutorial on simulation proof technique and trying to write my own proof for the first time. In page 4 of this tutorial it is mentioned that

[...] The value $a$ must therefore be written on the advice tape of the reduction algorithm.

and I also knew that $a$ in context of secure computation represents the parties' inputs (as prof. Lindell said in page 3 of the tutorial).

For proving security of oblivious transfer in semi-honest case (page 13), reduction algorithm $A$ is given $\sigma , b_\sigma$ on its advice tape. Could I also give $b_{1-\sigma}$ (other party's input) to $A$ on its advice tape if needed (which is in my case)?

$\endgroup$

1 Answer 1

3
$\begingroup$

Yes.

We work under the assumption that the protocol is not secure, which means that for infinitely many $n$, there is a pair of inputs $(x,y)$ on which the simulation fails (i.e., when the inputs are $x$ and $y$ the view generated by the simulator for at least one of the parties can be distinguished from a real one). Thus, when running on security parameter $n$, all non-uniform algorithms can be given $(x,y)$ as advice.

By the way, the reason why adversaries are only given $\sigma$ and $b_\sigma$ in this case (instead of $\sigma$ and $(b_\sigma,b_{1-\sigma})$) is that the given simulator always succeeds when $b_{1-\sigma} = 0$, so since we give an input pair where the simulator fails, it must be that $b_{1-\sigma} = 1$ and there is no need to give it explicitly.

$\endgroup$
1
  • $\begingroup$ I am aware of the fact that there is no need for explicitly giving $b_{\sigma-1}$ here but as I mentioned I need providing all inputs as advice to my reduction which you explained is possible. Thanks for you time $\endgroup$
    – Mhy
    Commented Jul 9, 2016 at 18:44

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.