Counting Method for Multi-party Computation over Non-abelian Groups

Publication Type:
Conference Proceeding
LNCS - Cryptology and Network Security - Proceedings of the 7th International Conference, 2008, 5339 pp. 162 - 177
Issue Date:
Full metadata record
Files in This Item:
Filename Description Size
Thumbnail2013005439OK.pdf463.18 kB
Adobe PDF
In the Crypto'07 paper [5], Desmedt et al. studied the problem of achieving secure n-party computation over non-Abelian groups. The function to be computed is f G (x 1,...,x n ) :?=?x 1 ·...·x n where each participant P i holds an input x i from the non-commutative group G. The settings of their study are the passive adversary model, information-theoretic security and black-box group operations over G. They presented three results. The first one is that honest majority is needed to ensure security when computing f G . Second, when the number of adversary t=?n2?-1, they reduced building such a secure protocol to a graph coloring problem and they showed that there exists a deterministic secure protocol computing f G using exponential communication complexity. Finally, Desmedt et al. turned to analyze random coloring of a graph to show the existence of a probabilistic protocol with polynomial complexity when t?
Please use this identifier to cite or link to this item: