Does any body know any good reference for meaning of straight-line simulatability? I am currently deep into Universal Composability (UC) framework of Canetti but I can't find any good reference for meaning of straight-line simulatability. Any help is appreciated.
2 Answers
Here, "straight-line" is contrasted with "rewinding". A simulator is "straight-line" if it does not "rewind" the party it is doing the simulation for.
For instance, in a zero-knowledge protocol, the simulator usually rewinds the "verifier". In the "straight-line" sense, this rewinding does not happen.
I first saw the term "straight-line simulator" in Rafael Pass's paper (On Deniabililty in the Common Reference String and Random Oracle Models. (CRYPTO'03)) and M.Sc. thesis (Alternative Variants of Zero-Knowledge Proofs).
Edit: I found an earlier paper: Concurrent Zero-Knowledge: Reducing the Need for Timing Constraints by Cynthia Dwork and Amit Sahai, which dates back to 1998. For more pointers, see Alon Rosen's comment below.
-
$\begingroup$ I don't know the term "straight-line simulator" but to me it that "straight-line" contrasts with "branching", analogous to linear-time vs branching-time temporal logics and trace equivalence vs (branching) bisimulation equivalence. Is there anything to this? $\endgroup$ Nov 14, 2010 at 12:20
-
$\begingroup$ Well, I don't think so. I found another reference that conforms to my definition. $\endgroup$ Nov 14, 2010 at 12:29
-
$\begingroup$ Sadeq's explanation is the same as any context I've heard the terms used in. Here are some NYU lecture notes from a class in Adv Crypto from last year that discuss the topic; in particular, see Claim 8. $\endgroup$ Nov 14, 2010 at 12:44
-
$\begingroup$ Deterministic sounds like a possible synonym. $\endgroup$ Nov 14, 2010 at 12:45
-
5$\begingroup$ Earlier uses of the concept of straight line simulatability (though possibly not under this terminology) can be found in: (1) Ran Canetti, Oded Goldreich, Shafi Goldwasser, Silvio Micali: Resettable zero-knowledge (extended abstract). STOC 2000: 235-244, and (2) Ran Canetti, Marc Fischlin: Universally Composable Commitments. CRYPTO 2001: 19-40. The notion comes up in the definition of UC, because it is not possible to rewind the "environment." It came up earlier in a different context in concurrent zero-knowledge, where a rewinding simulator may run into trouble. $\endgroup$ Nov 14, 2010 at 12:47
There is no formal definition of what it means to be a straight line simulator. It is only a intuitive idea that can be used to describe things in an informal manner. I am highly skeptical about whether one can even define what it means to not rewind a machine. Indeed, rewinding a machine is itself an informal term! What we really mean by rewdinding a machine is that by we can explore many possible paths of execution of a machine from a given state. Formal arguments are then based on number of such executions we need to explore before we can obtain a trapdoor or some other information that we need to further continue our proof.