{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,2]],"date-time":"2026-07-02T16:15:57Z","timestamp":1783008957500,"version":"3.54.5"},"publisher-location":"Berlin, Heidelberg","reference-count":32,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642376818","type":"print"},{"value":"9783642376825","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-37682-5_15","type":"book-chapter","created":{"date-parts":[[2013,4,3]],"date-time":"2013-04-03T01:48:15Z","timestamp":1364953695000},"page":"202-216","source":"Crossref","is-referenced-by-count":48,"title":["Practically Efficient Multi-party Sorting Protocols from Comparison Sort Algorithms"],"prefix":"10.1007","author":[{"given":"Koki","family":"Hamada","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ryo","family":"Kikuchi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dai","family":"Ikarashi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Koji","family":"Chida","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Katsumi","family":"Takahashi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"15_CR1","doi-asserted-by":"crossref","unstructured":"Ajtai, M., Koml\u00f3s, J., Szemer\u00e9di, E.: An O(n log n) sorting network. In: STOC, pp. 1\u20139. ACM (1983)","DOI":"10.1145\/800061.808726"},{"key":"15_CR2","doi-asserted-by":"crossref","unstructured":"Batcher, K.E.: Sorting networks and their applications. In: AFIPS Spring Joint Computing Conference, pp. 307\u2013314 (1968)","DOI":"10.1145\/1468075.1468121"},{"key":"15_CR3","doi-asserted-by":"crossref","unstructured":"Ben-David, A., Nisan, N., Pinkas, B.: Fairplaymp: a system for secure multi-party computation. In: Ning, P., Syverson, P.F., Jha, S. (eds.) ACM Conference on Computer and Communications Security, pp. 257\u2013266. ACM (2008)","DOI":"10.1145\/1455770.1455804"},{"key":"15_CR4","doi-asserted-by":"crossref","unstructured":"Ben-Or, M., Goldwasser, S., Wigderson, A.: Completeness theorems for non-cryptographic fault-tolerant distributed computation (extended abstract). In: [29], pp. 1\u201310","DOI":"10.1145\/62212.62213"},{"issue":"4","key":"15_CR5","doi-asserted-by":"publisher","first-page":"448","DOI":"10.1016\/S0022-0000(73)80033-9","volume":"7","author":"M. Blum","year":"1973","unstructured":"Blum, M., Floyd, R.W., Pratt, V.R., Rivest, R.L., Tarjan, R.E.: Time bounds for selection. J. Comput. Syst. Sci.\u00a07(4), 448\u2013461 (1973)","journal-title":"J. Comput. Syst. Sci."},{"key":"15_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"192","DOI":"10.1007\/978-3-540-88313-5_13","volume-title":"Computer Security - ESORICS 2008","author":"D. Bogdanov","year":"2008","unstructured":"Bogdanov, D., Laur, S., Willemson, J.: Sharemind: A framework for fast privacy-preserving computations. In: Jajodia, S., Lopez, J. (eds.) ESORICS 2008. LNCS, vol.\u00a05283, pp. 192\u2013206. Springer, Heidelberg (2008)"},{"key":"15_CR7","unstructured":"Burkhart, M., Strasser, M., Many, D., Dimitropoulos, X.A.: Sepia: Privacy-preserving aggregation of multi-domain network events and statistics. In: USENIX Security Symposium, pp. 223\u2013240. USENIX Association (2010)"},{"key":"15_CR8","doi-asserted-by":"crossref","unstructured":"Chaum, D., Cr\u00e9peau, C., Damg\u00e5rd, I.: Multiparty unconditionally secure protocols (extended abstract). In: [29], pp. 11\u201319","DOI":"10.1145\/62212.62214"},{"key":"15_CR9","volume-title":"Introduction to Algorithms","author":"T.H. Cormen","year":"2001","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 2nd edn. MIT Press, Cambridge (2001)","edition":"2"},{"key":"15_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1007\/11681878_15","volume-title":"Theory of Cryptography","author":"I. Damg\u00e5rd","year":"2006","unstructured":"Damg\u00e5rd, I., Fitzi, M., Kiltz, E., Nielsen, J.B., Toft, T.: Unconditionally secure constant-rounds multi-party computation for equality, comparison, bits and exponentiation. In: Halevi, S., Rabin, T. (eds.) TCC 2006. LNCS, vol.\u00a03876, pp. 285\u2013304. Springer, Heidelberg (2006)"},{"key":"15_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"378","DOI":"10.1007\/11535218_23","volume-title":"Advances in Cryptology \u2013 CRYPTO 2005","author":"I. Damg\u00e5rd","year":"2005","unstructured":"Damg\u00e5rd, I., Ishai, Y.: Constant-round multiparty computation using a black-box pseudorandom generator. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol.\u00a03621, pp. 378\u2013394. Springer, Heidelberg (2005)"},{"key":"15_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1007\/978-3-642-19571-6_10","volume-title":"Theory of Cryptography","author":"I. Damg\u00e5rd","year":"2011","unstructured":"Damg\u00e5rd, I., Meldgaard, S., Nielsen, J.B.: Perfectly secure oblivious RAM without random oracles. In: Ishai, Y. (ed.) TCC 2011. LNCS, vol.\u00a06597, pp. 144\u2013163. Springer, Heidelberg (2011)"},{"key":"15_CR13","unstructured":"Geisler, M.: Cryptographic Protocols: Theory and Implementation. PhD thesis, University of Aarhus (2010)"},{"key":"15_CR14","doi-asserted-by":"crossref","unstructured":"Goldreich, O.: The Foundations of Cryptography. Basic Applications, vol.\u00a02. Cambridge University Press (2004)","DOI":"10.1017\/CBO9780511721656"},{"key":"15_CR15","doi-asserted-by":"crossref","unstructured":"Goldreich, O., Micali, S., Wigderson, A.: How to play any mental game or a completeness theorem for protocols with honest majority. In: STOC, pp. 218\u2013229. ACM (1987)","DOI":"10.1145\/28395.28420"},{"key":"15_CR16","doi-asserted-by":"crossref","unstructured":"Goodrich, M.T.: Randomized shellsort: A simple oblivious sorting algorithm. In: SODA, pp. 1262\u20131277 (2010)","DOI":"10.1137\/1.9781611973075.101"},{"key":"15_CR17","doi-asserted-by":"crossref","unstructured":"Henecka, W., K\u00f6gl, S., Sadeghi, A.R., Schneider, T., Wehrenberg, I.: Tasty: tool for automating secure two-party computations. In: Al-Shaer, E., Keromytis, A.D., Shmatikov, V. (eds.) ACM Conference on Computer and Communications Security, pp. 451\u2013462. ACM (2010)","DOI":"10.1145\/1866307.1866358"},{"issue":"7","key":"15_CR18","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1145\/366622.366644","volume":"4","author":"C.A.R. Hoare","year":"1961","unstructured":"Hoare, C.A.R.: Algorithm 65: find. Commun. ACM\u00a04(7), 321\u2013322 (1961)","journal-title":"Commun. ACM"},{"key":"15_CR19","unstructured":"Huang, Y., Evans, D., Katz, J.: Private set intersection: Are garbled circuits better than custom protocols? In: NDSS (2012)"},{"key":"15_CR20","unstructured":"J\u00f3nsson, K.V., Kreitz, G., Uddin, M.: Secure multi-party sorting and applications. IACR Cryptology ePrint Archive 2011, 122 (2011)"},{"key":"15_CR21","unstructured":"Knuth, D.E.: Art of Computer Programming, 2nd edn. Sorting and Searching, vol.\u00a03, ch. 5. Addison-Wesley Professional (1998)"},{"key":"15_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"262","DOI":"10.1007\/978-3-642-24861-0_18","volume-title":"Information Security","author":"S. Laur","year":"2011","unstructured":"Laur, S., Willemson, J., Zhang, B.: Round-efficient oblivious database manipulation. In: Lai, X., Zhou, J., Li, H. (eds.) ISC 2011. LNCS, vol.\u00a07001, pp. 262\u2013277. Springer, Heidelberg (2011)"},{"key":"15_CR23","unstructured":"Malkhi, D., Nisan, N., Pinkas, B., Sella, Y.: Fairplay - secure two-party computation system. In: USENIX Security Symposium, pp. 287\u2013302 (2004)"},{"key":"15_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"483","DOI":"10.1007\/978-3-642-17373-8_28","volume-title":"Advances in Cryptology - ASIACRYPT 2010","author":"C. Ning","year":"2010","unstructured":"Ning, C., Xu, Q.: Multiparty computation for modulo reduction without bit-decomposition and a generalization to bit-decomposition. In: Abe, M. (ed.) ASIACRYPT 2010. LNCS, vol.\u00a06477, pp. 483\u2013500. Springer, Heidelberg (2010)"},{"key":"15_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1007\/978-3-540-71677-8_23","volume-title":"Public Key Cryptography \u2013 PKC 2007","author":"T. Nishide","year":"2007","unstructured":"Nishide, T., Ohta, K.: Multiparty computation for interval, equality, and comparison without bit-decomposition protocol. In: Okamoto, T., Wang, X. (eds.) PKC 2007. LNCS, vol.\u00a04450, pp. 343\u2013360. Springer, Heidelberg (2007)"},{"key":"15_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"364","DOI":"10.1007\/11935230_24","volume-title":"Advances in Cryptology \u2013 ASIACRYPT 2006","author":"S. Obana","year":"2006","unstructured":"Obana, S., Araki, T.: Almost optimum secret sharing schemes secure against cheating for arbitrary secret distribution. In: Lai, X., Chen, K. (eds.) ASIACRYPT 2006. LNCS, vol.\u00a04284, pp. 364\u2013379. Springer, Heidelberg (2006)"},{"key":"15_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"200","DOI":"10.1007\/3-540-68339-9_18","volume-title":"Advances in Cryptology - EUROCRYPT \u201996","author":"W. Ogata","year":"1996","unstructured":"Ogata, W., Kurosawa, K.: Optimum secret sharing scheme secure against cheating. In: Maurer, U.M. (ed.) EUROCRYPT 1996. LNCS, vol.\u00a01070, pp. 200\u2013211. Springer, Heidelberg (1996)"},{"issue":"11","key":"15_CR28","doi-asserted-by":"publisher","first-page":"612","DOI":"10.1145\/359168.359176","volume":"22","author":"A. Shamir","year":"1979","unstructured":"Shamir, A.: How to share a secret. Commun. ACM\u00a022(11), 612\u2013613 (1979)","journal-title":"Commun. ACM"},{"key":"15_CR29","unstructured":"Simon, J. (ed.): Proceedings of the 20th Annual ACM Symposium on Theory of Computing, STOC, Chicago, Illinois, USA, May 2-4. ACM (1988)"},{"key":"15_CR30","doi-asserted-by":"crossref","unstructured":"Skiena, S.S.: The Algorithm Design Manual, 2nd edn. Springer Publishing Company, Incorporated (2008)","DOI":"10.1007\/978-1-84800-070-4"},{"key":"15_CR31","doi-asserted-by":"crossref","unstructured":"Wang, G., Luo, T., Goodrich, M.T., Du, W., Zhu, Z.: Bureaucratic protocols for secure two-party sorting, selection, and permuting. In: ASIACCS, pp. 226\u2013237 (2010)","DOI":"10.1145\/1755688.1755716"},{"key":"15_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"240","DOI":"10.1007\/978-3-642-24316-5_17","volume-title":"Provable Security","author":"B. Zhang","year":"2011","unstructured":"Zhang, B.: Generic constant-round oblivious sorting algorithm for MPC. In: Boyen, X., Chen, X. (eds.) ProvSec 2011. LNCS, vol.\u00a06980, pp. 240\u2013256. Springer, Heidelberg (2011)"}],"container-title":["Lecture Notes in Computer Science","Information Security and Cryptology \u2013 ICISC 2012"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-37682-5_15","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,30]],"date-time":"2025-04-30T02:57:44Z","timestamp":1745981864000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-37682-5_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642376818","9783642376825"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-37682-5_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013]]}}}