nach oben

Erschienen in:

2023 | OriginalPaper | Buchkapitel

3-Party Secure Computation for RAMs: Optimal and Concretely Efficient

verfasst von : Atsunori Ichikawa, Ilan Komargodski, Koki Hamada, Ryo Kikuchi, Dai Ikarashi

Erschienen in: Theory of Cryptography

Verlag: Springer Nature Switzerland

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

A distributed oblivious RAM (DORAM) is a method for accessing a secret-shared memory while hiding the accessed locations. DORAMs are the key tool for secure multiparty computation (MPC) for RAM programs that avoids expensive RAM-to-circuit transformations.

We present new and improved 3-party DORAM protocols. For a logical memory of size N and for each logical operation, our DORAM requires \(O(\log N)\) local CPU computation steps. This is known to be asymptotically optimal. Our DORAM satisfies passive security in the honest majority setting. Our technique results with concretely-efficient protocols and does not use expensive cryptography (such as re-randomizable or homomorphic encryption). Specifically, our DORAM is 25X faster than the known most efficient DORAM in the same setting.

Lastly, we extend our technique to handle malicious attackers at the expense of using slightly larger blocks (i.e., \(\omega ((\lambda + b)\log N)\) vs. \(\lambda +b\) where \(b=\varOmega (\log N)\) is original block size). To the best of our knowledge, this is the first concretely-efficient maliciously secure DORAM.

Technically, our construction relies on a novel concretely-efficient 3-party oblivious permutation protocol. We combine it with efficient non-oblivious hashing techniques (i.e., Cuckoo hashing) to get a distributed oblivious hash table. From this, we build a full-fledged DORAM using a distributed variant of the hierarchical approach of Goldreich and Ostrovsky (J. ACM ’96). These ideas, and especially the permutation protocol, are of independent interest.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

Vorheriges Kapitel DORAM Revisited: Maliciously Secure RAM-MPC with Logarithmic Overhead

We model parties as RAM machines that can perform word-level addition and standard Boolean operations at unit cost.

As commonly done, we sometimes settle for overhead in an amortized sense, that is, we measure the average overhead over a sequence of requests. Known schemes can be made worst-case (“de-amortized”) [5, 36].

The protocol of Lu and Ostrovsky [33] is in the multi-party setting where there are two non-communicating servers and a single trusted lightweight client (see full version for details). Faber et al. [16] observed that the client in [33]’s scheme can be efficiently simulated by an MPC.

Here, we emphasize again that the DORAM of Falk et al. [19] requires \(O(\log ^2 N)\) computational cost in addition to the communication cost. We only have \(O(\log N)\) computational cost.

The metadata associated with each data blocks is used to avoid the stash-resampling attack of [18], same as was done in [3, 4, 18].

Note that if \(p\le \log \log N\), the obtained PRF key is single, \([\![s_p]\!] \).

Albrecht, M.R., Rechberger, C., Schneider, T., Tiessen, T., Zohner, M.: Ciphers for MPC and FHE. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9056, pp. 430–454. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46800-5_17CrossRef

Araki, T., Furukawa, J., Lindell, Y., Nof, A., Ohara, K.: High-throughput semi-honest secure three-party computation with an honest majority. In: CCS, pp. 805–817 (2016)

Asharov, G., Komargodski, I., Lin, W., Nayak, K., Peserico, E., Shi, E.: Optorama: optimal oblivious RAM. J. ACM 70(1), 4:1–4:70 (2023)

Asharov, G., Komargodski, I., Lin, W., Peserico, E., Shi, E.: Optimal oblivious parallel RAM. In: ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 2459–2521 (2022)

Asharov, G., Komargodski, I., Lin, W.-K., Shi, E.: Oblivious RAM with worst-case logarithmic overhead. In: Malkin, T., Peikert, C. (eds.) CRYPTO 2021. LNCS, vol. 12828, pp. 610–640. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-84259-8_21CrossRef

Bunn, P., Katz, J., Kushilevitz, E., Ostrovsky, R.: Efficient 3-party distributed ORAM. Cryptology ePrint Archive (2018)

Canetti, R.: Security and composition of multiparty cryptographic protocols. J. Cryptology 13(1), 143–202 (2000)MathSciNetCrossRefMATH

Catrina, O., de Hoogh, S.: Improved primitives for secure multiparty integer computation. In: Garay, J.A., De Prisco, R. (eds.) SCN, pp. 182–199 (2010)

Chan, T.H., Shi, E.: Circuit OPRAM: unifying statistically and computationally secure ORAMs and OPRAMs. In: TCC, pp. 72–107 (2017)

10.

Chida, K., et al.: Fast large-scale honest-majority MPC for malicious adversaries. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018. LNCS, vol. 10993, pp. 34–64. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-96878-0_2CrossRef

11.

Chida, K., Hamada, K., Ikarashi, D., Kikuchi, R., Kiribuchi, N., Pinkas, B.: An efficient secure three-party sorting protocol with an honest majority. Cryptology ePrint Archive (2019)

12.

Chida, K., Hamada, K., Ikarashi, D., Kikuchi, R., Pinkas, B.: High-throughput secure AES computation. In: WAHC, pp. 13–24 (2018)

13.

Cramer, R., Damgård, I., Ishai, Y.: Share conversion, pseudorandom secret-sharing and applications to secure computation. In: TCC, pp. 342–362 (2005)

14.

Damgård, I., Keller, M.: Secure multiparty AES. In: FC, pp. 367–374 (2010)

15.

Doerner, J., Shelat, A.: Scaling ORAM for secure computation. In: CCS, pp. 523–535 (2017)

16.

Faber, S., Jarecki, S., Kentros, S., Wei, B.: Three-party ORAM for secure computation. In: Iwata, T., Cheon, J.H. (eds.) ASIACRYPT 2015. LNCS, vol. 9452, pp. 360–385. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-48797-6_16CrossRef

17.

Falk, B., Noble, D., Ostrovsky, R., Shtepel, M., Zhang, J.: DORAM revisited: maliciously secure RAM-MPC with logarithmic overhead. IACR Cryptology ePrint Archive, p. 578 (2023)

18.

Hemenway Falk, B., Noble, D., Ostrovsky, R.: Alibi: a flaw in cuckoo-hashing based hierarchical ORAM schemes and a solution. In: Canteaut, A., Standaert, F.-X. (eds.) EUROCRYPT 2021. LNCS, vol. 12698, pp. 338–369. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-77883-5_12CrossRefMATH

19.

Falk, B.H., Noble, D., Ostrovsky, R.: 3-party distributed ORAM from oblivious set membership. In: SCN, pp. 437–461 (2022)

20.

Furukawa, J., Lindell, Y., Nof, A., Weinstein, O.: High-throughput secure three-party computation for malicious adversaries and an honest majority. In: Coron, J.-S., Nielsen, J.B. (eds.) EUROCRYPT 2017. LNCS, vol. 10211, pp. 225–255. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-56614-6_8CrossRef

21.

Genkin, D., Ishai, Y., Polychroniadou, A.: Efficient multi-party computation: from passive to active security via secure SIMD circuits. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9216, pp. 721–741. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-48000-7_35CrossRef

22.

Genkin, D., Ishai, Y., Prabhakaran, M.M., Sahai, A., Tromer, E.: Circuits resilient to additive attacks with applications to secure computation. In: STOC, pp. 495–504 (2014)

23.

Goldreich, O.: Towards a theory of software protection and simulation by oblivious rams. In: STOC, pp. 182–194 (1987)

24.

Goldreich, O., Ostrovsky, R.: Software protection and simulation on oblivious rams. J. ACM 43(3), 431–473 (1996)MathSciNetCrossRefMATH

25.

Goodrich, M.T., Mitzenmacher, M.: Privacy-preserving access of outsourced data via oblivious ram simulation. In: ICALP, pp. 576–587 (2011)

26.

Ichikawa, A., Komargodski, I., Hamada, K., Kikuchi, R., Ikarashi, D.: 3-party secure computation for rams: optimal and concretely efficient. IACR Cryptology ePrint Archive, p. 516 (2023)

27.

Ikarashi, D., Kikuchi, R., Hamada, K., Chida, K.: Actively private and correct MPC scheme in \(t<n/2\) from passively secure schemes with small overhead. Cryptology ePrint Archive (2014)

28.

Ito, M., Saito, A., Nishizeki, T.: Secret sharing scheme realizing general access structure. In: GLOBECOM, pp. 99–102 (1987)

29.

Kikuchi, R., et al.: Field extension in secret-shared form and its applications to efficient secure computation. In: ACISP, pp. 343–361 (2019)

30.

Kirsch, A., Mitzenmacher, M., Wieder, U.: More robust hashing: cuckoo hashing with a stash. J. Computing 39(4), 1543–1561 (2009)MathSciNetMATH

31.

Laur, S., Talviste, R., Willemson, J.: From oblivious AES to efficient and secure database join in the multiparty setting. In: ACNS, pp. 84–101 (2013)

32.

Laur, S., Willemson, J., Zhang, B.: Round-efficient oblivious database manipulation. In: ISC, pp. 262–277 (2011)

33.

Lu, S., Ostrovsky, R.: Distributed oblivious ram for secure two-party computation. In: TCC, pp. 377–396 (2013). https://eprint.iacr.org/2011/384

34.

Noble, D.: Explicit, closed-form, general bounds for cuckoo hashing with a stash. Cryptology ePrint Archive (2021)

35.

Ostrovsky, R.: Efficient computation on oblivious rams. In: STOC, pp. 514–523 (1990)

36.

Ostrovsky, R., Shoup, V.: Private information storage (extended abstract). In: STOC, pp. 294–303 (1997)

37.

Pagh, R., Rodler, F.F.: Cuckoo hashing. J. Algorithms 51(2), 122–144 (2004)MathSciNetCrossRefMATH

38.

Pippenger, N., Fischer, M.J.: Relations among complexity measures. J. ACM 26(2), 361–381 (1979)MathSciNetCrossRefMATH

39.

Shamir, A.: How to share a secret. Commun. ACM 22(11), 612–613 (1979)MathSciNetCrossRefMATH

40.

Wang, X., Chan, T.H., Shi, E.: Circuit ORAM: on tightness of the goldreich-ostrovsky lower bound. In: CCS, pp. 850–861 (2015)

Titel: 3-Party Secure Computation for RAMs: Optimal and Concretely Efficient
verfasst von: Atsunori Ichikawa
Ilan Komargodski
Koki Hamada
Ryo Kikuchi
Dai Ikarashi
Verlag: Springer Nature Switzerland
Buch: Theory of Cryptography
Print ISBN: 978-3-031-48614-2

Electronic ISBN: 978-3-031-48615-9

Copyright-Jahr: 2023
DOI: https://doi.org/10.1007/978-3-031-48615-9_17

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner