{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,2]],"date-time":"2026-05-02T00:47:22Z","timestamp":1777682842954,"version":"3.51.4"},"reference-count":28,"publisher":"SAGE Publications","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["JHS"],"published-print":{"date-parts":[[2021,3,29]]},"abstract":"<jats:p>Multi-party computation (MPC) sorting and searching protocols are frequently used in different databases with varied applications, as in cooperative intrusion detection systems, private computation of set intersection and oblivious RAM. Ivan Damgard et al. have proposed two techniques i.e., bit-decomposition protocol and bit-wise less than protocol for MPC. These two protocols are used as building blocks and have proposed two oblivious MPC protocols. The proposed protocols are based on data-dependent algorithms such as insertion sort and binary search. The proposed multi-party sorting protocol takes the shares of the elements as input and outputs the shares of the elements in sorted order. The proposed protocol exhibits O ( 1 ) constant round complexity and O ( n log n ) communication complexity. The proposed multi-party binary search protocol takes two inputs. One is the shares of the elements in sorted order and the other one is the shares of the element to be searched. If the position of the search element exists, the protocol returns the corresponding shares, otherwise it returns shares of zero. The proposed multi-party binary search protocol exhibits O ( 1 ) round complexity and O ( n log n ) communication complexity. The proposed multi-party sorting protocol works better than the existing quicksort protocol when the input is in almost sorted order. The proposed multi-party searching protocol gives almost the same results, when compared to the general binary search algorithm.<\/jats:p>","DOI":"10.3233\/jhs-210652","type":"journal-article","created":{"date-parts":[[2021,3,19]],"date-time":"2021-03-19T13:27:30Z","timestamp":1616160450000},"page":"67-82","source":"Crossref","is-referenced-by-count":0,"title":["Oblivious stable sorting protocol and oblivious binary search protocol for secure multi-party computation"],"prefix":"10.1177","volume":"27","author":[{"given":"Ch Koteswara","family":"Rao","sequence":"first","affiliation":[{"name":"Computer Science and Engineering Department, National Institute of Technology\u00a0\u2013 Tiruchirappalli, Tamil Nadu\u00a0\u2013 620015, India. E-mails:\u00a0kunwar@nitt.edu,\u00a0106117011@nitt.edu"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kunwar","family":"Singh","sequence":"additional","affiliation":[{"name":"Computer Science and Engineering Department, National Institute of Technology\u00a0\u2013 Tiruchirappalli, Tamil Nadu\u00a0\u2013 620015, India. E-mails:\u00a0kunwar@nitt.edu,\u00a0106117011@nitt.edu"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anoop","family":"Kumar","sequence":"additional","affiliation":[{"name":"Computer Science and Engineering Department, National Institute of Technology\u00a0\u2013 Tiruchirappalli, Tamil Nadu\u00a0\u2013 620015, India. E-mails:\u00a0kunwar@nitt.edu,\u00a0106117011@nitt.edu"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"179","reference":[{"key":"10.3233\/JHS-210652_ref1","doi-asserted-by":"crossref","unstructured":"M.\u00a0Ajtai, J.\u00a0Koml\u00f3s and E.\u00a0Szemer\u00e9di, An O(n\u2009log\u2009n) sorting network, in: Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing, 1983, pp.\u00a01\u20139, ACM.","DOI":"10.1145\/800061.808726"},{"key":"10.3233\/JHS-210652_ref2","doi-asserted-by":"crossref","unstructured":"K.E.\u00a0Batcher, Sorting networks and their applications, in: Proceedings of the April 30\u2013May 2, 1968, Spring Joint Computer Conference, 1968, pp.\u00a0307\u2013314, ACM.","DOI":"10.1145\/1468075.1468121"},{"key":"10.3233\/JHS-210652_ref3","doi-asserted-by":"crossref","unstructured":"D.\u00a0Bogdanov, S.\u00a0Laur and J.\u00a0Willemson, Sharemind: A framework for fast privacy-preserving computations, in: European Symposium on Research in Computer Security, 2008, pp.\u00a0192\u2013206, Springer.","DOI":"10.1007\/978-3-540-88313-5_13"},{"key":"10.3233\/JHS-210652_ref4","doi-asserted-by":"publisher","DOI":"10.1007\/11681878_15"},{"key":"10.3233\/JHS-210652_ref5","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-19571-6_10"},{"key":"10.3233\/JHS-210652_ref6","doi-asserted-by":"crossref","unstructured":"P.\u00a0Dikshit and K.\u00a0Singh, Efficient weighted threshold ECDSA for securing bitcoin wallet, in: 2017 ISEA Asia Security and Privacy (ISEASP), 2017, pp.\u00a01\u20139, IEEE.","DOI":"10.1109\/ISEASP.2017.7976994"},{"issue":"1","key":"10.3233\/JHS-210652_ref7","first-page":"75","article-title":"On the security of a privacy-preserving ranked multi-keyword search scheme","volume":"10","author":"Eslami","year":"2019","journal-title":"Journal of Wireless Mobile Networks, Ubiquitous Computing, and Dependable Applications (JoWUA)"},{"key":"10.3233\/JHS-210652_ref8","unstructured":"O.\u00a0Goldreich, Foundations of Cryptography: Volume 2, Basic Applications, Cambridge University Press, 2009."},{"key":"10.3233\/JHS-210652_ref9","doi-asserted-by":"crossref","unstructured":"O.\u00a0Goldreich, S.\u00a0Micali and A.\u00a0Wigderson, How to play any mental game, in: Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, 1987, pp.\u00a0218\u2013229, ACM.","DOI":"10.1145\/28395.28420"},{"key":"10.3233\/JHS-210652_ref10","doi-asserted-by":"crossref","unstructured":"S.\u00a0Goldwasser, How to play any mental game, or a completeness theorem for protocols with an honest majority, in: Proc. the Nineteenth Annual ACM STOC\u201987, 1987, pp.\u00a0218\u2013229.","DOI":"10.1145\/28395.28420"},{"key":"10.3233\/JHS-210652_ref11","doi-asserted-by":"crossref","unstructured":"S.\u00a0Goldwasser, M.\u00a0Ben-Or and A.\u00a0Wigderson, Completeness theorems for non-cryptographic fault-tolerant distributed computing, in: Proc. of the 20th STOC, 1988, pp.\u00a01\u201310.","DOI":"10.1145\/62212.62213"},{"key":"10.3233\/JHS-210652_ref12","doi-asserted-by":"crossref","unstructured":"M.T.\u00a0Goodrich, Randomized shellsort: A simple oblivious sorting algorithm, in: Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010, pp.\u00a01262\u20131277, Society for Industrial and Applied Mathematics.","DOI":"10.1137\/1.9781611973075.101"},{"key":"10.3233\/JHS-210652_ref13","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-22012-8_46"},{"key":"10.3233\/JHS-210652_ref14","doi-asserted-by":"crossref","unstructured":"K.\u00a0Hamada, R.\u00a0Kikuchi, D.\u00a0Ikarashi, K.\u00a0Chida and K.\u00a0Takahashi, Practically efficient multi-party sorting protocols from comparison sort algorithms, in: International Conference on Information Security and Cryptology, 2012, pp.\u00a0202\u2013216, Springer.","DOI":"10.1007\/978-3-642-37682-5_15"},{"issue":"1","key":"10.3233\/JHS-210652_ref15","first-page":"23","article-title":"BAdASS: Preserving privacy in behavioural advertising with applied secret sharing","volume":"10","author":"Helsloot","year":"2019","journal-title":"Journal of Wireless Mobile Networks, Ubiquitous Computing, and Dependable Applications (JoWUA)"},{"key":"10.3233\/JHS-210652_ref16","unstructured":"Y.\u00a0Huang, D.\u00a0Evans and J.\u00a0Katz, Private set intersection: Are garbled circuits better than custom protocols?, in: NDSS, 2012."},{"issue":"2","key":"10.3233\/JHS-210652_ref17","first-page":"1","article-title":"Survey on blockchain for Internet of things","volume":"9","author":"Hui","year":"2019","journal-title":"Journal of Internet Services and Information Security (JISIS)"},{"key":"10.3233\/JHS-210652_ref18","unstructured":"K.V.\u00a0J\u00f3nsson, G.\u00a0Kreitz and M.\u00a0Uddin, Secure multi-party sorting and applications., IACR Cryptology ePrint Archive 2011 (2011), 122."},{"key":"10.3233\/JHS-210652_ref19","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-24861-0_18"},{"key":"10.3233\/JHS-210652_ref20","unstructured":"C.L.\u00a0Liu, Elements of Discrete Mathematics, Tata McGraw-Hill Education, 1986."},{"key":"10.3233\/JHS-210652_ref21","unstructured":"D.\u00a0Malkhi, N.\u00a0Nisan, B.\u00a0Pinkas, Y.\u00a0Sella et al., Fairplay-secure two-party computation system, in: USENIX Security Symposium, Vol.\u00a04, 2004, p.\u00a09, San Diego, CA, USA."},{"key":"10.3233\/JHS-210652_ref22","doi-asserted-by":"crossref","unstructured":"T.\u00a0Nishide and K.\u00a0Ohta, Multiparty computation for interval, equality, and comparison without bit-decomposition protocol, in: International Workshop on Public Key Cryptography, 2007, pp.\u00a0343\u2013360, Springer.","DOI":"10.1007\/978-3-540-71677-8_23"},{"issue":"1","key":"10.3233\/JHS-210652_ref24","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1504\/IJAHUC.2020.107501","article-title":"Securely solving privacy preserving minimum spanning tree algorithms in semi-honest model","volume":"34","author":"Rao","year":"2020","journal-title":"International Journal of Ad Hoc and Ubiquitous Computing"},{"key":"10.3233\/JHS-210652_ref25","doi-asserted-by":"crossref","unstructured":"K.\u00a0Singh, C.P.\u00a0Rangan, R.\u00a0Agrawal and S.\u00a0Sheshank, Provably secure lattice based identity based unidirectional PRE and PRE+ schemes, Journal of Information Security and Applications 54 (2020), 102569.","DOI":"10.1016\/j.jisa.2020.102569"},{"issue":"2","key":"10.3233\/JHS-210652_ref26","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1080\/00207160.2014.928286","article-title":"Lattice-based identity-based resplittable threshold public key encryption scheme","volume":"93","author":"Singh","year":"2016","journal-title":"International Journal of Computer Mathematics"},{"key":"10.3233\/JHS-210652_ref28","doi-asserted-by":"publisher","DOI":"10.1145\/1755688.1755716"},{"issue":"2","key":"10.3233\/JHS-210652_ref29","first-page":"31","article-title":"Signature scheme from trapdoor functions","volume":"9","author":"Wang","year":"2019","journal-title":"Journal of Internet Services and Information Security (JISIS)"},{"key":"10.3233\/JHS-210652_ref30","unstructured":"A.C.-C.\u00a0Yao, Protocols for secure computations, in: FOCS, Vol.\u00a082, 1982, pp.\u00a0160\u2013164."}],"container-title":["Journal of High Speed Networks"],"original-title":[],"link":[{"URL":"https:\/\/content.iospress.com\/download?id=10.3233\/JHS-210652","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T08:44:17Z","timestamp":1777452257000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/full\/10.3233\/JHS-210652"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,3,29]]},"references-count":28,"journal-issue":{"issue":"1"},"URL":"https:\/\/doi.org\/10.3233\/jhs-210652","relation":{},"ISSN":["1875-8940","0926-6801"],"issn-type":[{"value":"1875-8940","type":"electronic"},{"value":"0926-6801","type":"print"}],"subject":[],"published":{"date-parts":[[2021,3,29]]}}}