Paper 2011/122

Secure Multi-Party Sorting and Applications

Kristjän Valur Jönsson, Gunnar Kreitz, and Misbah Uddin

Abstract

Sorting is among the most fundamental and well-studied problems within computer science and a core step of many algorithms. In this article, we consider the problem of constructing a secure multi-party computing (MPC) protocol for sorting. Our protocol builds on previous work in the fields of MPC and sorting networks. Apart from the immediate uses for sorting, our protocol can be used as a building-block in more complex algorithms. We present a weighted set intersection algorithm, where each party inputs a set of weighted elements and the output consists of the input elements with their weights summed. As a practical example, we apply our protocols in a network security setting for aggregation of security incident reports from multiple reporters, specifically to detect stealthy port scans in a distributed but privacy preserving manner. Both sorting and weighted set intersection use $\Ordo{n \log^2 n}$ comparisons in $\Ordo{\log^2 n}$ rounds with practical constants. Our protocols can be built upon any secret sharing scheme supporting multiplication and addition. We have implemented and evaluated the performance of sorting on the Sharemind secure multi-party computation platform, demonstrating the real-world performance of our proposed protocols.

Note: Added more references to related work.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Unknown where it was published
Keywords
Secure multi-party computationSortingAggregationCooperative anomaly detection
Contact author(s)
gkreitz @ kth se
History
2011-11-04: revised
2011-03-11: received
See all versions
Short URL
https://ia.cr/2011/122
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2011/122,
      author = {Kristjän Valur Jönsson and Gunnar Kreitz and Misbah Uddin},
      title = {Secure Multi-Party Sorting and Applications},
      howpublished = {Cryptology ePrint Archive, Paper 2011/122},
      year = {2011},
      note = {\url{https://eprint.iacr.org/2011/122}},
      url = {https://eprint.iacr.org/2011/122}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.