Precise definition for cryptographic protocol?

Question

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)

Answer 1

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 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 (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 (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.

Answer 2

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, Goldreich, Goldwasser, Micali and Goldwasser, Micali, Rivest 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). 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 3

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.