Secure Parallel Computation on Privately Partitioned Data and Applications

Parallel computation is an important aspect of multi-party computation, not only in terms of improving efficiency, but also in terms of providing privacy for computation involving conditional branching based on private data. While applying multi-party computation in parallel over several sets of input data is straightforward if the partitioning of the input data into sets is publicly known, the problem becomes much more challenging when this partitioning is private. This setting is relevant to broad class of secure computations, in particular to secure graph and database analysis in which the underlying data (graph or database) is private. In this paper, we consider a general class of functions which can be expressed via the iterative evaluation of a binary associative operation, and propose efficient protocols for evaluating such functions in parallel over privately partitioned input data. Our protocols are optimal in terms of the required number of evaluations of the underlying binary operation (i.e. 𝑁 -1 evaluations for total input size 𝑁 ), while simultaneously achieving a round complexity which is only logarithmic in the total size of the input data (i.e. 𝑂 (log 𝑁 )).

Applying our protocols to specific functions result in concrete improvements compared to dedicated protocols from previous works. For example, we improve upon the previously best known protocols for simple functionalities such as (grouped) summation and (grouped) max, as well as the secure graph analysis protocols by Nayak et al. (S&P'15), which all requires 𝑂 (𝑁 log 𝑁 ) evaluations of their respective underlying operations to achieve a 𝑂 (log 𝑁 ) round complexity. While our protocols achieve the same asymptotic performance as the shortest path algorithms by Anagreh et al. (Cryptography'21), we achieve better concrete performance. Lastly, considering shortest path computations on a weighted graph via the Bellman-Ford algorithm, we reduce the communication complexity by 2.4 ∼ 5.4 compared to the recent results by Araki et al. (CCS'21) on large-scale graphs of thousand nodes and edges. Besides this, we achieve efficient protocols for functions not considered previously, such as ArgMax, first/last projections, and list concatenation.