Guan Wang
Michael T. Goodrich
Wenliang Du
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.
- G. Aggarwal, N. Mishra, and B. Pinkas. Secure computation of the kth-ranked element. In In Advances in Cryptology-Proc. of Eurocrypt'04, pages 40--55, 2004.Google Scholar
- M. Ajtai, J. Komlos, and E. Szemeredi. Sorting in c log n parallel steps. Combinatorica, 3:1--19, 1983. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- K. E. Batcher. Sorting networks and their applications. In Proceedings of the AFIPS Spring Joint Computer Conference 32, pages 307--314, 1968. Google ScholarDigital Library
- M. Blum, R. W. Floyd, V. Pratt, R. Rivest, and R. Tarjan. Time bounds for selection, 1973.Google Scholar
- 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. Google ScholarDigital Library
- G. Chen and H. Shen. A bitonic selection algorithm on multiprocessor system. J. of Comput. Sci. Technol., 4:315--322, 1989.Google ScholarCross Ref
- 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. Google ScholarDigital Library
- M. Ciura. Best increments for the average case of shellsort. In International Symposium on Fundamentals of Computation Theory, Riga, Latvia, 2001. Google ScholarDigital Library
- T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms, Second Edition. The MIT Press, 2001. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- O. Goldreich. The Foundations of Cryptography, volume 2. 2004. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- L. J. Goldstein and S. W. Leibholz. On the synthesis of signal switching networks with transient blocking, 1967.Google Scholar
- M. T. Goodrich and R. Tamassia. Algorithm Design: Foundations, Analysis, and Internet Examples. Wiley, 2001.Google Scholar
- 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. Google ScholarDigital Library
- J. Incerpi. A study of the worst case of shellsort. Ph.D. thesis, Brown University, Dept. of Computer Science, 1994. Google ScholarDigital Library
- J. Incerpi and R. Sedgewick. Practical variations of shellsort. Information Processing Letters, 79:223--227, 2001. Google ScholarDigital Library
- D. E. Knuth. Seminumerical algorithms. The Art of Computer Programming, 2.Google Scholar
- D. E. Knuth. Sorting and searching. The Art of Computer Programming, 3.Google Scholar
- 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. Google ScholarDigital Library
- P. Lemke. The performance of randomized shellsort-like network sorting algorithms. In SCAMP working paper, Institute for Defense Analysis, Princeton, NJ, USA, 1994.Google Scholar
- Y. Lindell and B. Pinkas. Privacy preserving data mining. In Advances in Cryptology - Crypto2000, Lecture Notes in Computer Science, volume 1880, 2000. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- M. S. Paterson. Improved sorting networks with o(log n) depth. Algorithmica, 5:75--92, 2005.Google ScholarCross Ref
- H. Prokop. Cache-oblivious algorithms. Technical report, M.I.T, 1999.Google Scholar
- R. Sedgewick. Analysis of shellsort and related algorithms. In ESA 96: Fourth Annual European Symposium on Algorithms, pages 25--27, 1996. Google ScholarDigital Library
- D. L. Shell. A high-speed sorting procedure. Commun. ACM, 2(7):30--32, 1959. Google ScholarDigital Library
- A. C. Yao. How to generate and exchange secrets. In Proceedings 27th IEEE Symposium on Foundations of Computer Science, pages 162--167, 1986. Google ScholarDigital Library
Index Terms
- Bureaucratic protocols for secure two-party sorting, selection, and permuting
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 9815Ishai, 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