Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
From Indifferentiability to Constructive Cryptography (and Back) Read chapter Read first chapter

2016 | OriginalPaper | Chapter

Constant-Round Maliciously Secure Two-Party Computation in the RAM Model

Authors : Carmit Hazay, Avishay Yanai

Published in: Theory of Cryptography

Publisher: Springer Berlin Heidelberg

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

The random-access memory (RAM) model of computation allows program constant-time memory lookup and is more applicable in practice today, covering many important algorithms. This is in contrast to the classic setting of secure 2-party computation (2PC) that mostly follows the approach for which the desired functionality must be represented as a boolean circuit. In this work we design the first constant round maliciously secure two-party protocol in the RAM model. Our starting point is the garbled RAM construction of Gentry et al. [16] that readily induces a constant round semi-honest two-party protocol for any RAM program assuming identity-based encryption schemes. We show how to enhance the security of their construction into the malicious setting while facing several challenges that stem due to handling the data memory. Next, we show how to apply our techniques to a more recent garbled RAM construction by Garg et al. [13] that is based on one-way functions.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Secure Multiparty RAM Computation in Constant Rounds
next chapter More Efficient Constant-Round Multi-party Computation from BMR and SHE
Appendix
Available only for authorised users
Footnotes
1
The size mentioned is correct when relying on the IBE assumption, while relying on the OWF assumption would incur database size of \(|D|\cdot \log |D| \cdot \mathsf {poly}(\kappa ) \).
 
2
This can always be done by encrypting the memory.
 
3
The following definition is derived from the definition given in [8].
 
4
The use of \(\rho _1,\rho _2\) does not reveal any information about the access pattern nor about the encryption key of the data, these are determined only by the keys \(k_1,k_2\) and the random strings \(r_1,r_2\).
 
5
Nevertheless, we note that the memory data D will be kept in the receiver’s local memory.
 
6
Gentry et al. further demonstrated that this weaker notion of security is useful by providing a transformation from this setting into the stronger setting for which the simulator does not receive this extra information. Their proof holds against semi-honest adversaries. A simple observation shows that their proof can be extended for the malicious 2PC setting by considering secure protocols that run the oblivious RAM and the garbling computations; see below our transformation.
 
7
As for RAM programs, ORAM schemes can also support this property. Moreover, the [16] transformation discussed in Sect. 2.1 can be applied to ORAM schemes as well.
 
8
For ease of presentation, Gentry et al. abstract the security properties of the IBE scheme using a new primitive denoted by Timed IBE (TIBE); see Sect. 2.4 for more details.
 
9
This s might be different from the s used in the garbling algorithm, still we used the same letter for simplification.
 
10
Note that this holds with overwhelming probability since some of the garbled circuits might be malformed.
 
11
Note that if \(\mathrm{S}\) is honest then \(\mathsf {out}_{t,z_1} = \mathsf {out}_{t,z_2}\) for every \(z_1,z_2\in \tilde{Z}\).
 
Literature
1.
Afshar, A., Hu, Z., Mohassel, P., Rosulek, M.: How to efficiently evaluate RAM programs with malicious security. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9056, pp. 702–729. Springer, Heidelberg (2015). doi:10.​1007/​978-3-662-46800-5_​27
2.
Beaver, D.: Foundations of secure interactive computing. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 377–391. Springer, Heidelberg (1992). doi:10.​1007/​3-540-46766-1_​31
3.
Beaver, D., Micali, S., Rogaway, P.: The round complexity of secure protocols. In: Harriet, O. (ed.) 22nd STOC, pp. 503–513. ACM (1990)
4.
Bellare, M., Hoang, V.T., Rogaway, P.: Foundations of garbled circuits. In: CCS, pp. 784–796 (2012)
5.
6.
7.
8.
9.
Cook, S.A., Reckhow, R.A.: Time-bounded random access machines. In: Proceedings of the 4th Annual ACM Symposium on Theory of Computing, Denver, Colorado, USA, 1–3 May 1972, pp. 73–80 (1972)
10.
11.
Garg, S., Gupta, D., Miao, P., Pandey, O.: Secure multiparty ram computation in constant rounds. In: TCC (2016, to appear)
12.
Garg, S., Lu, S., Ostrovsky, R.: Black-box garbled RAM. In: FOCS 2015, pp. 210–229 (2016)
13.
Garg, S., Lu, S., Ostrovsky, R., Scafuro, A.: Garbled RAM from one-way functions. In: STOC, pp. 449–458 (2015)
14.
Gentry, C., Goldman, K.A., Halevi, S., Julta, C., Raykova, M., Wichs, D.: Optimizing ORAM and using it efficiently for secure computation. In: De Cristofaro, E., Wright, M. (eds.) PETS 2013. LNCS, vol. 7981, pp. 1–18. Springer, Heidelberg (2013). doi:10.​1007/​978-3-642-39077-7_​1 CrossRef
15.
Gentry, C., Halevi, S., Jutla, C.S., Raykova, M.: Private database access with he-over-oram architecture. IACR Cryptology ePrint Archive, 2014:345 (2014)
16.
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). doi:10.​1007/​978-3-642-55220-5_​23 CrossRef
17.
Goldreich, O.: Towards a theory of software protection and simulation by oblivious RAMs. In: STOC, pp. 182–194 (1987)
18.
Goldreich, O.: Foundations of Cryptography: Volume 2, Basic Applications. Cambridge University Press, New York (2004)CrossRefMATH
19.
Goldreich, O., Micali, S., Wigderson, A.: How to play any mental game or a completeness theorem for protocols with honest majority. In: STOC, pp. 218–229 (1987)
20.
21.
Goodrich, M.T., Mitzenmacher, M., Ohrimenko, O., Tamassia, R.: Privacy-preserving group data access via stateless oblivious RAM simulation. In: SODA, pp. 157–167 (2012)
22.
Gordon, S.D., Katz, J., Kolesnikov, V., Krell, F., Malkin, T., Raykova, M., Vahlis, Y.: Secure two-party computation in sublinear (amortized) time. In: CCS, pp. 513–524 (2012)
23.
Hu, Z., Mohassel, P., Rosulek, M.: Efficient zero-knowledge proofs of non-algebraic statements with sublinear amortized cost. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9216, pp. 150–169. Springer, Heidelberg (2015). doi:10.​1007/​978-3-662-48000-7_​8 CrossRef
24.
Ishai, Y., Kushilevitz, E., Ostrovsky, R., Prabhakaran, M., Sahai, A.: Efficient non-interactive secure computation. In: Paterson, K.G. (ed.) EUROCRYPT 2011. LNCS, vol. 6632, pp. 406–425. Springer, Heidelberg (2011). doi:10.​1007/​978-3-642-20465-4_​23 CrossRef
25.
26.
27.
28.
Keller, M., Scholl, P.: Efficient, oblivious data structures for MPC. In: Sarkar, P., Iwata, T. (eds.) ASIACRYPT 2014, Part II. LNCS, vol. 8874, pp. 506–525. Springer, Heidelberg (2014). doi:10.​1007/​978-3-662-45608-8_​27
29.
Kushilevitz, E., Lu, S., Ostrovsky, R.: On the (in)security of hash-based oblivious RAM and a new balancing scheme. In: SODA, pp. 143–156 (2012)
30.
Lindell, Y.: Fast cut-and-choose based protocols for malicious and covert adversaries. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013, Part II. LNCS, vol. 8043, pp. 1–17. Springer, Heidelberg (2013). doi:10.​1007/​978-3-642-40084-1_​1 CrossRef
31.
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). doi:10.​1007/​978-3-540-72540-4_​4 CrossRef
32.
33.
Liu, C., Huang, Y., Shi, E., Katz, J., Hicks, M.W.: Automating efficient ram-model secure computation. In: IEEE Symposium on Security and Privacy, pp. 623–638 (2014)
34.
35.
Miao, P.: Cut-and-choose for garbled RAM. Cut-and-Choose for Garbled RAM IACR Cryptology ePrint Archive 2016:907 (2016)
36.
Micali, S., Rogaway, P.: Secure computation. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 392–404. Springer, Heidelberg (1992)
37.
38.
Ostrovsky, R.: Efficient computation on oblivious RAMs. In: STOC, pp. 514–523 (1990)
39.
40.
41.
Ren, L., Fletcher, C.W., Kwon, A., Stefanov, E., Shi, E., van Dijk, M., Devadas, S.: Constants count: practical improvements to oblivious RAM. In: USENIX, pp. 415–430 (2015)
42.
Shi, E., Chan, T.-H.H., Stefanov, E., Li, M.: Oblivious RAM with O((logN)\(^{3}\)) worst-case cost. In: Lee, D.H., Wang, X. (eds.) ASIACRYPT 2011. LNCS, vol. 7073, pp. 197–214. Springer, Heidelberg (2011). doi:10.​1007/​978-3-642-25385-0_​11 CrossRef
43.
Stefanov, E., van Dijk, M., Shi, E., Fletcher, C.W., Ren, L., Xiangyao, Y., Devadas, S.: Path ORAM: an extremely simple oblivious RAM protocol. In: CCS, pp. 299–310 (2013)
44.
Wang, X., Hubert Chan, T.-H., Shi, E.: Circuit ORAM: on tightness of the Goldreich-Ostrovsky lower bound. In: CCS, pp. 850–861 (2015)
45.
Wang, X.S., Huang, Y., Hubert Chan, T.-H., Shelat, A., Shi, E.: SCORAM: oblivious RAM for secure computation. In: CCS, pp. 191–202 (2014)
46.
Williams, P., Sion, R.: Single round access privacy on outsourced storage. In: CCS, pp. 293–304 (2012)
47.
Yao, A.C.: Protocols for secure computations (extended abstract). In: FOCS, pp. 160–164 (1982)
48.
Yao, A.C.: How to generate and exchange secrets (extended abstract). In: FOCS, pp. 162–167 (1986)
Metadata
Title
Constant-Round Maliciously Secure Two-Party Computation in the RAM Model
Authors
Carmit Hazay
Avishay Yanai
Copyright Year
2016
Publisher
Springer Berlin Heidelberg
Book
Theory of Cryptography

Print ISBN: 978-3-662-53640-7

Electronic ISBN: 978-3-662-53641-4

Copyright Year: 2016

DOI
https://doi.org/10.1007/978-3-662-53641-4_20

Premium Partner

    Image Credits