This is a follow-up question to Mikero’s answer to Simulation-based proofs and universal composability proofs.

Let there be some protocol $\pi$ running between two parties $A$ and $B$. Furthermore, assume that I have proven $\pi$ secure using a stand-alone simulation-based proof. That is, I have written some proof $\mathsf{P}$, constructing a simulator for $A$ (and later for $B$) in the ideal world that interfaces with adversary $\mathcal{A}$ in a real-world execution of $\pi$ where it pretends to be $B$.

This results in sequential composability. Now, I would additionally like to prove security under parallel composition, but avoid the increased complexity of a full UC proof.

I understand that one can assume adversary $\mathcal{A}$ to be a dummy adversary (see the answer in that previous question, a combination with the external environment). If the simulators in my proof $\mathsf{P}$ do not make use of rewinding arguments and instead run and interfere with $\mathcal{A}$ straightline, is this a valid argument to show security under parallel composition?


1 Answer 1


The answer to your question (surprisingly) depends on whether the protocol is perfectly secure or not. I refer you to the following paper.

Information-Theoretically Secure Protocols and Security Under Composition by Kushilevitz, Lindell, Rabin.

They prove the following (theorem statements copy/pasted from their intro):

  • There exist protocols that are statistically secure in the stand-alone information theoretical model and are proven secure using straight-line black-box simulation, and yet are not secure under concurrent general composition.

  • Every protocol that is perfectly secure in the stand-alone model, and has a straight-line black-box simulator, is secure under concurrent general composition.

That being said, this result seems to heavily rely on specifics and edge cases of the standard security definitions. I would say that the spirit of your suggestion (straight-line, black-box, standalone implies UC) is very reasonable and applies in all reasonable situations.

  • $\begingroup$ Thanks a lot, very interesting! $\endgroup$
    – Simulator
    Jan 30 at 17:56
  • 1
    $\begingroup$ Theorem 5 of the paper you point to mentions a very reasonable requirement. start synchronization is sufficient as a formal argument for security under parallel composition. $\endgroup$
    – Simulator
    Jan 30 at 18:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.