Anzeige
Erschienen in:
2011 | OriginalPaper | Buchkapitel
Generic Constant-Round Oblivious Sorting Algorithm for MPC
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Various information-theoretically secure Multi-Party Computation (MPC) schemes have been proposed over some finite field
$\mathbb{F}$
or some finite ring ℝ. A function
f
that can be evaluated on MPC is usually represented by boolean or arithmetic circuits. In general, the function class that have constant-depth arithmetic circuit is studied. Additionally, some literatures show that one can represent any formulas and branching program by low-degree randomizing polynomials, which can be evaluated in constant rounds. However, these approaches have their limitations, and it is not easy to construct the optimal branching program for a complex function. Therefore, it is not obvious how to efficiently perform oblivious sort in constant rounds, but oblivious sort is one of the most important primitive protocols for MPC in practice. In this paper, we are going to show several constant-round 0-error oblivious sorting algorithms, together with some useful applications.