Score:2

Expanding stand-alone simulation-based proofs to UC proofs

ca flag

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?

Score:1
us flag

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.

Simulator avatar
ca flag
Thanks a lot, very interesting!
Simulator avatar
ca flag
Theorem 5 of the [paper](https://eprint.iacr.org/2009/630.pdf) you point to mentions a very reasonable requirement. _start synchronization_ is sufficient as a formal argument for security under parallel composition.
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.