On Protocol Divertibility.

Abstract

. In this paper, we establish the notion of divertibility as a protocol property as opposed to the existing notion as a language property (see Okamoto, Ohta [OO90]). We give a definition of protocol divertibility that applies to arbitrary 2-party protocols and is compatible with Okamoto and Ohta's definition in the case of interactive zero-knowledge proofs. Other important examples falling under the new definition are blind signature protocols. A su#cient criterion for divertibility is presented and found to be satisfied by many examples of protocols in the literature. The generality of the definition is further demonstrated by examples from protocol classes that have not been considered for divertibility before. We show diverted El-Gamal encryption and diverted Di#e-Hellman key exchange. Keywords: interactive protocol, divertibility, zero-knowledge proof, Fiat-Shamir identification, blind signature, Di#e-Hellman key-exchange, El-Gamal encryption. 1