Study group: On Secure Multi-party Computation in Black-Box Groups

Yesterday's study group, driven by Ashish and Jake-1, was on realizing multiparty computation over groups. Traditionally, MPC has been carried out over (finite) fields with some extensions to rings. It is a natural question to ask whether there exist constructions using different algebraic structures, interesting not only from a theoretical point of view, but also because group oriented work may lead to new techniques.

When one is dealing with groups rather than with others algebraic structures equipped with two operations, the first problem that arises is how to evaluate boolean circuits. Group-based circuits have essentially one type of gate (or two, considering gates with built-in constants). Working with non-abelian groups is of particular interest due to a result (section 4) reformulated here (theorem 1) that allows to translate any boolean circuit (expressed as AND and NOT gates) into a circuit over S _5.

In the paper, they provide the means to construct passively secure protocols among n parties against unbounded adversaries, for the evaluation of the n-product function

ƒ_G(x ₁, ...,x_n) = Πx_i, where x_i is privately held by party i, and then argue that the construction can be extended to the most general case. Also, for flexibility, they assume black-box access to the group G (i.e. parties only perform either group operation, group inverse or random sampling from the group).

They first prove that MPC in non-abelian groups requires honest majority by showing that ƒ_G is not t-private if t ≥ n/2, where t is the threshold on the number of corrupted parties and n ≥ 4 . They do so using a characterization of 1-private 2-inputs protocols, for the evaluation of function ƒ, via certain type of matrices (non-forbidden matrices), and showing by contradiction that if a n/2-private protocol for ƒ_G exists, then this characterization does not hold.

Then they construct a protocol for the n-product ƒ_G out of a 2-product subprotocol. This construction is relatively easy using a binary tree with leaf nodes set to the parties' inputs, and root node to the output of ƒ_G. The computation of each intermediate node is done running the subprotocol.

Given ℓ > t the only tool needed for the construction of the protocols is a ℓ-out-of-ℓ sharing of a given secret s. The shares are defined to be the vector ss = (s₁, ...,s_ℓ) where for a fixed j ∈ [ℓ] the shares s_i for i ≠ j are randomly chosen, and s_j is such that s = Πs_i. It can be proven that the distribution of ss is independent of j.

Interestingly, t-private n-party 2-product protocols can be constructed from the combinatorial problem of finding t-reliable n-colouring graphs. As the subprotocol employed in each node of the tree takes a 2ℓ-value and outputs a ℓ-value the graph also has this structure.

The protocol must provide correctness and privacy. For the former, recall that the working group is non-abelian. They use a stronger notion of planar directed acyclic graphs, what they call admisible PDAG; esentially is planarity what ensures that the order of the factors in the multplication does not get commuted. Privacy is achieved by the t-reliable n-colouring property of the admisible PDAG. Each node of the graph is labeled with a colour in [n] that designates the party that evaluates that particular node; the property states that for any adversarial set of indices Ι ∈ [n] there exists index j_x (j_y) such that it can be found a path from j_x (j_y) input node to j_x (j_y) output node with no colours in Ι. Intuitively, there are always intermediate values that escape from the adversary's control.

On what efficiency refers, if we are willing to keep the threshold t optimal (that is t < n/2) then the sharing parameter is ℓ = c(n,t) and this leads to exponential communication complexity. Although lowering the threshold by a graph-dependent constant gives linear ℓ on n.