Sage Journals: Discover world-class research

Abstract

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.

Keywords

Multi-party computation oblivious sorting bit-wise sharing bit-decomposition protocol bit-wise less than protocol searching

Get full access to this article

View all access options for this article.

References

Ajtai,

Komlós and

Szemerédi, An O(n log n) sorting network, in: Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing, 1983, pp. 1–9, ACM.

K.E.

Batcher, Sorting networks and their applications, in: Proceedings of the April 30–May 2, 1968, Spring Joint Computer Conference, 1968, pp. 307–314, ACM.

Bogdanov,

Laur and

Willemson, Sharemind: A framework for fast privacy-preserving computations, in: European Symposium on Research in Computer Security, 2008, pp. 192–206, Springer.

Damgård,

Fitzi,

Kiltz,

J.B.

Nielsen and

Toft, Unconditionally secure constant-rounds multi-party computation for equality, comparison, bits and exponentiation, in: Theory of Cryptography Conference, 2006, pp. 285–304, Springer. doi:10.1007/11681878_15.

Damgård,

Meldgaard and

J.B.

Nielsen, Perfectly secure oblivious RAM without random oracles, in: Theory of Cryptography Conference, 2011, pp. 144–163, Springer. doi:10.1007/978-3-642-19571-6_10.

Dikshit and

Singh, Efficient weighted threshold ECDSA for securing bitcoin wallet, in: 2017 ISEA Asia Security and Privacy (ISEASP), 2017, pp. 1–9, IEEE.

Eslami,

Noroozi and

Baek, On the security of a privacy-preserving ranked multi-keyword search scheme, Journal of Wireless Mobile Networks, Ubiquitous Computing, and Dependable Applications (JoWUA) 10(1) (2019), 75–85.

Goldreich, Foundations of Cryptography: Volume 2, Basic Applications, Cambridge University Press, 2009.

Goldreich,

Micali and

Wigderson, How to play any mental game, in: Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, 1987, pp. 218–229, ACM.

10.

Goldwasser, How to play any mental game, or a completeness theorem for protocols with an honest majority, in: Proc. the Nineteenth Annual ACM STOC’87, 1987, pp. 218–229.

11.

Goldwasser,

Ben-Or and

Wigderson, Completeness theorems for non-cryptographic fault-tolerant distributed computing, in: Proc. of the 20th STOC, 1988, pp. 1–10.

12.

M.T.

Goodrich, Randomized shellsort: A simple oblivious sorting algorithm, in: Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010, pp. 1262–1277, Society for Industrial and Applied Mathematics.

13.

M.T.

Goodrich and

Mitzenmacher, Privacy-preserving access of outsourced data via oblivious RAM simulation, in: International Colloquium on Automata, Languages, and Programming, 2011, pp. 576–587, Springer. doi:10.1007/978-3-642-22012-8_46.

14.

Hamada,

Kikuchi,

Ikarashi,

Chida and

Takahashi, Practically efficient multi-party sorting protocols from comparison sort algorithms, in: International Conference on Information Security and Cryptology, 2012, pp. 202–216, Springer.

15.

L.J.

Helsloot,

Tillem and

Erkin, BAdASS: Preserving privacy in behavioural advertising with applied secret sharing, Journal of Wireless Mobile Networks, Ubiquitous Computing, and Dependable Applications (JoWUA) 10(1) (2019), 23–41.

16.

Huang,

Evans and

Katz, Private set intersection: Are garbled circuits better than custom protocols?, in: NDSS, 2012.

17.

Hui,

An,

Wang,

Ju,

Yang,

Gao and

Lin, Survey on blockchain for Internet of things, Journal of Internet Services and Information Security (JISIS) 9(2) (2019), 1–30.

18.

K.V.

Jónsson,

Kreitz and

Uddin, Secure multi-party sorting and applications., IACR Cryptology ePrint Archive 2011 (2011), 122.

19.

Laur,

Willemson and

Zhang, Round-efficient oblivious database manipulation, in: International Conference on Information Security, 2011, pp. 262–277, Springer. doi:10.1007/978-3-642-24861-0_18.

20.

C.L.

Liu, Elements of Discrete Mathematics, Tata McGraw-Hill Education, 1986.

21.

Malkhi,

Nisan,

Pinkas,

Sella et al., Fairplay-secure two-party computation system, in: USENIX Security Symposium, Vol. 4, 2004, p. 9, San Diego, CA, USA.

22.

Nishide and

Ohta, Multiparty computation for interval, equality, and comparison without bit-decomposition protocol, in: International Workshop on Public Key Cryptography, 2007, pp. 343–360, Springer.

23.

Patra, Cryptography, https://www.csa.iisc.ac.in/~arpita/Cryptography15.html, 2015.

24.

C.K.

Rao and

Singh, Securely solving privacy preserving minimum spanning tree algorithms in semi-honest model, International Journal of Ad Hoc and Ubiquitous Computing 34(1) (2020), 1–10. doi:10.1504/IJAHUC.2020.107501.

25.

Singh,

C.P.

Rangan,

Agrawal and

Sheshank, Provably secure lattice based identity based unidirectional PRE and PRE+ schemes, Journal of Information Security and Applications 54 (2020), 102569.

26.

Singh,

C.P.

Rangan and

A.K.

Banerjee, Lattice-based identity-based resplittable threshold public key encryption scheme, International Journal of Computer Mathematics 93(2) (2016), 289–307. doi:10.1080/00207160.2014.928286.

27.

Tal Rabin Technion Secure Multiparty Computation, https://www.youtube.com/watch?v=NOtsxHoIcWQ, 2014.

28.

Wang,

Luo,

M.T.

Goodrich,

Du and

Zhu, Bureaucratic protocols for secure two-party sorting, selection, and permuting, in: Proceedings of the 5th ACM Symposium on Information, Computer and Communications Security, 2010, pp. 226–237, ACM. doi:10.1145/1755688.1755716.

29.

Wang,

Xiao,

Miao,

Liu and

Huang, Signature scheme from trapdoor functions, Journal of Internet Services and Information Security (JISIS) 9(2) (2019), 31–41.

30.

A.C.-C.

Yao, Protocols for secure computations, in: FOCS, Vol. 82, 1982, pp. 160–164.

Oblivious stable sorting protocol and oblivious binary search protocol for secure multi-party computation

Abstract

Keywords

Get full access to this article

References