11

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.

Yasser Sobhdel
  • 654
  • 6
  • 16

2 Answers2

10

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.

Sadeq Dousti
  • 16,479
  • 9
  • 69
  • 152
  • 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? – Dave Clarke Nov 14 '10 at 12:20
  • Well, I don't think so. I found another reference that conforms to my definition. – Sadeq Dousti Nov 14 '10 at 12:29
  • 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. – Daniel Apon Nov 14 '10 at 12:44
  • Deterministic sounds like a possible synonym. – Dave Clarke Nov 14 '10 at 12:45
  • @Dave: I beg to differ. Deterministic describes something else. In fact, both zero-knowledge and UC simulators are probabilistic machines. – Sadeq Dousti Nov 14 '10 at 12:47
  • 5
    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.

     – Alon Rosen Nov 14 '10 at 12:47
  • Thanks, I understand better. It's not my field and I was trying to establish connections with what I already know. – Dave Clarke Nov 14 '10 at 12:50
  • @Alon: Very useful, indeed. I also found a Crypto'98 paper in which the term was used. Please see the updated answer. – Sadeq Dousti Nov 14 '10 at 12:55
3

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.