Bureaucratic protocols for secure two-party sorting, selection, and permuting

Guan Wang, Tongbo Luo, Michael T. Goodrich, Wenliang Du, Zutao Zhu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

19 Scopus citations

Abstract

In this paper, we introduce a framework for secure two-party (S2P) computations, which we call bureaucratic computing, and we demonstrate its efficiency by designing practical S2P computations for sorting, selection, and random permutation. In a nutshell, the main idea behind bureaucratic 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 computational overheads that come from trying to apply Yao's garbled paradigm to anything other than simple two-input functions.

Original languageEnglish (US)
Title of host publicationProceedings of the 5th International Symposium on Information, Computer and Communications Security, ASIACCS 2010
Pages226-237
Number of pages12
DOIs
StatePublished - Jul 16 2010
Event5th ACM Symposium on Information, Computer and Communication Security, ASIACCS 2010 - Beijing, China
Duration: Apr 13 2010Apr 16 2010

Publication series

NameProceedings of the 5th International Symposium on Information, Computer and Communications Security, ASIACCS 2010

Other

Other5th ACM Symposium on Information, Computer and Communication Security, ASIACCS 2010
CountryChina
CityBeijing
Period4/13/104/16/10

Keywords

  • bureaucratic protocols
  • oblivious algorithms
  • secure two-party computation
  • sorting

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Hardware and Architecture
  • Information Systems
  • Software

Fingerprint Dive into the research topics of 'Bureaucratic protocols for secure two-party sorting, selection, and permuting'. Together they form a unique fingerprint.

  • Cite this

    Wang, G., Luo, T., Goodrich, M. T., Du, W., & Zhu, Z. (2010). Bureaucratic protocols for secure two-party sorting, selection, and permuting. In Proceedings of the 5th International Symposium on Information, Computer and Communications Security, ASIACCS 2010 (pp. 226-237). (Proceedings of the 5th International Symposium on Information, Computer and Communications Security, ASIACCS 2010). https://doi.org/10.1145/1755688.1755716