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

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

doi:10.1145/1755688.1755716

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

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

Department of Electrical Engineering & Computer Science

Research output: Chapter in Book/Entry/Poem › Conference contribution

26 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 language	English (US)
Title of host publication	Proceedings of the 5th International Symposium on Information, Computer and Communications Security, ASIACCS 2010
Pages	226-237
Number of pages	12
DOIs	https://doi.org/10.1145/1755688.1755716
State	Published - 2010
Event	5th ACM Symposium on Information, Computer and Communication Security, ASIACCS 2010 - Beijing, China Duration: Apr 13 2010 → Apr 16 2010

Publication series

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

Other

Other	5th ACM Symposium on Information, Computer and Communication Security, ASIACCS 2010
Country/Territory	China
City	Beijing
Period	4/13/10 → 4/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

Access to Document

10.1145/1755688.1755716

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

Bureaucratic protocols for secure two-party sorting, selection, and permuting. / Wang, Guan; Luo, Tongbo; Goodrich, Michael T. et al.
Proceedings of the 5th International Symposium on Information, Computer and Communications Security, ASIACCS 2010. 2010. p. 226-237 (Proceedings of the 5th International Symposium on Information, Computer and Communications Security, ASIACCS 2010).

Research output: Chapter in Book/Entry/Poem › Conference contribution

Wang, G, Luo, T, Goodrich, MT, 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. Proceedings of the 5th International Symposium on Information, Computer and Communications Security, ASIACCS 2010, pp. 226-237, 5th ACM Symposium on Information, Computer and Communication Security, ASIACCS 2010, Beijing, China, 4/13/10. https://doi.org/10.1145/1755688.1755716

Wang G, Luo T, Goodrich MT, Du W, Zhu Z. 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. 2010. p. 226-237. (Proceedings of the 5th International Symposium on Information, Computer and Communications Security, ASIACCS 2010). doi: 10.1145/1755688.1755716

Wang, Guan ; Luo, Tongbo ; Goodrich, Michael T. et al. / Bureaucratic protocols for secure two-party sorting, selection, and permuting. Proceedings of the 5th International Symposium on Information, Computer and Communications Security, ASIACCS 2010. 2010. pp. 226-237 (Proceedings of the 5th International Symposium on Information, Computer and Communications Security, ASIACCS 2010).

@inproceedings{b77200bb01594aa8bbd5855f6ad69d40,

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

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.",

keywords = "bureaucratic protocols, oblivious algorithms, secure two-party computation, sorting",

author = "Guan Wang and Tongbo Luo and Goodrich, {Michael T.} and Wenliang Du and Zutao Zhu",

note = "Copyright: Copyright 2010 Elsevier B.V., All rights reserved.; 5th ACM Symposium on Information, Computer and Communication Security, ASIACCS 2010 ; Conference date: 13-04-2010 Through 16-04-2010",

year = "2010",

doi = "10.1145/1755688.1755716",

language = "English (US)",

isbn = "9781605589367",

series = "Proceedings of the 5th International Symposium on Information, Computer and Communications Security, ASIACCS 2010",

pages = "226--237",

booktitle = "Proceedings of the 5th International Symposium on Information, Computer and Communications Security, ASIACCS 2010",

}

TY - GEN

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

AU - Wang, Guan

AU - Luo, Tongbo

AU - Goodrich, Michael T.

AU - Du, Wenliang

AU - Zhu, Zutao

PY - 2010

Y1 - 2010

N2 - 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.

AB - 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.

KW - bureaucratic protocols

KW - oblivious algorithms

KW - secure two-party computation

KW - sorting

UR - http://www.scopus.com/inward/record.url?scp=77954519783&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77954519783&partnerID=8YFLogxK

U2 - 10.1145/1755688.1755716

DO - 10.1145/1755688.1755716

M3 - Conference contribution

AN - SCOPUS:77954519783

SN - 9781605589367

T3 - Proceedings of the 5th International Symposium on Information, Computer and Communications Security, ASIACCS 2010

SP - 226

EP - 237

BT - Proceedings of the 5th International Symposium on Information, Computer and Communications Security, ASIACCS 2010

T2 - 5th ACM Symposium on Information, Computer and Communication Security, ASIACCS 2010

Y2 - 13 April 2010 through 16 April 2010

ER -

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

Abstract

Publication series

Other

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this