Multi-Party Function Evaluation in Initialization

The obvious advantage of this construction is that the complexity of authentication and disputes is independent of the number of risk bearers. The disadvantage is that a general suitable key-generation protocol is very inefficient however, see the last subsection for more efficient special cases. (Moreover, due to problems with definitions of multi-party function evaluation protocols, I did not even dare to call the security considerations below a proof sketch.) 

For the transformation of an arbitrary key-generation protocol Gen with one risk bearer into a protocol Gen that generates keys with the same distribution, but in a way that many risk bearers can trust them, a multi-party function evaluation protocol is used. 

As mentioned in Section 4.4.1, Related Work in Cryptology , multi-party protocols have almost exclusively been considered for the evaluation of (probabilistic) functions. The informal definition of a multi-party protocol that securely evaluates a function/on n inputs, jcj,. .., x , which are assumed to be contributed by n different users, is that the protocol has exactly the same effect for all users, honest and dishonest, as an evaluation by a trasted host would have. Such a trusted host would receive each input x,- secretly from the i-th user, apply/, and output y. =f(x, . .., x ) to everybody (or, if/is probabilistic, a value y distributed 

For discussions of the many pitfalls lying between this intuitive idea and a formal definition, see [Beav91, MiRo91]. (Furthermore, [MiRo91] only considers deterministic functions.) 

Variants exist where each user obtains a different output y,- secretly from the trusted host. If probabilistic functions are considered, the results may be correlated, i.e., there is a global probabilistic function F that maps n-tuples (xj,. .., x ) to w-tuples (yj. y , and the i-th user obtains y,- as a result. 

---