Secure Computation of the k th -Ranked Element

作者: Gagan Aggarwal , Nina Mishra , Benny Pinkas

DOI: 10.1007/978-3-540-24676-3_3

关键词:

摘要: Given two or more parties possessing large, confidential datasets, we consider the problem of securely computing k th -ranked element union e.g. median values in datasets. We investigate protocols with sublinear computation and communication costs. In two-party case, show that can be computed log rounds, where costs each round are O(log M), M is number bits needed to describe input data. The protocol made secure against a malicious adversary, hide sizes original multi-party setting, O(s M) overhead per round, s parties. used case also adversary.

参考文章(20)
R. Canetti, Universally composable security: a new paradigm for cryptographic protocols international conference on cluster computing. pp. 136- 145 ,(2001) , 10.1109/SFCS.2001.959888
Yannis E. Ioannidis, Viswanath Poosala, Venkatesh Ganti, Approximate Query Answering using Histograms. IEEE Data(base) Engineering Bulletin. ,vol. 22, pp. 5- 14 ,(1999)
Marc Fischlin, A Cost-Effective Pay-Per-Multiplication Comparison Method for Millionaires the cryptographers track at the rsa conference. pp. 457- 472 ,(2001) , 10.1007/3-540-45353-9_33
Joan Feigenbaum, Yuval Ishai, Tal Malkin, Kobbi Nissim, Martin J. Strauss, Rebecca N. Wright, Secure Multiparty Computation of Approximations international colloquium on automata languages and programming. pp. 927- 938 ,(2001) , 10.1007/3-540-48224-5_75
Matthew Hennessy, Robin Milner, On Observing Nondeterminism and Concurrency international colloquium on automata, languages and programming. pp. 299- 309 ,(1980) , 10.1007/3-540-10003-2_79
Nick Koudas, H. V. Jagadish, Torsten Suel, Kenneth C. Sevcik, Viswanath Poosala, S. Muthukrishnan, Optimal Histograms with Quality Guarantees very large data bases. pp. 275- 286 ,(1998)
Ran Canetti, Security and Composition of Multiparty Cryptographic Protocols Journal of Cryptology. ,vol. 13, pp. 143- 202 ,(2000) , 10.1007/S001459910006
O. Goldreich, S. Micali, A. Wigderson, How to play ANY mental game symposium on the theory of computing. pp. 218- 229 ,(1987) , 10.1145/28395.28420
Michael Rodeh, Finding the median distributively Journal of Computer and System Sciences. ,vol. 24, pp. 162- 166 ,(1982) , 10.1016/0022-0000(82)90045-9
D. Beaver, S. Micali, P. Rogaway, The round complexity of secure protocols symposium on the theory of computing. pp. 503- 513 ,(1990) , 10.1145/100216.100287