Paper 2023/1098

$\textsf{Asterisk}$: Super-fast MPC with a Friend

Banashri Karmakar, Indian Institute of Science Bangalore
Nishat Koti, Indian Institute of Science Bangalore
Arpita Patra, Indian Institute of Science Bangalore
Sikhar Patranabis, IBM IRL
Protik Paul, Indian Institute of Science Bangalore
Divya Ravi, Aarhus University
Abstract

Secure multiparty computation$~$(MPC) enables privacy-preserving collaborative computation over sensitive data held by multiple mutually distrusting parties. Unfortunately, in the most natural setting where a majority of the parties are maliciously corrupt$~$(also called the $\textit{dishonest majority}$ setting), traditional MPC protocols incur high overheads and offer weaker security guarantees than are desirable for practical applications. In this paper, we explore the possibility of circumventing these drawbacks and achieving practically efficient dishonest majority MPC protocols with strong security guarantees by assuming an additional semi-honest, non-colluding helper party $\mathrm{HP}$. We believe that this is a more realistic alternative to assuming an honest majority, since many real-world applications of MPC involving potentially large numbers of parties$~$(such as dark pools) are typically enabled by a central governing entity that can be modeled as the $\mathrm{HP}$. In the above model, we are the first to design, implement and benchmark a practically-efficient and general multi-party framework, $\textsf{Asterisk}$. Our framework requires invoking $\mathrm{HP}$ only a constant number of times, achieves the strong security guarantee of $\textit{fairness}$ (either all parties learn the output or none do), scales to hundreds of parties, outperforms all existing dishonest majority MPC protocols, and is, in fact, competitive with state-of-the-art honest majority MPC protocols. Our experiments show that $\textsf{Asterisk}$ achieves $228-288\times$ speedup in preprocessing as compared to the best dishonest majority MPC protocol. With respect to online time, $\textsf{Asterisk}$ supports $100$-party evaluation of a circuit with $10^6$ multiplication gates in approximately $20$ seconds. We also implement and benchmark practically efficient and highly scalable dark pool instances using $\textsf{Asterisk}$. The corresponding run times showcase the effectiveness of $\textsf{Asterisk}$ in enabling efficient realizations of real-world privacy-preserving applications with strong security guarantees.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Major revision. IEEE S&P 2024
Keywords
Multiparty ComputationDishonest MajorityFairnessDark pool
Contact author(s)
banashrik @ iisc ac in
kotis @ iisc ac in
arpita @ iisc ac in
sikhar patranabis @ ibm com
protikpaul @ iisc ac in
divya @ cs au dk
History
2024-07-01: last of 3 revisions
2023-07-14: received
See all versions
Short URL
https://ia.cr/2023/1098
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/1098,
      author = {Banashri Karmakar and Nishat Koti and Arpita Patra and Sikhar Patranabis and Protik Paul and Divya Ravi},
      title = {$\textsf{Asterisk}$: Super-fast {MPC} with a Friend},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/1098},
      year = {2023},
      url = {https://eprint.iacr.org/2023/1098}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.