<p>There are several definitions of cryptographic protocols, each of which tries to capture some particular features of interest.</p>

<p>I start with <a href="http://portal.acm.org/citation.cfm?id=22178" rel="nofollow">Goldwasser, Micali, and Rackoff</a> definition (1985): They first defined <strong>interactive Turing machines</strong> (ITM), based of which they defined (two-party) interactive protocols. An ITM is a special TM equipped with one read-only and one write-only communication tape. A pair of ITMs  constitutes an <strong>interactive protocol</strong> if the read-only communication tape of party A coincides with the write-only communication tape of party B, and vice versa. The power of parties and the adversary model is then defined accordingly (see the paper).</p>

<p>The multi-party case was later defined by <a href="http://portal.acm.org/citation.cfm?id=28395.28420" rel="nofollow">Goldreich, Micali, and Wigderson</a> (1987). They modeled a secure multi-party game in an elegant way, though the paper (as Goldreich states himself) leaves a lot of doors open. For a more concrete discussion see: <a href="http://www.wisdom.weizmann.ac.il/~oded/pp.html" rel="nofollow">http://www.wisdom.weizmann.ac.il/~oded/pp.html</a>.</p>

<p>Finally, a much stronger model was proposed by <a href="http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=959888&amp;tag=1" rel="nofollow">Canetti</a> (2001). In his paper, he defines a framework called Universal Composability (UC), based on which he defines the cryptographic protocols and puts forward a notion of security for them.</p>

<p>As far as I recall, the last paper cites a lot of other works which try to define and model security protocols. Therefore, I strongly advise you to take a look at it.</p>

CC BY-SA 2.5
2010-12-21T18:27:12.960Z
I added a separate answer in which I try to clarify the distinction between syntax and the security of a protocol. My answer also refers to the pointers in Sadeq's answer.
Alon Rosen
CC BY-SA 2.5
2010-12-22T08:44:47.233Z
@Alon: Thanks. I always enjoy reading your posts.
Sadeq Dousti
CC BY-SA 2.5
2010-12-21T09:02:43.270Z
2010-12-21T09:02:43.270Z
Sadeq Dousti
<p>Generally spealing, the definition of a cryptographic protocol consists of two different parts: <strong>syntax</strong> and <strong>security</strong>.</p>

<p>The syntax specifies the functionality of the protocol under legitimate use (dealing with issues such as key generation, correct decryption, valid signature verification, or more generally some desired output). A protocol can be totally "insecure" and still satisfy the syntax of the cryptographic task at hand.</p>

<p>The security part deals with guaranteeing that the protocol can be used safely in a cryptographic context. It specifies the access that the adversary has to the protocol, as well as what it means for the adversary to break it. </p>

<p>It is desirable that a security definition carries some "semantics" with it, in the sense that if a protocol satisfies this definition then the user is convinced that the security guarantee is meaningful (e.g. having a security definition that allows any protocol is certainly "legitimate" but it clearly doesn't guarantee any security). </p>

<p>The biggest conceptual contribution of modern cryptography is to develop a methodology for coming up with security definitions that are extremely meaningful and at the same time realizable (see <a href="http://theory.lcs.mit.edu/~cis/pubs/shafi/1984-jcss.pdf" rel="nofollow">Goldwasser Micali</a>, <a href="http://theory.lcs.mit.edu/~cis/pubs/shafi/1986-jacm.pdf" rel="nofollow">Goldreich, Goldwasser, Micali</a> and <a href="http://people.csail.mit.edu/rivest/GoldwasserMicaliRivest-ADigitalSignatureSchemeSecureAgainstAdaptiveChosenMessageAttacks.pdf" rel="nofollow">Goldwasser, Micali, Rivest</a> for prime examples of this methodology).</p>

<p>Following the works mentioned above it has become common (some would say mandatory) practice to define both syntax and security and to prove that a given protocol satisfies the given definitions (usually under some widely accepted intractability assumptions). The precise definitions to be satisfied depend on the cryptographic task at hand, and are evaluated in light of the intended application.</p>

<p>As Sadeq points out in his answer, the general syntax of protocols is defined via interactive Turing Machines (by <a href="http://theory.lcs.mit.edu/~cis/pubs/shafi/1989-siamjc.pdf" rel="nofollow">Goldwasser Micali Rackoff</a>). This definition allows to model players that "keep state" between messages that are sent and received. The GMR paper is also the first to rigorously define security for interactive protocols, and in particular what it means for a protocol to be zero-knowledge. More general security requirements are given in later papers on secure two and multi-party computation. For references to these see Sadeq's answer.</p>

CC BY-SA 2.5
2010-12-21T12:52:22.733Z
2010-12-21T18:23:16.873Z
2010-12-21T18:23:16.873Z
Alon Rosen
<p>This is a follow up answer to the edited question. As I wrote in the comment above, <strong>anything</strong> can be defined to be a protocol. The real question is whether the object you define is useful. As I wrote in my previous answer this depends on the actual definition and  on what the user wants from the protocol (which is what I tried to elaborate on in my previous answer).</p>

<p>The most common way to go about defining the syntax and security of a cryptographic protocol is to specify its intended functionality as if the users were interacting with an "ideal" black box (the functionality specifies the output of players in the protocol as a function of the players' inputs). Security (and correctness) are then obtained by requiring that for any adversary A attacking a real execution of your protocol there exists a (roughly) equally powerful adversary S that would have done equally well by attacking the ideal black box (without actual access to the protocol messages).</p>

<p>The above is known as the simulation paradigm (sometimes referred to as the real/ideal paradigm). The idea is that in the ideal world there are no attacks beyond observing the input/output relationship (which is what you indended to give away anyway by running the protocol), and hence there are also no attacks in the real world. The actual definition is slightly more involved. You can find it in the references given in Sadeq's answer.</p>

<p>An alternative, more exlicit way for defining security is the "game based" one. It involves stating explicity what it means for the adversary to break the system (think of the definition of signatures). Its advantage over the simulation based definitions is that it may be easier to realize. This is because simulation is very strong: it implies that the adversary learns <strong>nothing</strong> beyond what is intended. The advatange of the simulation approach is that it often guarantees the preservation of security under composition.</p>

CC BY-SA 2.5
2010-12-22T19:19:09.317Z
But then even public-key encryption schemes could be called "protocols". Why is RSA called an "encryption scheme" and not an "private data exchange protocol"? Surely RSA can be formulated in the way you described...
Jay
CC BY-SA 2.5
2010-12-22T19:51:39.607Z
You can call RSA a protocol if you want. This wouldn't change what it is. What really counts are the explicit syntax/security requirements that you place on the scheme you use (of course terminology is important, but it is secondary to the actual requirements). Coincidentally, public key encryption is often used as a key exchange protocol, so strictly speaking calling it a "protocol" would not be innapropriate (defining the security of key-exchange is actually a good excercise).
Alon Rosen
CC BY-SA 2.5
2010-12-22T19:57:31.453Z
Traditionally the term protocol has been reserved for schemes that involve interaction. But there are exceptions. For example, we use the term commitment schemes (and not protocols), even though in many cases these schemes are interactive. In any case, the important thing is what you require from a scheme, not how you categorize it.
Alon Rosen
CC BY-SA 2.5
2010-12-22T13:39:24.973Z
2010-12-23T13:14:08.113Z
2010-12-23T13:14:08.113Z
Alon Rosen
<p>Is there some precise definition of cryptographic protocol?
I'm asking because I have tried a few good books and they don't seem to define it (Douglas Stinson, Wenbo Mao, Trappe/Washington). The lecture notes by Goldwasser and Bellare come close, but don't really define protocols (and leave key distribution out of the protocols chapter, for example).</p>

<p>I've seen people include key management in protocols and others keeping it out; the same for secret sharing and some other topics.</p>

<p>So, does that mean there no widely-accepted definition for cryptographic protocols?</p>

<p>Edit: I'm not sure I was clear enough when I originally posted the question -- I wanted to know what usually is considered a "protocol" in cryptography and what is not (and not how I'd go about defining some particular protocol)</p>

CC BY-SA 2.5
2010-12-22T13:26:19.473Z
In my answer below I tried to explain how the definition of a protocol looks like in general. Syntactically speaking, anything can be considered a protocol. But for it to be useful in a cryptographic sense the definition should carry some functionality (preferrably the functionality that the designer intended), and additionally satisfy some meaningful security guarantee. The decision of whether what you defined is useful from a cryptographic perspective is left to the user.
Alon Rosen
<cr.crypto-security>
Precise definition for cryptographic protocol?
Jay
# Precise definition for cryptographic protocol?

(Asked by: username_0 on 2010-12-21)

Is there some precise definition of cryptographic protocol?
I'm asking because I have tried a few good books and they don't seem to define it (Douglas Stinson, Wenbo Mao, Trappe/Washington). The lecture notes by Goldwasser and Bellare come close, but don't really define protocols (and leave key distribution out of the protocols chapter, for example).

I've seen people include key management in protocols and others keeping it out; the same for secret sharing and some other topics.

So, does that mean there no widely-accepted definition for cryptographic protocols?

Edit: I'm not sure I was clear enough when I originally posted the question -- I wanted to know what usually is considered a "protocol" in cryptography and what is not (and not how I'd go about defining some particular protocol)

**Tags:** cr.crypto-security
> **Comments:**
> **username_1**: In my answer below I tried to explain how the definition of a protocol looks like in general. Syntactically speaking, anything can be considered a protocol. But for it to be useful in a cryptographic sense the definition should carry some functionality (preferrably the functionality that the designer intended), and additionally satisfy some meaningful security guarantee. The decision of whether what you defined is useful from a cryptographic perspective is left to the user.  

---

## 3 answers

### Answer by username_2 on 2010-12-21. Score: 8

There are several definitions of cryptographic protocols, each of which tries to capture some particular features of interest.

I start with [Goldwasser, Micali, and Rackoff](http://portal.acm.org/citation.cfm?id=22178) definition (1985): They first defined **interactive Turing machines** (ITM), based of which they defined (two-party) interactive protocols. An ITM is a special TM equipped with one read-only and one write-only communication tape. A pair of ITMs constitutes an **interactive protocol** if the read-only communication tape of party A coincides with the write-only communication tape of party B, and vice versa. The power of parties and the adversary model is then defined accordingly (see the paper).

The multi-party case was later defined by [Goldreich, Micali, and Wigderson](http://portal.acm.org/citation.cfm?id=28395.28420) (1987). They modeled a secure multi-party game in an elegant way, though the paper (as Goldreich states himself) leaves a lot of doors open. For a more concrete discussion see: <http://www.wisdom.weizmann.ac.il/~oded/pp.html>.

Finally, a much stronger model was proposed by [Canetti](http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=959888&tag=1) (2001). In his paper, he defines a framework called Universal Composability (UC), based on which he defines the cryptographic protocols and puts forward a notion of security for them.

As far as I recall, the last paper cites a lot of other works which try to define and model security protocols. Therefore, I strongly advise you to take a look at it.

> **Comments:**
> **username_1**: I added a separate answer in which I try to clarify the distinction between syntax and the security of a protocol. My answer also refers to the pointers in Sadeq's answer.  
> **username_2**: @Alon: Thanks. I always enjoy reading your posts.  

---

### Answer by username_1 on 2010-12-21. Score: 6

Generally spealing, the definition of a cryptographic protocol consists of two different parts: **syntax** and **security**.

The syntax specifies the functionality of the protocol under legitimate use (dealing with issues such as key generation, correct decryption, valid signature verification, or more generally some desired output). A protocol can be totally "insecure" and still satisfy the syntax of the cryptographic task at hand.

The security part deals with guaranteeing that the protocol can be used safely in a cryptographic context. It specifies the access that the adversary has to the protocol, as well as what it means for the adversary to break it.

It is desirable that a security definition carries some "semantics" with it, in the sense that if a protocol satisfies this definition then the user is convinced that the security guarantee is meaningful (e.g. having a security definition that allows any protocol is certainly "legitimate" but it clearly doesn't guarantee any security).

The biggest conceptual contribution of modern cryptography is to develop a methodology for coming up with security definitions that are extremely meaningful and at the same time realizable (see [Goldwasser Micali](http://theory.lcs.mit.edu/~cis/pubs/shafi/1984-jcss.pdf), [Goldreich, Goldwasser, Micali](http://theory.lcs.mit.edu/~cis/pubs/shafi/1986-jacm.pdf) and [Goldwasser, Micali, Rivest](http://people.csail.mit.edu/rivest/GoldwasserMicaliRivest-ADigitalSignatureSchemeSecureAgainstAdaptiveChosenMessageAttacks.pdf) for prime examples of this methodology).

Following the works mentioned above it has become common (some would say mandatory) practice to define both syntax and security and to prove that a given protocol satisfies the given definitions (usually under some widely accepted intractability assumptions). The precise definitions to be satisfied depend on the cryptographic task at hand, and are evaluated in light of the intended application.

As Sadeq points out in his answer, the general syntax of protocols is defined via interactive Turing Machines (by [Goldwasser Micali Rackoff](http://theory.lcs.mit.edu/~cis/pubs/shafi/1989-siamjc.pdf)). This definition allows to model players that "keep state" between messages that are sent and received. The GMR paper is also the first to rigorously define security for interactive protocols, and in particular what it means for a protocol to be zero-knowledge. More general security requirements are given in later papers on secure two and multi-party computation. For references to these see Sadeq's answer.


---

### Answer by username_1 on 2010-12-22. Score: 4

This is a follow up answer to the edited question. As I wrote in the comment above, **anything** can be defined to be a protocol. The real question is whether the object you define is useful. As I wrote in my previous answer this depends on the actual definition and on what the user wants from the protocol (which is what I tried to elaborate on in my previous answer).

The most common way to go about defining the syntax and security of a cryptographic protocol is to specify its intended functionality as if the users were interacting with an "ideal" black box (the functionality specifies the output of players in the protocol as a function of the players' inputs). Security (and correctness) are then obtained by requiring that for any adversary A attacking a real execution of your protocol there exists a (roughly) equally powerful adversary S that would have done equally well by attacking the ideal black box (without actual access to the protocol messages).

The above is known as the simulation paradigm (sometimes referred to as the real/ideal paradigm). The idea is that in the ideal world there are no attacks beyond observing the input/output relationship (which is what you indended to give away anyway by running the protocol), and hence there are also no attacks in the real world. The actual definition is slightly more involved. You can find it in the references given in Sadeq's answer.

An alternative, more exlicit way for defining security is the "game based" one. It involves stating explicity what it means for the adversary to break the system (think of the definition of signatures). Its advantage over the simulation based definitions is that it may be easier to realize. This is because simulation is very strong: it implies that the adversary learns **nothing** beyond what is intended. The advatange of the simulation approach is that it often guarantees the preservation of security under composition.

> **Comments:**
> **username_0**: But then even public-key encryption schemes could be called "protocols". Why is RSA called an "encryption scheme" and not an "private data exchange protocol"? Surely RSA can be formulated in the way you described...  
> **username_1**: You can call RSA a protocol if you want. This wouldn't change what it is. What really counts are the explicit syntax/security requirements that you place on the scheme you use (of course terminology is important, but it is secondary to the actual requirements). Coincidentally, public key encryption is often used as a key exchange protocol, so strictly speaking calling it a "protocol" would not be innapropriate (defining the security of key-exchange is actually a good excercise).  
> **username_1**: Traditionally the term protocol has been reserved for schemes that involve interaction. But there are exceptions. For example, we use the term commitment schemes (and not protocols), even though in many cases these schemes are interactive. In any case, the important thing is what you require from a scheme, not how you categorize it.  

---

