research-article

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

Authors:

Michael T. Goodrich,

Zutao ZhuAuthors Info & Claims

ASIACCS '10: Proceedings of the 5th ACM Symposium on Information, Computer and Communications Security

Pages 226 - 237

https://doi.org/10.1145/1755688.1755716

Published: 13 April 2010 Publication History

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.

References

[1]

G. Aggarwal, N. Mishra, and B. Pinkas. Secure computation of the k^th-ranked element. In In Advances in Cryptology-Proc. of Eurocrypt'04, pages 40--55, 2004.

[2]

M. Ajtai, J. Komlos, and E. Szemeredi. Sorting in c log n parallel steps. Combinatorica, 3:1--19, 1983.

Digital Library

[3]

M. J. Atallah and W. Du. Secure multi-party computational geometry. In WADS2001: 7th International Workshop on Algorithms and Data Structures, pages 165--179, Providence, Rhode Island, USA, August 8--10 2001.

Digital Library

[4]

K. E. Batcher. Sorting networks and their applications. In Proceedings of the AFIPS Spring Joint Computer Conference 32, pages 307--314, 1968.

Digital Library

[5]

M. Blum, R. W. Floyd, V. Pratt, R. Rivest, and R. Tarjan. Time bounds for selection, 1973.

[6]

R. Canetti, Y. Ishai, R. Kumar, M. K. Reiter, R. Rubinfeld, and R. N. Wright. Selective private function evaluation with applications to private statistics (extended abstract). In Proceedings of Twentieth ACM Symposium on Principles of Distributed Computing (PODC), 2001.

Digital Library

[7]

G. Chen and H. Shen. A bitonic selection algorithm on multiprocessor system. J. of Comput. Sci. Technol., 4:315--322, 1989.

[8]

B. Chor, O. Goldreich, E. Kushilevitz, and M. Sudan. Private information retrieval. In Proceedings of IEEE Symposium on Foundations of Computer Science, Milwaukee, WI USA, October 23--25 1995.

Digital Library

[9]

M. Ciura. Best increments for the average case of shellsort. In International Symposium on Fundamentals of Computation Theory, Riga, Latvia, 2001.

Digital Library

[10]

T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms, Second Edition. The MIT Press, 2001.

Digital Library

[11]

J. Feigenbaum, Y. Ishai, T. Malkin, K. Nissim, M. Strauss, and R. Wright. Secure multiparty computation of approximations. In Twenty Eighth International Colloquium on Automata, Language and Programming, 2001.

Digital Library

[12]

M. Frigo, C. E. Leiserson, H. Prokop, and S. Ramachandran. Cache-oblivious algorithms (extended abstract). In In Proc. 40th Annual Symposium on Foundations of Computer Science, pages 285--397. IEEE Computer Society Press, 1999.

Digital Library

[13]

O. Goldreich. The Foundations of Cryptography, volume 2. 2004.

Digital Library

[14]

O. Goldreich, S. Micali, and A. Wigderson. How to play any mental game. In Proceedings of the 19th Annual ACM Symposium on Theory of Computing, pages 218--229, 1987.

Digital Library

[15]

L. J. Goldstein and S. W. Leibholz. On the synthesis of signal switching networks with transient blocking, 1967.

[16]

M. T. Goodrich and R. Tamassia. Algorithm Design: Foundations, Analysis, and Internet Examples. Wiley, 2001.

[17]

Michael T. Goodrich. Randomized Shellsort: A simple oblivious sorting algorithm. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1--16. SIAM, 2010.

Digital Library

[18]

J. Incerpi. A study of the worst case of shellsort. Ph.D. thesis, Brown University, Dept. of Computer Science, 1994.

Digital Library

[19]

J. Incerpi and R. Sedgewick. Practical variations of shellsort. Information Processing Letters, 79:223--227, 2001.

Digital Library

[20]

D. E. Knuth. Seminumerical algorithms. The Art of Computer Programming, 2.

[21]

D. E. Knuth. Sorting and searching. The Art of Computer Programming, 3.

[22]

T. Leighton, Y. Ma, and T. Suel. On probabilistic networks for selection, merging, and sorting. In SPAA'95, pages 106--118, Santa Barbara, CA, USA, 1995.

Digital Library

[23]

P. Lemke. The performance of randomized shellsort-like network sorting algorithms. In SCAMP working paper, Institute for Defense Analysis, Princeton, NJ, USA, 1994.

[24]

Y. Lindell and B. Pinkas. Privacy preserving data mining. In Advances in Cryptology - Crypto2000, Lecture Notes in Computer Science, volume 1880, 2000.

Digital Library

[25]

D. Malkhi, N. Nisan, B. Pinkas, and Y. Sella. Fairplay -- a secure two-party computation system. In In USENIX Security Symposium, pages 287--302, 2004.

Digital Library

[26]

M. S. Paterson. Improved sorting networks with o(log n) depth. Algorithmica, 5:75--92, 2005.

[27]

H. Prokop. Cache-oblivious algorithms. Technical report, M.I.T, 1999.

[28]

R. Sedgewick. Analysis of shellsort and related algorithms. In ESA 96: Fourth Annual European Symposium on Algorithms, pages 25--27, 1996.

Digital Library

[29]

D. L. Shell. A high-speed sorting procedure. Commun. ACM, 2(7):30--32, 1959.

Digital Library

[30]

A. C. Yao. How to generate and exchange secrets. In Proceedings 27th IEEE Symposium on Foundations of Computer Science, pages 162--167, 1986.

Digital Library

Cited By

Attrapadung NIsayama KSadakane KTozawa KLuo BLiao XXu JKirda ELie D(2024)Secure Parallel Computation with Oblivious State TransitionsProceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security10.1145/3658644.3690315(3008-3022)Online publication date: 2-Dec-2024
https://dl.acm.org/doi/10.1145/3658644.3690315
Kim SSon YPaek JCho SLee H(2024)A Survey of Blind Sorting Techniques: Approaches Using Fully Homomorphic Encryption2024 15th International Conference on Information and Communication Technology Convergence (ICTC)10.1109/ICTC62082.2024.10827130(480-485)Online publication date: 16-Oct-2024
https://doi.org/10.1109/ICTC62082.2024.10827130
Ch KSingh KKumar A(2024)The oblivious comparison sorting protocols for secure multi-party computationMultimedia Tools and Applications10.1007/s11042-024-18139-683:26(67763-67777)Online publication date: 27-Jan-2024
https://doi.org/10.1007/s11042-024-18139-6
Show More Cited By

Index Terms

Bureaucratic protocols for secure two-party sorting, selection, and permuting
1. Social and professional topics
  1. Professional topics
    1. Management of computing and information systems

Recommendations

An Efficient Protocol for Secure Two-Party Computation in the Presence of Malicious Adversaries

We show an efficient secure two-party protocol, based on Yao's construction, which provides security against malicious adversaries. Yao's original protocol is only secure in the presence of semi-honest adversaries, and can be transformed into a protocol ...
On the Power of Secure Two-Party Computation
Proceedings, Part II, of the 36th Annual International Cryptology Conference on Advances in Cryptology --- CRYPTO 2016 - Volume 9815

Ishai, Kushilevitz, Ostrovsky and Sahai STOC 2007, SIAM JoC 2009 introduced the powerful "MPC-in-the-head" technique that provided a general transformation of information-theoretic MPC protocols secure against passive adversaries to a ZK proof in a "...
Secure Two-Party Computation via Cut-and-Choose Oblivious Transfer

Protocols for secure two-party computation enable a pair of parties to compute a function of their inputs while preserving security properties such as privacy, correctness and independence of inputs. Recently, a number of protocols have been proposed ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ASIACCS '10: Proceedings of the 5th ACM Symposium on Information, Computer and Communications Security

April 2010

363 pages

ISBN:9781605589367

DOI:10.1145/1755688

General Chair:
Dengguo Feng
Chinese Academy of Sciences, China
,
Program Chairs:
David Basin
ETH Zurich, Switzerland
,
Peng Liu
Pennsylvania State University

Copyright © 2010 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGSAC: ACM Special Interest Group on Security, Audit, and Control

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 13 April 2010

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

National Science Foundation

Conference

ASIA CCS '10

Sponsor:

SIGSAC

ASIA CCS '10: 5th ACM Symposium on Information, Computer and Communications Security

April 13 - 16, 2010

Beijing, China

Acceptance Rates

ASIACCS '10 Paper Acceptance Rate 25 of 166 submissions, 15%;

Overall Acceptance Rate 418 of 2,322 submissions, 18%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

23
Total Citations
View Citations
310
Total Downloads

Downloads (Last 12 months)24
Downloads (Last 6 weeks)2

Reflects downloads up to 19 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Attrapadung NIsayama KSadakane KTozawa KLuo BLiao XXu JKirda ELie D(2024)Secure Parallel Computation with Oblivious State TransitionsProceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security10.1145/3658644.3690315(3008-3022)Online publication date: 2-Dec-2024
https://dl.acm.org/doi/10.1145/3658644.3690315
Kim SSon YPaek JCho SLee H(2024)A Survey of Blind Sorting Techniques: Approaches Using Fully Homomorphic Encryption2024 15th International Conference on Information and Communication Technology Convergence (ICTC)10.1109/ICTC62082.2024.10827130(480-485)Online publication date: 16-Oct-2024
https://doi.org/10.1109/ICTC62082.2024.10827130
Ch KSingh KKumar A(2024)The oblivious comparison sorting protocols for secure multi-party computationMultimedia Tools and Applications10.1007/s11042-024-18139-683:26(67763-67777)Online publication date: 27-Jan-2024
https://doi.org/10.1007/s11042-024-18139-6
Thießen TVahrenhold J(2022)Klee’s Measure Problem Made ObliviousLATIN 2022: Theoretical Informatics10.1007/978-3-031-20624-5_8(121-138)Online publication date: 29-Oct-2022
https://doi.org/10.1007/978-3-031-20624-5_8
Rao CSingh KKumar A(2021)Oblivious stable sorting protocol and oblivious binary search protocol for secure multi-party computationJournal of High Speed Networks10.3233/JHS-21065227:1(67-82)Online publication date: 1-Jan-2021
https://dl.acm.org/doi/10.3233/JHS-210652
Attrapadung NHanaoaka GMatsuda TMorita HOhara KSchuldt JTeruya TTozawa KKim YKim JVigna GShi E(2021)Oblivious Linear Group Actions and ApplicationsProceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security10.1145/3460120.3484584(630-650)Online publication date: 12-Nov-2021
https://dl.acm.org/doi/10.1145/3460120.3484584
Sutradhar KOm H(2021)Efficient Cryptographic protocol for Sorting with Data-oblivious2021 2nd International Conference for Emerging Technology (INCET)10.1109/INCET51464.2021.9456338(1-6)Online publication date: 21-May-2021
https://doi.org/10.1109/INCET51464.2021.9456338
Darivandpour JLe DAtallah M(2021)Secure two-party input-size reduction: Challenges, solutions and applicationsInformation Sciences10.1016/j.ins.2021.01.038567(256-277)Online publication date: Aug-2021
https://doi.org/10.1016/j.ins.2021.01.038
Dehghan MSadeghiyan B(2020)Secure Multi-party Sorting Protocol Based on Distributed Oblivious Transfer2020 10th International Conference on Computer and Knowledge Engineering (ICCKE)10.1109/ICCKE50421.2020.9303630(011-017)Online publication date: 29-Oct-2020
https://doi.org/10.1109/ICCKE50421.2020.9303630
Chen ZChen LHuang LZhong H(2016)On Privacy-Preserving Cloud Auction2016 IEEE 35th Symposium on Reliable Distributed Systems (SRDS)10.1109/SRDS.2016.045(279-288)Online publication date: Sep-2016
https://doi.org/10.1109/SRDS.2016.045
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten