Skip to main content

2018 | OriginalPaper | Buchkapitel

Efficient Maliciously Secure Multiparty Computation for RAM

verfasst von : Marcel Keller, Avishay Yanai

Erschienen in: Advances in Cryptology – EUROCRYPT 2018

Verlag: Springer International Publishing

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

search-config
loading …

Abstract

A crucial issue, that mostly affects the performance of actively secure computation of RAM programs, is the task of reading/writing from/to memory in a private and authenticated manner. Previous works in the active security and multiparty settings are based purely on the SPDZ (reactive) protocol, hence, memory accesses are treated just like any input to the computation. However, a garbled-circuit-based construction (such as BMR), which benefits from a lower round complexity, must resolve the issue of converting memory data bits to their corresponding wire keys and vice versa.
In this work we propose three techniques to construct a secure memory access, each appropriates to a different level of abstraction of the underlying garbling functionality. We provide a comparison between the techniques by several metrics. To the best of our knowledge, we are the first to construct, prove and implement a concretely efficient garbled-circuit-based actively secure RAM computation with dishonest majority.
Our construction is based on our third (most efficient) technique, cleverly utilizing the underlying SPDZ authenticated shares (Damgård et al., Crypto 2012), yields lean circuits and a constant number of communication rounds per physical memory access. Specifically, it requires no additional circuitry on top of the ORAM’s, incurs only two rounds of broadcasts between every two memory accesses and has a multiplicative overhead of 2 on top of the ORAM’s storage size.
Our protocol outperforms the state of the art in this settings when deployed over WAN. Even when simulating a very conservative RTT of 100 ms our protocol is at least one order of magnitude faster than the current state of the art protocol of Keller and Scholl (Asiacrypt 2015).

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!

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!

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!

Anhänge
Nur mit Berechtigung zugänglich
Fußnoten
1
The decrease in throughput reflects the runtime overhead implied by the ORAM, as mentioned above, this overhead depends on the memory size N.
 
2
The amount of memory being accessed to satisfy a CPU instruction depends on the instruction itself, for instance a SIMD instruction access more data than a SISD instruction.
 
3
The state-of-the-art construction of an AES circuits incurs only 5200 AND gates.
 
4
Encoding the state as wire labels is simpler than encoding the memory since it only requires matching wire labels of output wires of one CPU-step to the input wires of the next. This can be done in the offline phase, without knowing the program or the input.
 
5
Remember that \(x^i\) denotes the share of party \(p_i\) and not an exponentiation operation.
 
6
Note that \(\mathsf {access}_1\) is the output to all parties, not only the adversary’s, however, for the simulation purpose we use this as the adversary’s output.
 
7
They require only a simple XOR operation.
 
8
Loading time depends on the implementation, i.e. whether using dereferences or not.
 
9
Using the AES-NI instruction set from Intel’s Sandy Bridge microarchitecture and on, a RoundKey instruction takes a single CPU cycle and latency of 8, that is, one could reach a throughput of up to 8 RoundKey operations with the same key at the same CPU cycle [21, Chap. 5.10].
 
10
“Oblivious array” is the name given in [24] to the basic oblivious random memory access, which allows reading and writing with a secret index. This is in distinction to “oblivious dictionary” that allows reading according to a secret ‘key’ in a key-value (dictionary) data structure, where the key may be larger than the size of the memory.
 
11
As defined in [36, A.2] under ORAM metrics.
 
Literatur
2.
Zurück zum Zitat Ben-Efraim, A., Lindell, Y., Omri, E.: Optimizing semi-honest secure multiparty computation for the internet, pp. 578–590 (2016) Ben-Efraim, A., Lindell, Y., Omri, E.: Optimizing semi-honest secure multiparty computation for the internet, pp. 578–590 (2016)
5.
Zurück zum Zitat Boyle, E., Gilboa, N., Ishai, Y.: Function secret sharing: improvements and extensions, pp. 1292–1303 (2016) Boyle, E., Gilboa, N., Ishai, Y.: Function secret sharing: improvements and extensions, pp. 1292–1303 (2016)
7.
Zurück zum Zitat Canetti, R., Holmgren, J.: Fully succinct garbled RAM, pp. 169–178 (2016) Canetti, R., Holmgren, J.: Fully succinct garbled RAM, pp. 169–178 (2016)
9.
Zurück zum Zitat Doerner, J., Shelat, A.: Scaling ORAM for secure computation. In: CCS (2017) Doerner, J., Shelat, A.: Scaling ORAM for secure computation. In: CCS (2017)
10.
12.
Zurück zum Zitat Garg, S., Lu, S., Ostrovsky, R.: Black-box garbled RAM, pp. 210–229 (2015) Garg, S., Lu, S., Ostrovsky, R.: Black-box garbled RAM, pp. 210–229 (2015)
13.
Zurück zum Zitat Garg, S., Lu, S., Ostrovsky, R., Scafuro, A.: Garbled RAM from one-way functions, pp. 449–458 (2015) Garg, S., Lu, S., Ostrovsky, R., Scafuro, A.: Garbled RAM from one-way functions, pp. 449–458 (2015)
15.
Zurück zum Zitat Goldreich, O.: Foundations of Cryptography: Basic Applications, vol. 2. Cambridge University Press, New York (2004)CrossRefMATH Goldreich, O.: Foundations of Cryptography: Basic Applications, vol. 2. Cambridge University Press, New York (2004)CrossRefMATH
16.
Zurück zum Zitat 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) 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)
17.
18.
Zurück zum Zitat Gordon, S.D., Katz, J., Kolesnikov, V., Krell, F., Malkin, T., Raykova, M., Vahlis, Y.: Secure two-party computation in sublinear (amortized) time, pp. 513–524 (2012) Gordon, S.D., Katz, J., Kolesnikov, V., Krell, F., Malkin, T., Raykova, M., Vahlis, Y.: Secure two-party computation in sublinear (amortized) time, pp. 513–524 (2012)
23.
Zurück zum Zitat Keller, M., Orsini, E., Scholl, P.: MASCOT: faster malicious arithmetic secure computation with oblivious transfer, pp. 830–842 (2016) Keller, M., Orsini, E., Scholl, P.: MASCOT: faster malicious arithmetic secure computation with oblivious transfer, pp. 830–842 (2016)
26.
Zurück zum Zitat Lindell, Y., Riva, B.: Blazing fast 2PC in the offline/online setting with security for malicious adversaries. In: CCS, pp. 579–590 (2015) Lindell, Y., Riva, B.: Blazing fast 2PC in the offline/online setting with security for malicious adversaries. In: CCS, pp. 579–590 (2015)
28.
Zurück zum Zitat Liu, C., Huang, Y., Shi, E., Katz, J., Hicks, M.W.: Automating efficient RAM-model secure computation, pp. 623–638 (2014) Liu, C., Huang, Y., Shi, E., Katz, J., Hicks, M.W.: Automating efficient RAM-model secure computation, pp. 623–638 (2014)
29.
Zurück zum Zitat Liu, C., Wang, X.S., Nayak, K., Huang, Y., Shi, E.: ObliVM: a programming framework for secure computation, pp. 359–376 (2015) Liu, C., Wang, X.S., Nayak, K., Huang, Y., Shi, E.: ObliVM: a programming framework for secure computation, pp. 359–376 (2015)
33.
Zurück zum Zitat Ostrovsky, R., Shoup, V.: Private information storage (extended abstract), pp. 294–303 (1997) Ostrovsky, R., Shoup, V.: Private information storage (extended abstract), pp. 294–303 (1997)
35.
Zurück zum Zitat Stefanov, E., van Dijk, M., Shi, E., Fletcher, C.W., Ren, L., Yu, X., Devadas, S.: Path ORAM: an extremely simple oblivious RAM protocol, pp. 299–310 (2013) Stefanov, E., van Dijk, M., Shi, E., Fletcher, C.W., Ren, L., Yu, X., Devadas, S.: Path ORAM: an extremely simple oblivious RAM protocol, pp. 299–310 (2013)
36.
Zurück zum Zitat Wang, X., Chan, T.-H.H., Shi, E.: Circuit ORAM: On tightness of the Goldreich-Ostrovsky lower bound, pp. 850–861 (2015) Wang, X., Chan, T.-H.H., Shi, E.: Circuit ORAM: On tightness of the Goldreich-Ostrovsky lower bound, pp. 850–861 (2015)
38.
Zurück zum Zitat Wang, X., Ranellucci, S., Katz, J.: Authenticated garbling and efficient maliciously secure two-party computation. In: CCS, pp. 21–37 (2017) Wang, X., Ranellucci, S., Katz, J.: Authenticated garbling and efficient maliciously secure two-party computation. In: CCS, pp. 21–37 (2017)
40.
Zurück zum Zitat Yao, A.C.-C.: How to generate and exchange secrets (extended abstract). In: FOCS, pp. 162–167 (1986) Yao, A.C.-C.: How to generate and exchange secrets (extended abstract). In: FOCS, pp. 162–167 (1986)
Metadaten
Titel
Efficient Maliciously Secure Multiparty Computation for RAM
verfasst von
Marcel Keller
Avishay Yanai
Copyright-Jahr
2018
DOI
https://doi.org/10.1007/978-3-319-78372-7_4