I have a two party protocol, let's call it $M$. At some point, there are $k$ steps, each one involving an oblivious transfer protocol, which is known to be secure against semi honest adversaries. These OT protocoles have independent input and outputs for different steps. Also, I have shown that $M$ is semi-honest if the parties ignore the inside states of each OT protocol. Can I say that $M$ is also secure against semi honest adversaries? Or do I have to include in the view of each adversaries the 'tape' of values involved inside the subroutine OT protocol?

Is it possible to give an answer that does not depend on how OT protocols work. For instance, lets say that a protocol $P$ uses independent instances of $M$ as a subroutine, and suppose $M$ is in fact secure against semi-honest adversaries. Can we say $P$ is secure against semi-honest adversaries?


1 Answer 1


In general, no, you cannot do that. That is why frameworks like universal composability exist.

In the UC framework, you prove a protocol, $\pi_1$ is secure according to some adversary model. You do this by showing how $\pi_1$ is indistinguishable from some ideal functionality $\mathcal{F}_1$, where the ideal functionality is secure by definition (e.g., via the use of a trusted third party).

Then, say you are developing another protocol, $\pi_2$, that calls $\pi_1$ as a subroutine. You can replace the call to $\pi_1$ with a call to $\mathcal{F}_1$ in $\pi_2$. Prove the (UC-)security of $\pi_2$ run in this manner, which should be easier since you have taken a portion of it and replaced it with a "secure-by-definition" subroutine. The theorems behind the UC framework prove that if $\pi_2$ calling $\mathcal{F}_1$ is secure, then $\pi_2$ calling $\pi_1$ instead is also secure.

Without something like this, you cannot simply inherit security of protocols called as subroutines. The picture is different, however, if the protocols are run sequentially, as mentioned in the comment below.

  • $\begingroup$ Isn't showing that a protocol is secure against semi-honest adversaries the same as showing that it is indistinguishable from some ideal functionality ? And also, what about malicious adversary? Thanks $\endgroup$ Jul 22, 2016 at 12:04
  • $\begingroup$ There are other ways to show semi-honest security. UC works for semi-honest and malicious, you just have to change how things work in the setup. $\endgroup$
    – mikeazo
    Jul 22, 2016 at 12:13
  • $\begingroup$ I highly recommend you read How To Simulate It. Especially 10.1. $\endgroup$
    – mikeazo
    Jul 22, 2016 at 12:18
  • 1
    $\begingroup$ As @mikeazo said, if you prove with UC then you can compose in any way you like, and in particular concurrently. However, its important to note that even if you just prove under the classic "stand-alone" definition, then you still get "sequential modular composition" which is exactly the same except that you have to run the different protocols one after another and not concurrently. $\endgroup$ Jul 22, 2016 at 13:44
  • $\begingroup$ Thanks, I was already aware of your wonderful tutorial. I will try to prove UC then. $\endgroup$ Jul 22, 2016 at 19:02

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.