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 2016/768

High-Throughput Semi-Honest Secure Three-Party Computation with an Honest Majority

Toshinori Araki, Jun Furukawa, Yehuda Lindell, Ariel Nof, and Kazuma Ohara


In this paper, we describe a new information-theoretic protocol (and a computationally-secure variant) for secure {\em three}-party computation with an honest majority. The protocol has very minimal computation and communication; for Boolean circuits, each party sends only a single bit for every AND gate (and nothing is sent for XOR gates). Our protocol is (simulation-based) secure in the presence of semi-honest adversaries, and achieves privacy in the client/server model in the presence of malicious adversaries. On a cluster of three 20-core servers with a 10Gbps connection, the implementation of our protocol carries out over \textit{1.3 million} AES computations per second, which involves processing over \textit{7 billion gates per second}. In addition, we developed a Kerberos extension that replaces the ticket-granting-ticket encryption on the Key Distribution Center (KDC) in MIT-Kerberos with our protocol, using keys/ passwords that are shared between the servers. This enables the use of Kerberos while protecting passwords. Our implementation is able to support a login storm of over 35,000 logins per second, which suffices even for very large organizations. Our work demonstrates that high-throughput secure computation is possible on standard hardware.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. ACM CCS 2016
secure multiparty computationhonest majorityconcrete efficiencyKerberos
Contact author(s)
lindell @ biu ac il
2016-11-10: revised
2016-08-12: received
See all versions
Short URL
Creative Commons Attribution


      author = {Toshinori Araki and Jun Furukawa and Yehuda Lindell and Ariel Nof and Kazuma Ohara},
      title = {High-Throughput Semi-Honest Secure Three-Party Computation with an Honest Majority},
      howpublished = {Cryptology ePrint Archive, Paper 2016/768},
      year = {2016},
      doi = {10.1145/2976749.2978331},
      note = {\url{https://eprint.iacr.org/2016/768}},
      url = {https://eprint.iacr.org/2016/768}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.