Graph design for secure multiparty computation over non-Abelian groups

Recently, Desmedt et al. studied the problem of achieving secure n-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 G. They showed three results for the n-product function f _G (x ₁,...,x _n ) :∈=∈x ₁ •x ₂ •...•x _n , where the input of party P _i is x _i ∈ ∈G for i∈ ∈{1,...,n}. First, if then it is impossible to have a t-private protocol computing f _G . Second, they demonstrated that one could t-privately compute f _G for any in exponential communication cost. Third, they constructed a randomized algorithm with O(n t ²) 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 ε>∈0, one can design a randomized algorithm for any using O(n ³) 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 t∈=∈O(n ^1∈-∈ε ) (again for any fixed ε>∈0). Our results extend to the more general function where m∈≥∈n and each of the n parties holds one or more input values.