Wilko Henecka
ABSTRACT
Secure two-party computation allows two untrusting parties to jointly compute an arbitrary function on their respective private inputs while revealing no information beyond the outcome. Existing cryptographic compilers can automatically generate secure computation protocols from high-level specifications, but are often limited in their use and efficiency of generated protocols as they are based on either garbled circuits or (additively) homomorphic encryption only.
In this paper we present TASTY, a novel tool for automating, i.e., describing, generating, executing, benchmarking, and comparing, efficient secure two-party computation protocols. TASTY is a new compiler that can generate protocols based on homomorphic encryption and efficient garbled circuits as well as combinations of both, which often yields the most efficient protocols available today. The user provides a high-level description of the computations to be performed on encrypted data in a domain-specific language. This is automatically transformed into a protocol. TASTY provides most recent techniques and optimizations for practical secure two-party computation with low online latency. Moreover, it allows to efficiently evaluate circuits generated by the well-known Fairplay compiler.
We use TASTY to compare protocols for secure multiplication based on homomorphic encryption with those based on garbled circuits and highly efficient Karatsuba multiplication. Further, we show how TASTY improves the online latency for securely evaluating the AES functionality by an order of magnitude compared to previous software implementations. TASTY allows to automatically generate efficient secure protocols for many privacy-preserving applications where we consider the use cases for private set intersection and face recognition protocols.
- }}M. Barni, P. Failla, V. Kolesnikov, R. Lazzeretti, A.-R. Sadeghi, and T. Schneider. Secure evaluation of private linear branching programs with medical applications. In European Symposium on Research in Computer Security (ESORICS'09), volume 5789 of LNCS, pages 424--439. Springer, 2009. Google Scholar
Digital Library
- }}D. Beaver. Precomputing oblivious transfer. In Advances in Cryptology -- CRYPTO'95, volume 963 of LNCS, pages 97--109. Springer, 1995. Google ScholarDigital Library
- }}A. Ben-David, N. Nisan, and B. Pinkas. FairplayMP: a system for secure multi-party computation. In ACM Conference on Computer and Communications Security (ACM CCS'08), pages 257--266. ACM, 2008. http://fairplayproject.net/fairplayMP.html. Google ScholarDigital Library
- }}M. Ben-Or, S. Goldwasser, and A. Wigderson. Completeness theorems for non-cryptographic fault-tolerant distributed computation. In Symp. on Theory of Comp. (STOC'88), pages 1--10. ACM, 1988. Google ScholarDigital Library
- }}D. Bogdanov, S. Laur, and J. Willemson. Sharemind: A framework for fast privacy-preserving computations. In European Symposium on Research in Computer Security (ESORICS'08), volume 5283 of LNCS, pages 192--206. Springer, 2008. Google ScholarDigital Library
- }}D. Boneh, E.-J. Goh, and K. Nissim. Evaluating 2-DNF formulas on ciphertexts. In Theory of Cryptography (TCC'05), volume 3378 of LNCS, pages 325--341. Springer, 2005. Google ScholarDigital Library
- }}J. Brickell, D. E. Porter, V. Shmatikov, and E. Witchel. Privacy-preserving remote diagnostics. In ACM Conference on Computer and Communications Security (ACM CCS'07), pages 498--507. ACM, 2007. Google ScholarDigital Library
- }}T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill Book Company, 2001. Google ScholarDigital Library
- }}I. Damg ård, M. Geisler, and M. Kr øigaard. Efficient and secure comparison for on-line auctions. In Australasian Conference on Information Security and Privacy (ACISP'07), volume 4586 of LNCS, pages 416--430. Springer, 2007. Google ScholarDigital Library
- }}I. Damg ård, M. Geisler, and M. Kr øigaard. A correction to "Efficient and Secure Comparison for On-Line Auctions". Cryptology ePrint Archive, Report 2008/321, 2008. http://eprint.iacr.org.Google Scholar
- }}I. Damg ård, M. Geisler, M. Kr øig ård, and J. B. Nielsen. Asynchronous multiparty computation: Theory and implementation. In Public Key Cryptography (PKC'09), volume 5443 of LNCS, pages 160--179. Springer, 2009. http://viff.dk. Google ScholarDigital Library
- }}I. Damg ård and M. Jurik. A generalisation, a simplification and some applications of paillier's probabilistic public-key system. In Public-Key Cryptography (PKC'01), volume 1992 of LNCS, pages 119--136. Springer, 2001. Google ScholarDigital Library
- }}M. Dijk, C. Gentry, S. Halevi, and V. Vaikuntanathan. Fully homomorphic encryption over the integers. In Advances in Cryptology -- EUROCRYPT'10, LNCS, pages 24--43. Springer, 2010. Google ScholarDigital Library
- }}T. El Gamal. A public key cryptosystem and a signature scheme based on discrete logarithms. In Advances in Cryptology -- CRYPTO '84, volume 196 of LNCS, pages 10--18. Springer, 1985. Google ScholarDigital Library
- }}Z. Erkin, M. Franz, J. Guajardo, S. Katzenbeisser, I. Lagendijk, and T. Toft. Privacy-preserving face recognition. In Privacy Enhancing Technologies (PET'09), volume 5672 of LNCS, pages 235--253. Springer, 2009. Google ScholarDigital Library
- }}M. J. Freedman, K. Nissim, and B. Pinkas. Efficient private matching and set intersection. In Advances in Cryptology -- EUROCRYPT'04, volume 3027 of LNCS, pages 1--19. Springer, 2004.Google Scholar
- }}C. Gentry. Fully homomorphic encryption using ideal lattices. In ACM Symposium on Theory of Computing (STOC'09), pages 169--178. ACM, 2009. Google ScholarDigital Library
- }}C. Gentry, S. Halevi, and V. Vaikuntanathan. A simple BGN-type cryptosystem from LWE. In Advances in Cryptology -- EUROCRYPT'10, volume 6110 of LNCS, pages 506--522. Springer, 2010. Google ScholarDigital Library
- }}D. Giry and J.-J. Quisquater. Cryptographic key length recommendation, 2010. http://keylength.com.Google Scholar
- }}GMP -- GNU multi precision arithmetic library. http://gmplib.org.Google Scholar
- }}gmpy -- multiprecision arithmetic for Python. http://code.google.com/p/gmpy.Google Scholar
- }}Gnuplot.py. http://gnuplot-py.sourceforge.net.Google Scholar
- }}W. Henecka, S. K ögl, A.-R. Sadeghi, T. Schneider, and I. Wehrenberg. TASTY: Tool for Automating Secure Two-partY computations. Cryptology ePrint Archive, Report 2010/365, 2010. http://eprint.iacr.org/.Google Scholar
- }}Y. Ishai, J. Kilian, K. Nissim, and E. Petrank. Extending oblivious transfers efficiently. In Advances in Cryptology -- CRYPTO'03, volume 2729 of LNCS, pages 145--161. Springer, 2003.Google Scholar
- }}A. Jarrous and B. Pinkas. Secure hamming distance based computation and its applications. In Applied Cryptography and Network Security (ACNS'09), volume 5536 of LNCS, pages 107--124. Springer, 2009. Google ScholarDigital Library
- }}A. Karatsuba and Y. Ofman. Multiplication of many-digital numbers by automatic computers. SSSR Academy of Sciences, 145:293--294, 1962.Google Scholar
- }}V. Kolesnikov, A.-R. Sadeghi, and T. Schneider. Improved garbled circuit building blocks and applications to auctions and computing minima. In Cryptology and Network Security (CANS'09), volume 5888 of LNCS, pages 1--20. Springer, 2009. Google ScholarDigital Library
- }}V. Kolesnikov, A.-R. Sadeghi, and T. Schneider. Modular design of efficient secure function evaluation protocols. Cryptology ePrint Archive, Report 2010/079, February 2010. http://eprint.iacr.org.Google Scholar
- }}Y. Lindell and B. Pinkas. A proof of Yao's protocol for secure two-party computation. Journal of Cryptology, 22(2):161--188, 2009. Cryptology ePrint Archive: Report 2004/175. Google ScholarDigital Library
- }}Y. Lindell and B. Pinkas. Secure multiparty computation for privacy-preserving data mining. J. of Privacy and Confidentiality, 1(1):59--98, 2009.Google ScholarCross Ref
- }}Y. Lindell, B. Pinkas, and N. Smart. Implementing two-party computation efficiently with security against malicious adversaries. In Security and Cryptography for Networks (SCN'08), volume 5229 of LNCS, pages 2--20. Springer, 2008. Google ScholarDigital Library
- }}P. MacKenzie, A. Oprea, and M. K. Reiter. Automatic generation of two-party computations. In ACM Conference on Computer and Communications Security (ACM CCS'03), pages 210--219. ACM, 2003. Google ScholarDigital Library
- }}D. Malkhi, N. Nisan, B. Pinkas, and Y. Sella. Fairplay -- a secure two-party computation system. In USENIX Security Symposium, 2004. http://fairplayproject.net/fairplay.html. Google ScholarDigital Library
- }}T. Moran. The qilin crypto SDK -- an open-source java SDK for rapid prototyping of cryptographic protocols. http://qilin.seas.harvard.edu.Google Scholar
- }}M. Naor and B. Pinkas. Efficient oblivious transfer protocols. In ACM-SIAM Symposium On Discrete Algorithms (SODA'01), pages 448--457. Society for Industrial and Applied Mathematics, 2001. Google ScholarDigital Library
- }}M. Naor, B. Pinkas, and R. Sumner. Privacy preserving auctions and mechanism design. In ACM Conf. on Electronic Commerce, pages 129--139, 1999. Google ScholarDigital Library
- }}J. D. Nielsen. Languages for Secure Multiparty Computation and Towards Strongly Typed Macros. PhD thesis, University of Aarhus, Denmark, 2009.Google Scholar
- }}J. D. Nielsen and M. I. Schwartzbach. A domain-specific programming language for secure multiparty computation. In Workshop on Programming Languages and Analysis for Security (PLAS'07), pages 21--30. ACM, 2007. Google ScholarDigital Library
- }}J. Nzouonta, M. C. Silaghi, and M. Yokoo. Secure computation for combinatorial auctions and market exchanges. In Autonomous Agents and Multiagent Systems (AAMAS'04), pages 1398--1399. IEEE, 2004. Google ScholarDigital Library
- }}M. Osadchy, B. Pinkas, A. Jarrous, and B. Moskovich. SCiFI - a system for secure face identification. In IEEE Symposium on Security & Privacy (S &P'10), pages 239--254. IEEE, 2010. Google ScholarDigital Library
- }}P. Paillier. Public-key cryptosystems based on composite degree residuosity classes. In Advances in Cryptology -- EUROCRYPT'99, volume 1592 of LNCS, pages 223--238. Springer, 1999. Google ScholarDigital Library
- }}A. Paus, A.-R. Sadeghi, and T. Schneider. Practical secure evaluation of semi-private functions. In Applied Cryptography and Network Security (ACNS'09), volume 5536 of LNCS, pages 89--106. Springer, 2009. Google ScholarDigital Library
- }}T. P. Pedersen. Non-interactive and information-theoretic secure verifiable secret sharing. In Advances in Cryptology -- CRYPTO'91, volume 576 of LNCS, pages 129--140. Springer, 1992. Google ScholarDigital Library
- }}B. Pinkas, T. Schneider, N. P. Smart, and S. C. Williams. Secure two-party computation is practical. In Advances in Cryptology -- ASIACRYPT'09, volume 5912 of LNCS, pages 250--267. Springer, 2009. Google ScholarDigital Library
- }}A.-R. Sadeghi, T. Schneider, and I. Wehrenberg. Efficient privacy-preserving face recognition. In 12th International Conference on Information Security and Cryptology (ICISC '09), LNCS. Springer, 2009. Google ScholarDigital Library
- }}A. Schr öpfer, F. Kerschbaum, D. Biswas, S. Gei ßinger, and C. Sch ütz. L1 -- faster development and benchmarking of cryptographic protocols. In ECRYPT Workshop on Software Performance Enhancements for Encryption and Decryption and Cryptographic Compilers (SPEED-CC '09), October 12--13, 2009.Google Scholar
- }}Standards for efficient cryptography, SEC 2: Recommended elliptic curve domain parameters. Technical report, Certicom Research, 2000. Available from http://www.secg.org.Google Scholar
- }}M. C. Silaghi. SMC: Secure multiparty computation language. http://cs.fit.edu/ msilaghi/SMC/, 2004.Google Scholar
- }}N. P. Smart and F. Vercauteren. Fully homomorphic encryption with relatively small key and ciphertext sizes. In Public Key Cryptography (PKC'10), volume 6056 of LNCS, pages 420--443. Springer, 2010. Google ScholarDigital Library
- }}TASTY -- Tool for Automating Secure Two-partY computations. http://tastyproject.net.Google Scholar
- }}M. Turk and A. Pentland. Eigenfaces for recognition. Journal of Cognitive Neuroscience, 3(1):71--86, 1991. Google ScholarDigital Library
- }}A. C. Yao. Protocols for secure computations. In IEEE Symposium on Foundations of Computer Science (FOCS'82), pages 160--164. IEEE, 1982. Google ScholarDigital Library
- }}A. C. Yao. How to generate and exchange secrets. In IEEE Symposium on Foundations of Computer Science (FOCS'86), pages 162--167. IEEE, 1986. Google ScholarDigital Library
Index Terms
- TASTY: tool for automating secure two-party computations
Recommendations
Optimizing Semi-Honest Secure Multiparty Computation for the Internet
CCS '16: Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications SecurityIn the setting of secure multiparty computation, a set of parties with private inputs wish to compute some function of their inputs without revealing anything but their output. Over the last decade, the efficiency of secure two-party computation has ...
Computationally Secure Oblivious Transfer
We describe new computationally secure protocols of 1-out-of-N oblivious transfer, k-out-of-N oblivious transfer, and oblivious transfer with adaptive queries. The protocols are very efficient compared with solutions based on generic two-party ...
Foundations of garbled circuits
CCS '12: Proceedings of the 2012 ACM conference on Computer and communications securityGarbled circuits, a classical idea rooted in the work of Yao, have long been understood as a cryptographic technique, not a cryptographic goal. Here we cull out a primitive corresponding to this technique. We call it a garbling scheme. We provide a ...
Comments