Koji Chida
ABSTRACT
This work describes a three-times ($3\times$) improvement to the performance of secure computation of AES over a network of three parties with an honest majority. The throughput that is achieved is even better than that of computing AES in some scenarios of local (non-private) computation. The performance improvement is achieved through an optimization of the generic secure protocol, and, more importantly, through an optimization of the description of the AES function to support more efficient secure computation, and an optimization of the protocol to the underlying architecture. This demonstrates that the development process of efficient secure computation must include adapting the description of the computed function to be tailored to the protocol, and adapting the implementation of the protocol to the architecture. This work focuses on the secure computation of AES since it has been widely investigated as a de-facto standard performance benchmark for secure computation, and is also important by itself for many applications. Furthermore, parts of the improvements are general and not specific to AES, and can be applied to secure computation of arbitrary functions.
- Kazumaro Aoki and Helger Lipmaa. 2000. Fast Implementations of AES Candidates. In Third AES Candidate Conference .Google Scholar
- Toshinori Araki, Assi Barak, Jun Furukawa, Yehuda Lindell, Ariel Nof, Kazuma Ohara, Adi Watzman, and Or Weinstein. 2017. Optimized Honest-Majority MPC for Malicious Adversaries - Breaking the 1 Billion-Gate Per Second Barrier. In IEEE Symposium on Security and Privacy, SP 2017 .Google ScholarCross Ref
- Toshinori Araki, Jun Furukawa, Yehuda Lindell, Ariel Nof, and Kazuma Ohara. 2016. High-Throughput Semi-Honest Secure Three-Party Computation with an Honest Majority. In ACM CCS. 805--817. Google ScholarDigital Library
- Donald Beaver, Silvio Micali, and Phillip Rogaway. 1990. The Round Complexity of Secure Protocols (Extended Abstract). In Proceedings of the 22nd Annual ACM Symposium on Theory of Computing,. 503--513. Google ScholarDigital Library
- Aner Ben-Efraim, Yehuda Lindell, and Eran Omri. 2016. Optimizing Semi-Honest Secure Multiparty Computation for the Internet. In ACM CCS. 578--590. Google ScholarDigital Library
- Michael Ben-Or, Shafi Goldwasser, and Avi Wigderson. 1988. Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation (Extended Abstract). In STOC. 1--10. Google ScholarDigital Library
- Daniel J. Bernstein and Peter Schwabe. 2008. New AES Software Speed Records. In INDOCRYPT 2008. 322--336. Google ScholarDigital Library
- Dan Bogdanov, Sven Laur, and Jan Willemson. 2008. Sharemind: A Framework for Fast Privacy-Preserving Computations. In ESORICS . 192--206. Google ScholarDigital Library
- Dan Bogdanov, Marko J oemets, Sander Siim, and Meril Vaht. 2016. Privacy-preserving tax fraud detection in the cloud with realistic data volumes. Cybernetica research report.Google Scholar
- Joan Boyar and René Peralta. 2010. A New Combinational Logic Minimization Technique with Applications to Cryptology. In SEA 2010, . 178--189. Google ScholarDigital Library
- Ran Canetti. 2001. Universally Composable Security: A New Paradigm for Cryptographic Protocols. In FOCS . 136--145. Google ScholarDigital Library
- David Chaum, Claude Crépeau, and Ivan Damgård. 1988. Multiparty Unconditionally Secure Protocols (Extended Abstract). In STOC . 11--19. Google ScholarDigital Library
- Ronald Cramer, Ivan Damgård, and Yuval Ishai. 2005. Share Conversion, Pseudorandom Secret-Sharing and Applications to Secure Computation. In TCC . 342--362. Google ScholarDigital Library
- Ivan Damgård and Marcel Keller. 2010. Secure Multiparty AES. In FC. 367--374. Google ScholarDigital Library
- Ivan Damgård, Marcel Keller, Enrique Larraia, Christian Miles, and Nigel P. Smart. 2012. Implementing AES via an Actively/Covertly Secure Dishonest-Majority MPC Protocol. In SCN . 241--263. Google ScholarDigital Library
- Ivan Damgård, Marcel Keller, Enrique Larraia, Valerio Pastro, Peter Scholl, and Nigel P. Smart. 2013. Practical Covertly Secure MPC for Dishonest Majority - Or: Breaking the SPDZ Limits. In ESORICS. 1--18.Google Scholar
- Morris Dworkin. 2001. Recommendation for block cipher modes of operation. methods and techniques . Technical Report. DTIC Document. Google ScholarDigital Library
- Niels Ferguson and Bruce Schneier. 2003. Practical Cryptography .John Wiley & Sons. Google ScholarDigital Library
- Jun Furukawa, Yehuda Lindell, Ariel Nof, and Or Weinstein. 2017. High-Throughput Secure Three-Party Computation for Malicious Adversaries and an Honest Majority. In EUROCRYPT 2017. 225--255.Google ScholarCross Ref
- Oded Goldreich. 2004. The Foundations of Cryptography - Volume 2, Basic Applications .Cambridge University Press. Google ScholarDigital Library
- Oded Goldreich, Silvio Micali, and Avi Wigderson. 1987. How to Play any Mental Game or A Completeness Theorem for Protocols with Honest Majority. In STOC. 218--229. Google ScholarDigital Library
- Dai Ikarashi, Ryo Kikuchi, Koki Hamada, and Koji Chida. 2014. Actively Private and Correct MPC Scheme in $t<n/2$ from Passively Secure Schemes with Small Overhead. IACR Cryptology ePrint Archive , Vol. 2014 (2014), 304.Google Scholar
- Mitsuru Ito, Akira Saito, and Takao Nishizeki. 1989. Secret sharing scheme realizing general access structure. IEICE Transactions , Vol. 72 (1989), 56--64. Issue 9.Google Scholar
- Sriram Keelveedhi, Mihir Bellare, and Thomas Ristenpart. 2013. DupLESS: Server-Aided Encryption for Deduplicated Storage. In USENIX Security . 179--194. Google ScholarDigital Library
- Marcel Keller, Peter Scholl, and Nigel P. Smart. 2013. An architecture for practical actively secure MPC with dishonest majority. In ACM CCS. 549--560. Google ScholarDigital Library
- Eizen Kimura, Koki Hamada, Ryo Kikuchi, Koji Chida, Kazuya Okamoto, Shirou Manabe, Tomohiro Kuroda, Yasushi Matsumura, Toshihiro Takeda, and Naoki Mihara. 2016. Evaluation of Secure Computation in a Distributed Healthcare Setting. In Proceedings of MIE2016 at HEC2016. 152--156.Google Scholar
- John Launchbury, Iavor S. Diatchki, Thomas DuBuisson, and Andy Adams-Moran. 2012. Efficient lookup-table protocol in secure multiparty computation. In ACM ICFP. 189--200. Google ScholarDigital Library
- Sven Laur, Riivo Talviste, and Jan Willemson. 2013. From Oblivious AES to Efficient and Secure Database Join in the Multiparty Setting. In ACNS. 84--101. Google ScholarDigital Library
- Jesper Buus Nielsen, Peter Sebastian Nordholt, Claudio Orlandi, and Sai Sheshank Burra. 2012. A New Approach to Practical Active-Secure Two-Party Computation. In CRYPTO. 681--700. Google ScholarDigital Library
- NIST. 2001. Announcing the ADVANCED ENCRYPTION STANDARD (AES) . Technical Report.Google Scholar
- Michael Palmer. 2012. Hands-on networking fundamentals .Cengage learning. Google ScholarDigital Library
- Benny Pinkas, Thomas Schneider, Nigel P. Smart, and Stephen C. Williams. 2009. Secure Two-Party Computation Is Practical. In ASIACRYPT. 250--267. Google ScholarDigital Library
- Peter Rindal and Mike Rosulek. 2016. Faster Malicious 2-Party Secure Computation with Online/Offline Dual Execution. In USENIX Security. 297--314. Google ScholarDigital Library
- Justine Sherry, Chang Lan, Raluca Ada Popa, and Sylvia Ratnasamy. 2015. BlindBox: Deep Packet Inspection over Encrypted Traffic. In SIGCOMM. 213--226. Google ScholarDigital Library
- Riivo Talviste. 2016. Applying Secure Multi-Party Computation in Practice . Ph.D. Dissertation. University of Tartu.Google Scholar
- Andrew Chi-Chih Yao. 1986. How to Generate and Exchange Secrets (Extended Abstract). In FOCS. 162--167. Google ScholarDigital Library
- Samee Zahur, Mike Rosulek, and David Evans. 2015. Two Halves Make a Whole - Reducing Data Transfer in Garbled Circuits Using Half Gates. In EUROCRYPT. 220--250.Google Scholar
Index Terms
- High-Throughput Secure AES Computation
Recommendations
Improvements to Secure Computation with Penalties
CCS '16: Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications SecurityMotivated by the impossibility of achieving fairness in secure computation [Cleve, STOC 1986], recent works study a model of fairness in which an adversarial party that aborts on receiving output is forced to pay a mutually predefined monetary penalty ...
Complete fairness in secure two-party computation
STOC '08: Proceedings of the fortieth annual ACM symposium on Theory of computingIn the setting of secure two-party computation, two mutually distrusting parties wish to compute some function of their inputs while preserving, to the extent possible, various security properties such as privacy, correctness, and more. One desirable ...
Black-Box Constructions of Protocols for Secure Computation
In this paper, we study the question of whether or not it is possible to construct protocols for general secure computation in the setting of malicious adversaries and no honest majority that use the underlying primitive (e.g., enhanced trapdoor ...
Comments