Abstract
Secure 2-party computation (2PC) is becoming practical for some applications. However, most approaches are limited by the fact that the desired functionality must be represented as a boolean circuit. In response, random-access machines (RAM programs) have recently been investigated as a promising alternative representation.
In this work, we present the first practical protocols for evaluating RAM programs with security against malicious adversaries. A useful efficiency measure is to divide the cost of malicious-secure evaluation of \(f\) by the cost of semi-honest-secure evaluation of \(f\). Our RAM protocols achieve ratios matching the state of the art for circuit-based 2PC. For statistical security \(2^{-s}\), our protocol without preprocessing achieves a ratio of \(s\); our online-offline protocol has a pre-processing phase and achieves online ratio \(\sim 2 s / \log T\), where \(T\) is the total execution time of the RAM program.
To summarize, our solutions show that the “extra overhead” of obtaining malicious security for RAM programs (beyond what is needed for circuits) is minimal and does not grow with the running time of the program.
Mike Rosulek — Supported by NSF award CCF-1149647.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Afshar, A., Hu, Z., Mohassel, P., Rosulek, M.: How to efficiently evaluate ram programs with malicious security. Cryptology ePrint Archive, Report 2014/759 (2014). http://eprint.iacr.org/
Asharov, G., Lindell, Y., Schneider, T., Zohner, M.: More efficient oblivious transfer and extensions for faster secure computation. In: Sadeghi, et al. (eds.) [35], pp. 535–548
Beaver, D.: Commodity-based cryptography (extended abstract). In: 29th Annual ACM Symposium on Theory of Computing, pp. 446–455. ACM Press, May 1997
Bellare, M., Hoang, V.T., Rogaway, P.: Adaptively secure garbling with applications to one-time programs and secure outsourcing. In: Wang, X., Sako, K. (eds.) ASIACRYPT 2012. LNCS, vol. 7658, pp. 134–153. Springer, Heidelberg (2012)
Bellare, M., Hoang, V.T., Rogaway, P.: Foundations of garbled circuits. In: Yu, et al. (eds.) [43], pp. 784–796
Chen, J., Wee, H.: Fully, (almost) tightly secure IBE and dual system groups. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013, Part II. LNCS, vol. 8043, pp. 435–460. Springer, Heidelberg (2013)
Chung, K.-M., Pass, R.: A simple ORAM. Cryptology ePrint Archive, Report 2013/243 (2013). http://eprint.iacr.org/2013/243
Damgård, I., Pastro, V., Smart, N.P., Zakarias, S.: Multiparty computation from somewhat homomorphic encryption. In: Safavi-Naini, Canetti. (eds.) [36], pp. 643–662
Frederiksen, T.K., Jakobsen, T.P., Nielsen, J.B., Nordholt, P.S., Orlandi, C.: MiniLEGO: efficient secure two-party computation from general assumptions. In: Johansson, Nguyen (eds.) [17], pp. 537–556
Gentry, C., Halevi, S., Lu, S., Ostrovsky, R., Raykova, M., Wichs, D.: Garbled RAM revisited. In: Nguyen, P.Q., Oswald, E. (eds.) EUROCRYPT 2014. LNCS, vol. 8441, pp. 405–422. Springer, Heidelberg (2014)
Goldreich, O., Micali, S., Wigderson, A.: How to play any mental game or a completeness theorem for protocols with honest majority. In: Aho, A. (ed.) 19th Annual ACM Symposium on Theory of Computing, pp. 218–229. ACM Press, May 1987
Goldreich, O., Ostrovsky, R.: Software protection and simulation on oblivious RAMs. J. ACM 43(3), 431–473 (1996)
Gordon, S.D., Katz, J., Kolesnikov, V., Krell, F., Malkin, T., Raykova, M., Vahlis, Y.: Secure two-party computation in sublinear (amortized) time. In: Yu, et al. (eds.) [43], pp. 513–524
Huang, Y., Katz, J., Evans, D.: Efficient secure two-party computation using symmetric cut-and-choose. In: Canetti, Garay (eds.) [6], pp. 18–35
Huang, Y., Katz, J., Kolesnikov, V., Kumaresan, R., Malozemoff, A.J.: Amortizing garbled circuits. In: Garay, J.A., Gennaro, R. (eds.) CRYPTO 2014, Part II. LNCS, vol. 8617, pp. 458–475. Springer, Heidelberg (2014)
Ishai, Y., Kilian, J., Nissim, K., Petrank, E.: Extending oblivious transfers efficiently. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 145–161. Springer, Heidelberg (2003)
Johansson, T., Nguyen, P.Q. (eds.): EUROCRYPT 2013. LNCS, vol. 7881. Springer, Heidelberg (2013)
Kamara, S., Mohassel, P., Riva, B.: Salus: a system for server-aided secure function evaluation. In: Yu, et al. (eds.) [43], pp. 797–808
Keller, M., Scholl, P.: Efficient, oblivious data structures for MPC. Cryptology ePrint Archive, Report 2014/137 (2014). http://eprint.iacr.org/
Kiraz, M., Schoenmakers, B.: A protocol issue for the malicious case of yao’s garbled circuit construction. In: 27th Symposium on Information Theory in the Benelux, pp. 283–290 (2006)
Kolesnikov, V., Schneider, T.: Improved garbled circuit: free XOR gates and applications. In: Aceto, L., Damgård, I., Goldberg, L.A., Halldórsson, M.M., Ingólfsdóttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part II. LNCS, vol. 5126, pp. 486–498. Springer, Heidelberg (2008)
Kreuter, B., Shelat, A., Shen, C.-H.: Billion-gate secure computation with malicious adversaries. In: Proceedings of the 21st USENIX Conference on Security Symposium, p. 14. USENIX Association (2012)
Lindell, Y.: Fast cut-and-choose based protocols for malicious and covert adversaries. In: Canetti, Garay (eds.) [6], pp. 1–17
Lindell, Y., Pinkas, B.: An efficient protocol for secure two-party computation in the presence of malicious adversaries. In: Naor, M. (ed.) EUROCRYPT 2007. LNCS, vol. 4515, pp. 52–78. Springer, Heidelberg (2007)
Lindell, Y., Pinkas, B.: Secure two-party computation via cut-and-choose oblivious transfer. In: Ishai, Y. (ed.) TCC 2011. LNCS, vol. 6597, pp. 329–346. Springer, Heidelberg (2011)
Lindell, Y., Riva, B.: Cut-and-Choose yao-based secure computation in the online/offline and batch settings. In: Garay, J.A., Gennaro, R. (eds.) CRYPTO 2014, Part II. LNCS, vol. 8617, pp. 476–494. Springer, Heidelberg (2014)
Liu, C., Huang, Y., Shi, E., Katz, J., Hicks, M.: Automating efficient RAM-model secure computation. In: Proceedings of the IEEE Symposium on Security and Privacy (Oakland), May 2014
Lu, S., Ostrovsky, R.: How to garble RAM programs. In: Johansson, Nguyen (eds.) [17], pp. 719–734
Mohassel, P., Franklin, M.K.: Efficiency tradeoffs for malicious two-party computation. In: Yung, M., Dodis, Y., Kiayias, A., Malkin, T. (eds.) PKC 2006. LNCS, vol. 3958, pp. 458–473. Springer, Heidelberg (2006)
Mohassel, P., Riva, B.: Garbled circuits checking garbled circuits: more efficient and secure two-party computation. In: Canetti, Garay (eds.) [6], pp. 36–53
Mood, B., Gupta, D., Feigenbaum, J., Butler, K.: Reuse it or lose it: more efficient secure computation through reuse of encrypted values. In: ACM CCS (2014)
Nielsen, J.B., Nordholt, P.S., Orlandi, C., Burra, S.S.: A new approach to practical active-secure two-party computation. In: Safavi-Naini, Canetti (eds.) [36], pp. 681–700
Nielsen, J.B., Orlandi, C.: LEGO for two-party secure computation. In: Reingold, O. (ed.) TCC 2009. LNCS, vol. 5444, pp. 368–386. Springer, Heidelberg (2009)
Pinkas, B., Schneider, T., Smart, N.P., Williams, S.C.: Secure two-party computation is practical. In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol. 5912, pp. 250–267. Springer, Heidelberg (2009)
Sadeghi, A.R., Gligor, V.D., Yung, M. (eds.): ACM CCS 13: 20th Conference on Computer and Communications Security. ACM Press, November 2013
Safavi-Naini, R., Canetti, R. (eds.): CRYPTO 2012. LNCS, vol. 7417. Springer, Heidelberg (2012)
Shelat, A., Shen, C.: Two-Output secure computation with malicious adversaries. In: Paterson, K.G. (ed.) EUROCRYPT 2011. LNCS, vol. 6632, pp. 386–405. Springer, Heidelberg (2011)
Shelat, A., Shen, C.-H.: Fast two-party secure computation with minimal assumptions. In: Sadeghi, et al. (eds.) [35], pp. 523–534
Shi, E., Chan, T.-H.H., Stefanov, E., Li, M.: Oblivious RAM with O((logN)\(^\text{3 }\)) worst-case cost. In: Lee, D.H., Wang, X. (eds.) ASIACRYPT 2011. LNCS, vol. 7073, pp. 197–214. Springer, Heidelberg (2011)
Stefanov, E., van Dijk, M., Shi, E., Fletcher, C.W., Ren, L., Yu, X., Devadas, S.: Path ORAM: an extremely simple oblivious RAM protocol. In: Sadeghi, et al. (eds.) [35], pp. 299–310
Yao, A.C.-C.: Protocols for secure computations (extended abstract). In: 23rd Annual Symposium on Foundations of Computer Science, pp. 160–164. IEEE Computer Society Press, November 1982
Yao, A.C.-C.: How to generate and exchange secrets (extended abstract). In: 27th Annual Symposium on Foundations of Computer Science, pp. 162–167. IEEE Computer Society Press, October 1986
Yu, T., Danezis, G., Gligor, V.D. (eds.): ACM CCS 12: 19th Conference on Computer and Communications Security. ACM Press, October 2012
Zahur, S.: Obliv-c: a lightweight compiler for data-oblivious computation. In: Workshop on Applied Multi-Party Computation. Microsoft Research, Redmond (2014)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 International Association for Cryptologic Research
About this paper
Cite this paper
Afshar, A., Hu, Z., Mohassel, P., Rosulek, M. (2015). How to Efficiently Evaluate RAM Programs with Malicious Security. In: Oswald, E., Fischlin, M. (eds) Advances in Cryptology -- EUROCRYPT 2015. EUROCRYPT 2015. Lecture Notes in Computer Science(), vol 9056. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-46800-5_27
Download citation
DOI: https://doi.org/10.1007/978-3-662-46800-5_27
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-46799-2
Online ISBN: 978-3-662-46800-5
eBook Packages: Computer ScienceComputer Science (R0)