Paper 2022/574

Comparison-Based MPC in Star Topology (Full Version)

Gowri R Chandran, Carmit Hazay, Robin Hundt, and Thomas Schneider


With the large amount of data generated nowadays, analysis of this data has become eminent. Since a vast amount of this data is private, it is also important that the analysis is done in a secure manner. Comparison-based functions are commonly used in data analysis. These functions use the comparison operation as the basis. Secure computation of such functions have been discussed for median by Aggarwal et al. (EUROCRYPT'04) and for convex hull by Shelat and Venkitasubramaniam (ASIACRYPT'15). In this paper, we present a generic protocol for the secure computation of comparison-based functions. In order to scale to a large number of participants, we propose this protocol in a star topology with an aim to reduce the communication complexity. We also present a protocol for one specific comparison-based function, the $k^{th}$ ranked element. The construction of one of our protocols leaks some intermediate values but does not reveal information about an individual party's inputs. We demonstrate that our protocol offers better performance than the protocol for $k^{th}$ ranked element by Tueno et. al. (FC'20) by providing an implementation.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Minor revision. International Conference on Security and Cryptography (SECRYPT’22)
Secure multi-party computationkth ranked elementOptimisation problemsScheduling problems
Contact author(s)
chandran @ encrypto cs tu-darmstadt de
2022-05-16: received
Short URL
Creative Commons Attribution


      author = {Gowri R Chandran and Carmit Hazay and Robin Hundt and Thomas Schneider},
      title = {Comparison-Based MPC in Star Topology (Full Version)},
      howpublished = {Cryptology ePrint Archive, Paper 2022/574},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.