Secure multiparty protocols and zero-knowledge proof systems tolerating a faulty minority (Q809588)

Consider the problem of computing a function \(f(x_ 1,x_ 2,...,x_ n)\) where input arguments are distributed among n processors (one argument per processor), without revealing individual inputs as an additional requirement. The processors are connected by secure communication lines, however no single processor is completely reliable, hence it is not possible to arrange for some central, trusted processor to simply collect the inputs and return the function value. There is also a possibility that some number of processors are corrupted by a resource - unbounded adversary that may attempt to interface with the protocol, or to gain extra information. The article presents a novel solution of the problem, i.e. a multiparty protocol tolerating faults in \(t<n/2\) processors, improving previous solutions for \(t<n/3\) fault processors. Besides the protocol the author introduces concise definitions for security and fault-tolerance. It is stressed that not only the information obtained by the adversary, but also the adversary influence on the final result (through the choice of corrupted processors and their inputs) must be considered. The notion of relative resilience is introduced and formally defined. This approach allows for the unification of privacy and correctness issues in defining security, moreover it allows comparisons between arbitrary protocols, not only a direct measurement against a fixed standard.