nach oben

Journal of Cryptology

Erschienen in:

11.12.2017

Fast Garbling of Circuits Under Standard Assumptions

verfasst von: Shay Gueron, Yehuda Lindell, Ariel Nof, Benny Pinkas

Erschienen in: Journal of Cryptology | Ausgabe 3/2018

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

Protocols for secure computation enable mutually distrustful parties to jointly compute on their private inputs without revealing anything, but the result. Over recent years, secure computation has become practical and considerable effort has been made to make it more and more efficient. A highly important tool in the design of two-party protocols is Yao’s garbled circuit construction (Yao 1986), and multiple optimizations on this primitive have led to performance improvements in orders of magnitude over the last years. However, many of these improvements come at the price of making very strong assumptions on the underlying cryptographic primitives being used (e.g., that AES is secure for related keys, that it is circular-secure, and even that it behaves like a random permutation when keyed with a public fixed key). The justification behind making these strong assumptions has been that otherwise it is not possible to achieve fast garbling and thus fast secure computation. In this paper, we take a step back and examine whether it is really the case that such strong assumptions are needed. We provide new methods for garbling that are secure solely under the assumption that the primitive used (e.g., AES) is a pseudorandom function. Our results show that in many cases, the penalty incurred is not significant, and so a more conservative approach to the assumptions being used can be adopted.

Vorheriger Artikel Asymptotically Efficient Lattice-Based Digital Signatures

Nächster Artikel Key-Recovery Attacks on ASASA

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

We do not count the base OTs of the OT extension since these would outweigh everything else, and can anyway be precomputed. Our aim here is to see the effect of the change in the garbled circuits and our tests are under optimal conditions for JustGarble-type constructions [5]. For the same reason, we do not look at the effect inside protocols for malicious adversaries since all of the other work will clearly outweigh any additional costs in garbling. We remark that the OT extension of [2] requires assuming a correlation-robust hash function. This is arguably a less problematic assumption than related-key security for block ciphers and also is an orthogonal issue to the assumptions needed for garbling.

Concretely, on a Haswell processor, 8 pipelined AES computations cost approximately 77 cycles, whereas one non-pipelined AES computation costs approximately 70 cycles.

Haswell (resp., Broadwell) is an Intel Architecture Codename of a recently announced 4th (resp., 5th) Generation Intel^® Core^TM Processor. For short, we refer to them simply as Haswell (resp., Broadwell).

AESENCLAST is used since the last round of AES does not include the MixColumns operation, which is a part of all other rounds and therefore run in the AESENC instruction, but not in AESENCLAST.

We note that garbling with hash functions is much slower than with AES, especially when an AES-NI supporting architecture is utilized. Thus, related-key security for AES is required, which is a less than ideal assumption.

It may be tempting to propose that one of \(k_i^0,k_i^1\) will also remain the same; i.e., set \(\tilde{k}_i^{\pi _i} = k_i^{\pi _i}\) and \(\tilde{k}_i^{\bar{\pi }_i} = F_{k_i^{\bar{\pi }_i}}(g)\). However, in this case, if the evaluator happens to have \( k_i^{\bar{\pi }_i}\) and \( k_j^{\bar{\pi }_j}\), then it can compute \(T \oplus F_{k_i^{\bar{\pi }_i}}(g) \oplus F_{k_j^{\bar{\pi }_j}}(g)\). Note that \(T = F_{k_j^{\bar{\pi }_j}}(g) \oplus \tilde{k}_j^{\bar{\pi }_j} = F_{k_j^{\bar{\pi }_j}}(g) \oplus \tilde{k}_j^{\pi _j} \oplus \Delta _\ell = F_{k_j^{\bar{\pi }_j}}(g) \oplus \tilde{k}_j^{\pi _j} \oplus k_i^{\pi _i} \oplus F_{k_i^{\bar{\pi }_i}}(g)\) and so the result obtained by the evaluator is \(\tilde{k}_j^{\pi _j} \oplus k_i^{\pi _i}=\tilde{k}_j^{\pi _j} \oplus \tilde{k}_i^{\pi _i}\). If these keys are used in other gates, then an attacker sees the XOR of two keys and encryptions computed with each key separately. This is once again a related-key type assumption.

Recall that in the reduction the adversary \(\mathcal{A}_i\) knows the input x. However, in the experiment in the proof of obliviousness, \(\mathcal{A}\) also outputs x and so it is known. Thus, the same reduction works.

This is the real difference between the fleXOR approach and our standard assumption-based scheme: our scheme is not flexible; all XOR gates are garbled in the same way such that for each wire there will be an independent new offset that is set pseudorandomly when garbling each gate, and not in advance as in the fleXOR approach. As a result, our scheme requires 4 (or 3) encryptions even though only one ciphertext is required.

We remark that the proof of Kolesnikov et al. [14] that the problem of finding an optimal monotone ordering is NP-hard does not go through for monotone and safe. We do not know if the problem of finding an optimal safe and monotone ordering is NP-hard.

Note that taking \(\phi _i^{max}\) at every gate does not guarantee at most 1 ciphertext per XOR gate.

Circuits of Basic Functions Suitable For MPC and FHE. http://www.cs.bris.ac.uk/Research/CryptographySecurity/MPC. Accessed April 2015

G. Asharov, Y. Lindell, T. Schneier, M. Zohner, More efficient oblivious transfer and extensions for faster secure computation, in the 20th ACM Conference on Computer and Communications Security (ACM CCS). (2013), pp. 535–548

M. Bellare, V.T. Hoang, P. Rogaway. Foundations of garbled circuits, in the 19th ACM Conference on Computer and Communications Security (ACM CCS). (2012), pp. 784–796

J. Black. The ideal-cipher model, revisited: an uninstantiable blockcipher-based hash function, in FSE 2006. LNCS, vol. 4047 (Springer, Berlin, 2006), pp. 328–340

M. Bellare, V.T. Hoang, S. Keelveedhi, P. Rogaway. Efficient garbling from a fixed-key blockcipher, in the IEEE Symposium on Security and Privacy 2013 (2013), pp. 478–492

A. Biryukov, D. Khovratovich, I. Nikolic. Distinguisher and related-key attack on the full AES-256, in CRYPTO 2009, LNCS, vol. 5677 (Springer, Berlin, 2009), pp. 231–249

S.G. Choi, J. Katz, R. Kumaresan, H. Zhou. On the security of the “Free-XOR” technique, in the 9th TCC, LNCS, vol. 7194 (Springer, Berlin, 2012), pp. 39–53

S. Gueron. Intel Advanced Encryption Standard (AES) Instructions Set, Rev 3.01 (2012). https://software.intel.com/en-us/articles/intel-advanced-encryption-standard-aes-instructions-set

S. Gueron. Intel’s new AES instructions for enhanced performance and security, in the 16th FSE (FSE 2009). LNCS, vol. 5665 (Springer, Berlin, 2009), pp. 51–66

10.

S. Gueron. Optimized implementation of AES 128/192/256 key expansion (2015). Software patch in https://bugzilla.mozilla.org/show_bug.cgi?id=1122903

11.

Y. Huang, D. Evans, J. Katz, L. Malka, Faster secure two-party computation using garbled circuits, in the 20th USENIX Security Symposium, 2011

12.

Y. Ishai, J. Kilian, K. Nissim, E. Petrank, Extending oblivious transfer efficiently, in CRYPTO 2003, LNCS vol. 2729 (Springer, Berlin, 2003), pp. 145–161

13.

L.R. Knudsen, V. Rijmen, Known-key distinguishers for some block ciphers, in ASIACRYPT 2007. LNCS, vol. 4833 (Springer, Berlin, 2007), pp. 315–324

14.

V. Kolesnikov, P. Mohassel, M. Rosulek. FleXOR: flexible garbling for XOR gates that beats free-XOR, in CRYPTO 2014. LNCS, vol. 8617 (Springer, Berlin, 2014), pp. 440–457

15.

V. Kolesnikov, T. Schneider, Improved garbled circuit: free XOR gates and applications, in the 35th ICALP. LNCS, vol. 5126 (Springer, Berlin, 2008), pp. 486–498

16.

V. Kolesnikov, T. Schneider, Secure function evaluation techniques for circuits containing XOR gates with applications to universal circuits. Patent No. US 8,443,205 B2 (2013)

17.

B. Kreuter, A. Shelat, C. Shen, Billion-gate secure computation with malicious adversaries, in the 21st USENIX Security Symposium (2012)

18.

Y. Lindell, B. Pinkas, A proof of Yao’s protocol for secure two-party computation. J. Cryptol. 22(2), 161–188 (2009)CrossRefMATH

19.

Y. Lindell, B. Pinkas, N. Smart. Implementing two-party computation efficiently with security against malicious adversaries, in the 6th Conference on Security and Cryptography for Networks. LNCS, vol. 5229 (Springer, Berlin, 2008), pp. 2–20

20.

M. Naor, B. Pinkas, R. Sumner. Privacy preserving auctions and mechanism design, in the ACM Conference on Electronic Commerce. (1999), pp. 129–139

21.

B. Pinkas, T. Schneider, N.P. Smart, S.C. Williams. Secure two-party computation is practical, in ASIACRYPT 2009. LNCS, vol. 5912 (Springer, Berlin 2009), pp. 250–267

22.

A. Yao. How to generate and exchange secrets, in the 27th FOCS, 1986. pp. 162–167

23.

S. Zahur, M. Rosulek, D. Evans. Two halves make a whole—reducing data transfer in garbled circuits using half gates, in EUROCRYPT 2015. LNCS, vol. 9057 (Springer, Berlin, 2015), pp. 220–250

Titel: Fast Garbling of Circuits Under Standard Assumptions
verfasst von: Shay Gueron
Yehuda Lindell
Ariel Nof
Benny Pinkas
Publikationsdatum: 11.12.2017
Verlag: Springer US
Erschienen in: Journal of Cryptology / Ausgabe 3/2018
Print ISSN: 0933-2790
Elektronische ISSN: 1432-1378
DOI: https://doi.org/10.1007/s00145-017-9271-y

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"

Weitere Artikel der Ausgabe 3/2018

On the Feasibility of Extending Oblivious Transfer

Stream Ciphers: A Practical Solution for Efficient Homomorphic-Ciphertext Compression

On Constructing One-Way Permutations from Indistinguishability Obfuscation

Completeness for Symmetric Two-Party Functionalities: Revisited

Asymptotically Efficient Lattice-Based Digital Signatures

Efficient Slide Attacks

Premium Partner