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{sub}G (x{sub}1,..., x{sub}n):= x{sub}1·x{sub}2·... ·x{sub}n, where the input of party P{sub}i is x{sub}i∈G for i∈{1,..., n}. First, if t≥[n/2] then it is impossible to have a t-private protocol computing f{sub}G. Second, they demonstrated that one could t-privately compute f{sub}G for any t≤ [n/2]-1 in exponential communication cost. Third, they constructed a randomized algorithm with O(nt{sup}2) communication complexity for any t0, one can design a randomized algorithm for any t≤n/(2+ε) using O(n{sup}3) communication complexity, thus nearly matching the known upper bound [n/2]-1. 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{sup}(1-ε)) (again for any fixed ε> 0). Our results extend to the more general function f{sub}G (x{sub}1, ..., x{sub}m):=x{sub}1·x{sub}2·... ·x{sub}m where m≥n and each of the n parties holds one or more input values.