Graph Design for Secure Multiparty Computation over Non-Abelian Groups

Xiaoming Sun, Andrew Chi-Chih Yao and Christophe Tartary

Abstract

Recently, Desmedt et al. studied the problem of achieving secure -party computation over non-Abelian groups. They considered the passive adversary model and they assumed that the parties were only allowed to perform black-box operations over the finite group . They showed three results for the -product function , where the input of party is for . First, if then it is impossible to have a -private protocol computing . Second, they demonstrated that one could -privately compute for any in exponential communication cost. Third, they constructed a randomized algorithm with communication complexity for any .

In this paper, we extend these results in two directions. First, we use percolation theory to show that for any fixed , one can design a randomized algorithm for any using communication complexity, thus nearly matching the known upper bound . This is the first time that percolation theory is used for multiparty computation. Second, we exhibit a deterministic construction having polynomial communication cost for any (again for any fixed ). Our results extend to the more general function where and each of the parties holds one or more input values.

Publication Details: In Proceedings of ASIACRYPT 2008. Lecture Notes in Computer Science, vol. 5350, pp 37 - 53, Springer - Verlag.

Download: pdf
 

Back to the list of publications (research area).

Back to the list of publications (category).

Back to the main page.