eprint.iacr.org will be offline for approximately an hour for routine maintenance at 11pm UTC on Tuesday, April 16. We lost some data between April 12 and April 14, and some authors have been notified that they need to resubmit their papers.

Paper 2022/1595

Efficient Secure Three-Party Sorting with Applications to Data Analysis and Heavy Hitters

Gilad Asharov, Bar-Ilan University
Koki Hamada, NTT Corporation
Dai Ikarashi, NTT Corporation
Ryo Kikuchi, NTT Corporation
Ariel Nof, Bar-Ilan University
Benny Pinkas, Bar-Ilan University
Katsumi Takahashi, NTT Corporation
Junichi Tomida, NTT Corporation
Abstract

We present a three-party sorting protocol secure against passive and active adversaries in the honest majority setting. The protocol can be easily combined with other secure protocols which work on shared data, and thus enable different data analysis tasks, such as private set intersection of shared data, deduplication, and the identification of heavy hitters. The new protocol computes a stable sort. It is based on radix sort and is asymptotically better than previous secure sorting protocols. It improves on previous radix sort protocols by not having to shuffle the entire length of the items after each comparison step. We implemented our sorting protocol with different optimizations and achieved concretely fast performance. For example, sorting one million items with 32-bit keys and 32-bit values takes less than 2 seconds with semi-honest security and about 3.5 seconds with malicious security. Finding the heavy hitters among hundreds of thousands of 256-bit values takes only a few seconds, compared to close to an hour in previous work.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. ACM CCS 2022
DOI
10.1145/3548606.3560691
Keywords
MPC; Sorting
Contact author(s)
Gilad Asharov @ biu ac il
koki hamada rb @ hco ntt co jp
dai ikarashi rd @ hco ntt co jp
9h358j30qe @ gmail com
ariel nof @ biu ac il
benny @ pinkas net
katsumi takahashi aw @ hco ntt co jp
tomida junichi @ gmail com
History
2022-11-17: approved
2022-11-16: received
See all versions
Short URL
https://ia.cr/2022/1595
License
No rights reserved
CC0

BibTeX

@misc{cryptoeprint:2022/1595,
      author = {Gilad Asharov and Koki Hamada and Dai Ikarashi and Ryo Kikuchi and Ariel Nof and Benny Pinkas and Katsumi Takahashi and Junichi Tomida},
      title = {Efficient Secure Three-Party Sorting with Applications to Data Analysis and Heavy Hitters},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1595},
      year = {2022},
      doi = {10.1145/3548606.3560691},
      note = {\url{https://eprint.iacr.org/2022/1595}},
      url = {https://eprint.iacr.org/2022/1595}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.