1
$\begingroup$

I read some papers which studied the relation between the fault tolerance in secure multiparty computation and the connectivity of the underlying communication graph. Here I consider information-theoretic security. By the paper The Byzantine Generals Strike Again, in the case where the adversaries are malicious and their behaviors are not restricted, to achieve correctness and security, the number of adversaries must be less than one half of the connectivity of the communication graph. By another paper Connectivity requirements for Byzantine agreement under restricted types of failures, if the behaviors' of the adversaries are restricted to omission or stopping faults, then to achieve correctness and security, it is enough that the number of adversaries is less than the connectivity of the communication graph.

In my problem, I only consider semi-honest adversaries. I wonder is there any result for this case for the relation between the fault tolerance and the connectivity of the communication graph.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.