<p>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.</p>

<p>For instance, in a zero-knowledge protocol, the simulator usually rewinds the "verifier". In the "straight-line" sense, this rewinding does not happen.</p>

<p>I first saw the term "straight-line simulator" in Rafael Pass's paper (<a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.113.8695&amp;rep=rep1&amp;type=pdf" rel="noreferrer">On Deniabililty in the Common Reference String and Random Oracle Models. (CRYPTO'03)</a>) and M.Sc. thesis (<a href="http://www.cs.cornell.edu/~rafael/papers/raf-lic.pdf" rel="noreferrer">Alternative Variants of Zero-Knowledge Proofs</a>).</p>

<p><strong>Edit:</strong> I found an earlier paper: <a href="http://www.springerlink.com/content/gwtuy0hnnakb6p7h/" rel="noreferrer">Concurrent Zero-Knowledge: Reducing the Need for Timing Constraints</a> by Cynthia Dwork and Amit Sahai, which dates back to 1998. For more pointers, see Alon Rosen's comment below.</p>

CC BY-SA 2.5
2010-11-14T12:20:54.493Z
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
CC BY-SA 2.5
2010-11-14T12:29:50.103Z
Well, I don't think so. I found [another reference](http://books.google.com/books?id=BX40yPO_J1kC&pg=PA449&lpg=PA449&dq=%22straight-line+simulator%22&source=bl&ots=eJzsrWzCM8&sig=Dgh9MH0cODBKQFJJMmEIJZetHvI&hl=en&ei=9dXfTPGtJcrChAer4qSYDQ&sa=X&oi=book_result&ct=result&resnum=1&ved=0CBUQ6AEwAA#v=onepage&q=%22straight-line%20simulator%22&f=false) that conforms to my definition.
Sadeq Dousti
CC BY-SA 2.5
2010-11-14T12:44:43.723Z
Sadeq's explanation is the same as any context I've heard the terms used in. Here are some [NYU lecture notes](http://cs.nyu.edu/courses/fall09/G22.3220-001/scribe/lecture7.pdf) from a class in Adv Crypto from last year that discuss the topic; in particular, see Claim 8.
Daniel Apon
CC BY-SA 2.5
2010-11-14T12:45:28.483Z
*Deterministic* sounds like a possible synonym.
Dave Clarke
CC BY-SA 2.5
2010-11-14T12:47:23.783Z
@Dave: I beg to differ. *Deterministic* describes something else. In fact, both zero-knowledge and UC simulators are *probabilistic* machines.
Sadeq Dousti
CC BY-SA 2.5
2010-11-14T12:47:26.810Z
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
CC BY-SA 2.5
2010-11-14T12:50:26.090Z
Thanks, I understand better. It's not my field and I was trying to establish connections with what I already know.
Dave Clarke
CC BY-SA 2.5
2010-11-14T12:55:57.350Z
@Alon: Very useful, indeed. I also found a Crypto'98 paper in which the term was used. Please see the updated answer.
Sadeq Dousti
CC BY-SA 2.5
2010-11-14T12:15:20.740Z
2010-11-14T12:54:52.700Z
2010-11-14T12:54:52.700Z
Sadeq Dousti
<p>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.</p>

<cr.crypto-security>
straight-line simulatability
Yasser Sobhdel
# straight-line simulatability

(Asked by: username_0 on 2010-11-14)

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.

**Tags:** cr.crypto-security


---

## 1 answers

### Answer by username_1 on 2010-11-14. Score: 10 | Accepted answer

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)](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.113.8695&rep=rep1&type=pdf)) and M.Sc. thesis ([Alternative Variants of Zero-Knowledge Proofs](http://www.cs.cornell.edu/~rafael/papers/raf-lic.pdf)).

**Edit:** I found an earlier paper: [Concurrent Zero-Knowledge: Reducing the Need for Timing Constraints](http://www.springerlink.com/content/gwtuy0hnnakb6p7h/) by Cynthia Dwork and Amit Sahai, which dates back to 1998. For more pointers, see username_4's comment below.

> **Comments:**
> **username_2**: 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?  
> **username_1**: Well, I don't think so. I found [another reference](http://books.google.com/books?id=BX40yPO_J1kC&pg=PA449&lpg=PA449&dq=%22straight-line+simulator%22&source=bl&ots=eJzsrWzCM8&sig=Dgh9MH0cODBKQFJJMmEIJZetHvI&hl=en&ei=9dXfTPGtJcrChAer4qSYDQ&sa=X&oi=book_result&ct=result&resnum=1&ved=0CBUQ6AEwAA#v=onepage&q=%22straight-line%20simulator%22&f=false) that conforms to my definition.  
> **username_3**: Sadeq's explanation is the same as any context I've heard the terms used in. Here are some [NYU lecture notes](http://cs.nyu.edu/courses/fall09/G22.3220-001/scribe/lecture7.pdf) from a class in Adv Crypto from last year that discuss the topic; in particular, see Claim 8.  
> **username_2**: *Deterministic* sounds like a possible synonym.  
> **username_1**: @Dave: I beg to differ. *Deterministic* describes something else. In fact, both zero-knowledge and UC simulators are *probabilistic* machines.  
> **username_4**: 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.  
> **username_2**: Thanks, I understand better. It's not my field and I was trying to establish connections with what I already know.  
> **username_1**: @Alon: Very useful, indeed. I also found a Crypto'98 paper in which the term was used. Please see the updated answer.  

---

