Salus: a system for server-aided secure function evaluation

ABSTRACT

Secure function evaluation (SFE) allows a set of mutually distrustful parties to evaluate a function of their joint inputs without revealing their inputs to each other. SFE has been the focus of active research and recent work suggests that it can be made practical. Unfortunately, current protocols and implementations have inherent limitations that are hard to overcome using standard and practical techniques. Among them are: (1) requiring participants to do work linear in the size of the circuit representation of the function; (2) requiring all parties to do the same amount of work; and (3) not being able to provide complete fairness.

A promising approach for overcoming these limitations is to augment the SFE setting with a small set of untrusted servers that have no input to the computation and that receive no output, but that make their computational resources available to the parties. In this model, referred to as server-aided SFE, the goal is to tradeoff the parties' work at the expense of the servers. Motivated by the emergence of public cloud services such as Amazon EC2 and Microsoft Azure, recent work has explored the extent to which server-aided SFE can be achieved with a single server.

In this work, we revisit the sever-aided setting from a practical perspective and design single-server-aided SFE protocols that are considerably more efficient than all previously-known protocols. We achieve this in part by introducing several new techniques for garbled-circuit-based protocols, including a new and efficient input-checking mechanism for cut-and-choose and a new pipelining technique that works in the presence of malicious adversaries. Furthermore, we extend the server-aided model to guarantee fairness which is an important property to achieve in practice.

Finally, we implement and evaluate our constructions experimentally and show that our protocols (regardless of the number of parties involved) yield implementations that are 4 and 6 times faster than the most optimized two-party SFE implementation when the server is assumed to be malicious and covert, respectively.

References

1. G. Asharov, A. Jain, A. Lopez-Alt, E. Tromer, V. Vaikuntanathan, and D. Wichs. Multiparty computation with low communication, computation and interaction via threshold FHE. In EUROCRYPT, 2012.
2. Y. Aumann and Y. Lindell. Security against covert adversaries: Efficient protocols for realistic adversaries. In TCC, 2007.
3. B. Barak and O. Goldreich. Universal arguments and their applications. In CCC, 2002.
4. A. Ben-David, N. Nisan, and B. Pinkas. Fairplaymp: a system for secure multi-party computation. In CCS, 2008.
5. D. Bogdanov, S. Laur, and J. Willemson. Sharemind: A framework for fast privacy-preserving computations. In ESORICS, 2008.
6. P. Bogetoft, D. Christensen, I. Damgard, M. Geisler, T. Jakobsen, M. Krøigaard, J. Nielsen, J. B. Nielsen, K. Nielsen, J. Pagter, M. Schwartzbach, and T. Toft. Secure multiparty computation goes live. In FC, 2009.
7. P. Bogetoft, I. Damgard, T. P. Jakobsen, K. Nielsen, J. Pagter, and T. Toft. A practical implementation of secure auctions based on multiparty integer computation. In FC, 2006.
8. J. Boyar and R. Peralta. A small depth-16 circuit for the aes s-box. In Information Security and Privacy Research, 2012.
9. R. Canetti. Security and composition of multi-party cryptographic protocols. Journal of Cryptology, 2000.
10. D. Chaum, C. Crépeau, and I. Damgard. Multiparty unconditionally secure protocols. In STOC, 1988.
11. S. G. Choi, K. Hwang, J. Katz, T. Malkin, and D. Rubenstein. Secure multi-party computation of boolean circuits with applications to privacy in on-line marketplaces. In CT-RSA, 2012.
12. R. Cleve. Limits on the security of coin flips when half the processors are faulty. In STOC, 1986.
13. Ivan Damgaard, Martin Geisler, Mikkel Kroigaard, and Jesper Buus Nielsen. Asynchronous multiparty computation: Theory and implementation. In PKC, 2009.
14. I. Damgard, S. Faust, and C. Hazay. Secure two-party computation with low communication. In TCC, 2012.
15. I. Damgard, M. Geisler, M. Krøigaard, and J.-B. Nielsen. Asynchronous multiparty computation: Theory and implementation. In PKC, 2009.
16. I. Damgard and Y. Ishai. Constant-round multiparty computation using a black-box pseudorandom generator. In CRYPTO, 2005.
17. I. Damgard, Y. Ishai, M. Krøigaard, J.-B. Nielsen, and A. Smith. Scalable multiparty computation with nearly optimal work and resilience. In CRYPTO, 2008.
18. U. Feige, J. Killian, and M. Naor. A minimal model for secure computation (extended abstract). In STOC, 1994.
19. J. Garay, P. MacKenzie, M. Prabhakaran, and K. Yang. Resource fairness and composability of cryptographic protocols. TCC, 2006.
20. R. Gennaro, C. Gentry, and B. Parno. Non-interactive verifiable computing: outsourcing computation to untrusted workers. In Advances in Cryptology - CRYPTO '10, volume 6223 of Lecture Notes in Computer Science, pages 465--482. Springer-Verlag, 2010.
21. C. Gentry. Fully homomorphic encryption using ideal lattices. In STOC, 2009.
22. O. Goldreich. Foundations of Cryptography -- Volume 2. Cambridge University Press, 2004.
23. O. Goldreich. Foundations of Cryptography -- Volume 1. Cambridge University Press, 2006.
24. O. Goldreich, S. Micali, and A. Wigderson. How to play ANY mental game. In STOC, 1987.
25. D. Gordon, J. Katz, V. Kolesnikov, T. Malkin, M. Raykova, and Y. Vahlis. Secure computation with sublinear amortized work. Technical Report 2011/482, IACR ePrint Cryptography Archive, 2011.
26. S. Gordon and J. Katz. Partial fairness in secure two-party computation. EUROCRYPT, 2010.
27. S. D. Gordon, C. Hazay, J. Katz, and Y. Lindell. Complete fairness in secure two-party computation. Journal of the ACM (JACM), 58(6):24, 2011.
28. W. Henecka, S. Kogl, A.-R. Sadeghi, T. Schneider, and I. Wehrenberg. TASTY: tool for automating secure two-party computations. In CCS, 2010.
29. Y. Huang, D. Evans, J. Katz, and L. Malka. Faster secure two-party computation using garbled circuits. In USENIX Security, 2011.
30. Y. Ishai, J. Kilian, K. Nissim, and E. Petrank. Extending oblivious transfers efficiently. In CRYPTO, 2003.
31. K. Jarvinen, V. Kolesnikov, A.-R. Sadeghi, and T. Schneider. Garbled circuits for leakage-resilience: hardware implementation and evaluation of one-time programs. In CHES, 2010.
32. S. Kamara, P. Mohassel, and M. Raykova. Outsourcing multi-party comptuation. Technical Report 2011/272, IACR ePrint Cryptography Archive, 2011.
33. J. Katz, R. Ostrovsky, and A. Smith. Round efficiency of multi-party computation with a dishonest majority. In EUROCRYPT, 2003.
34. M. S. Kiraz and B. Schoenmakers. An efficient protocol for fair secure two-party computation. In CT-RSA, 2008.
35. V. Kolesnikov and T. Schneider. Improved garbled circuit: Free xor gates and applications. In ICALP, 2008.
36. B. Kreuter, a. shelat, and C.-H. Shen. Towards billion-gate secure computation with malicious adversaries. Technical Report 2012/179, IACR ePrint Cryptography Archive, 2012.
37. Y. Lindell. Parallel coin-tossing and constant-round secure two-party computation. In CRYPTO, 2001.
38. Y. Lindell and B. Pinkas. An efficient protocol for secure two-party computation in the presence of malicious adversaries. In EUROCRYPT, 2007.
39. Y. Lindell and B. Pinkas. A proof of security of Yao's protocol for two-party computation. Journal of Cryptology, 2009.
40. Y. Lindell and B. Pinkas. Secure two-party computation via cut-and-choose oblivious transfer. In TCC, 2011.
41. Y. Lindell, B. Pinkas, and N. Smart. Implementing two-party computation efficiently with security against malicious adversaries. In SCN, 2008.
42. L. Malka. Vmcrypt: modular software architecture for scalable secure computation. In CCS, 2011.
43. D. Malkhi, N. Nisan, B. Pinkas, and Y. Sella. Fairplay--a secure two-party computation system. In USENIX Security, 2004.
44. S. Micali and P. Rogaway. Secure computation (abstract). In CRYPTO, 1992.
45. P. Mohassel and M. Franklin. Efficiency tradeoffs for malicious two-party computation. In PKC, 2006.
46. M. Naor and K. Nissim. Communication preserving protocols for secure function evaluation. In STOC, 2001.
47. M. Naor and B. Pinkas. Oblivious transfer and polynomial evaluation. In STOC, 1999.
48. M. Naor and B. Pinkas. Efficient oblivious transfer protocols. In SODA, 2001.
49. M. Naor, B. Pinkas, and R. Sumner. Privacy preserving auctions and mechanism design. In EC, 1999.
50. C. Peikert, V. Vaikuntanathan, and B. Waters. A framework for efficient and composable oblivious transfer. In CRYPTO, Berlin, Heidelberg, 2008.
51. B. Pinkas. Fair secure two-party computation. EUROCRYPT, 2003.
52. B. Pinkas, T. Schneider, N. Smart, and S. Williams. Secure two-party computation is practical. In ASIACRYPT, 2009.
53. M. Rabin. How to exchange secrets by oblivious transfer. Technical Report TR-81, Aiken Computation Lab, Harvard University, 1981.
54. A. Shamir. How to share a secret. Commun. ACM, November 1979.
55. A. Shelat and C. H. Shen. Two-output secure computation with malicious adversaries. In EUROCRYPT, 2011.
56. D. Woodruff. Revisiting the efficiency of malicious two-party computation. In EUROCRYPT, 2007.
57. A. Yao. Protocols for secure computations. In FOCS, 1982.
58. A. Yao. How to generate and exchange secrets. In FOCS, 1986.

Index Terms

• Security and privacy

• Social and professional topics

  • Computing / technology policy

    • Computer crime