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.
$\begingroup$
$\endgroup$
Add a comment
|
$\begingroup$
$\endgroup$
8
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.
answered Nov 14 '10 at 12:15
-
$\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 '10 at 12:20
-
$\begingroup$ Well, I don't think so. I found another reference that conforms to my definition. $\endgroup$ Nov 14 '10 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 '10 at 12:44
-
$\begingroup$ Deterministic sounds like a possible synonym. $\endgroup$ Nov 14 '10 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 '10 at 12:47
$\begingroup$
$\endgroup$
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.