4
$\begingroup$

I am reading the book "Efficient Secure Two-Party Protocol". A question came to my mind. why has the author used a probabilistic polynomial time algorithm for security definition of ideal/real model in the semi-honest model, but used a non-uniform probabilistic polynomial time algorithm in the malicious model? Thanks for considering my question.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
6
$\begingroup$

The non-uniformity needed for the proofs of security is in the distinguisher (in order to get advice as to which inputs the protocol breaks on in the reduction). However, if you are already assuming non-uniformity for the distinguisher, then you may as well assume it for the real adversary. But, if you assume it for the real adversary then you also need it for the simulator since the simulator needs to be as strong as the adversary in order to be able to run it.

The above is all true for the malicious case. However, in the semi-honest case, you still need non-uniformity for the distinguisher, but there is no adversary; the simulator just needs to generate the view of the semi-honest adversary in the protocol. For this, it suffices to use a uniform machine. Having said this, nothing would be lost by taking a non-uniform simulator; it’s just that we don’t need it to prove security of protocols (at least, I don't know of any protocol for semi-honest that requires a non-uniform reduction; if there is such a case, then they can just use non-uniform simulation, as I mentioned).

Improve this answer
$\endgroup$
2
  • $\begingroup$ Can you perhaps present some concrete examples where, if you were assuming the distinguisher was uniform, certain reduction could not take place? I don't think this is well motivated in your book, or at least I'm missing it. Thank you! $\endgroup$
    – Daniel
    Commented Apr 5, 2021 at 17:19
  • $\begingroup$ EDIT: I found where you use it at the bottom of page 69. I wonder if there is no way around it, and if the use of non-uniformity is actually quite common in other MPC protocols, or if this is something that you needed for this particular proof, but doesn't usually appear in other protocols. $\endgroup$
    – Daniel
    Commented Apr 5, 2021 at 20:42

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.