E ciency. Each application may have its own set of requirements on the e ciency of a key estab- lishment protocol. For example, secure mobile communications generally require a \light- weight" protocol, as a mobile device is usually computationally less powerful than a wired one. As a second example, a network layer security application has far more stringent requirements on the e ciency of key establishment than does an upper layer application. Factors that contribute to the e ciency of a key establishment protocol include (1) the number of moves (or ows, passes) of messages between two participants, (2) the length of messages communicated between the participants (measured in bits), (3) the computational cost invested by both participants, (4) the size of secure storage, (5) the degree of pre- computation (which is especially important if the protocol is intended to be used with computationally weak devices), and so on. One of the challenges that face a protocol designer is to arrive at a key establishment protocol that would not only minimize the rst four factors but also maximize the fth factor, while maintaining the goals of the protocol. Optimally e cient protocols that rely on secret key cryptosystems and/or a KDC have been proposed in [8, 24]. Among public key based protocols, Xxxxxx and Xxxxxx'x pro- posals [6] minimize the computational requirements of a less powerful participant. These protocols are particularly suitable for applications where one of the two participants is computationally weak.
E ciency. The protocol presented in this paper is very e cient, since almost everything can be precomputed o -line for the clients, while achieving a strong level of security. The amount of memory available on the clients may provide a trade-o : { by storing many distinct triples (yi; i; i) one increases the security level, but one hashing and one XOR have to be performed on-line; { by storing many H1(ck i), for each (yi; i; i), for several values of the counter, one increases e ciency, since only one XOR has to be performed on-line.
