On the verifiability of two-party algebraic protocols (Q1083426)

Two-party communication protocols for public-key cryptosystems are studied. The formal models are based on the definitions given by \textit{D. Dolev} and \textit{A. Yao} [IEEE Trans. Inf. Theory IT-29, 198-208 (1983; Zbl 0502.94005)]. While the main concern of Dolev and Yao was security, the subject of the present paper is the 'verifiability' of protocols. If a protocol is both sender-verifiable and receiver-verifiable, then either participant can detect when a false or altered message has been injected into the system and can refuse to respond to such a message. Hence, the power of a saboteur can be severely limited if at each stage the participants refuse to continue the exchange unless the last message received complies with the protocol. This means that the message authentication problem of \textit{W. Diffie} and \textit{M. Hellman} [Proc. IEEE 67, 397-427 (1979)] can be solved. To formally describe the notion of verifiabiality, 'sender-verification sequences' and 'receiver-verification sequences' are introduced; if a protocol has a strong sender-verification (receiver-verification) sequence, then there is a simple algorithm that the sender (resp., receiver) can use to determine at each state whether the last message received complies with the protocol. The main results are characterization theorems for both symmetric cascade protocols and symmetric name-stamp protocols that have strong sender-verification sequences or strong receiver-verification sequences. In addition, characterization theorems for nonsymmetric cascade protocols and non- symmetric name-stamp protocols that have verification sequences that are not necessarily strong are developed.