Paper 2017/687

Impossibility of Secure Multi-Party Products in Non-Abelian Groups

Jessica Covington, Megan Golbek, and Mike Rosulek

Abstract

Suppose $n$ parties have respective inputs $x_1,\dots ,x_n\in \mathbb{G}$, where $\mathbb{G}$ is a finite group. The parties would like to privately compute $x_1{x}_2\cdots x_n$ (where multiplication refers to the group operation in $\mathbb{G}$). There is a well-known secure protocol that works for any number of parties $n$ when $\mathbb{G}$ is abelian. In this note we consider private group-product protocols for non-abelian groups. We show that such protocols are possible for if and only if $n$ (the number of parties) is less than 4.

Note: We are withdrawing this report after discovering that its results have previously appeared in the following paper: Desmedt, Pieprzyk, Steinfeld & Wang: "On Secure Multi-Party Computation in Black-Box Groups", CRYPTO 2007.