Bureaucratic Protocols for Secure Two-Party Sorting,Selection, and Permuting

摘要

In this paper, we introduce a framework for secure two-party (S2P) computations, which we call bureaucratic comput ing, and we demonstrate its efficiency by designing prac tical S2P computations for sorting, selection, and random permutation. In a nutshell, the main idea behind bureau cratic computing is to design data-oblivious algorithms that push all knowledge and influence of input values down to small black-box circuits, which are simulated using Yao's garbled paradigm. The practical benefit of this approach is that it maintains the zero-knowledge features of secure two-party computations while avoiding the significant com putational overheads that come from trying to apply Yao's garbled paradigm to anything other than simple twoinput functions.