Interactive Functions and Algorithms

A probabilistic interactive function is a probabilistic state-transition function, usually on a countable domain. Hence it is characterized by three sets /, O, and 5, the sets of possible inputs, outputs, and states, respectively, and a probabilistic function (see above) / 7 x 5 — O x 5. (In contrast to the field of non-cryptologic protocol specification, the functions themselves, and not finite descriptions of them, are used here. Anyway, they are mainly used to model the unknown behaviour of computationally unrestricted attackers.) 

Most systems in cryptology are synchronous. For the programs, this means that they are defined in rounds In each round, they receive some messages at the 

As complexity is not considered here, the internal state of a component is not really interesting. Hence a notion that describes the pure input-output behaviour of a component might be more appropriate, e.g., as in [Gray92, Schu94]. However, the behaviour of connected components is much easier to describe with state-transition functions. 

With both interactive functions and interactive algorithms, some details can be formalized in various ways  

If the number of entities in a system and the connection structure is fixed in the protocol, each output of a state-transition function can be a tuple of values that represent the outputs on different channels. The individual output sets should be augmented by a special element nojoutput. With Turing machines, one can either use output tuples, too, or a separate tape for each simplex channel. 

---