nach oben

Journal of Cryptology

Erschienen in:

01.07.2016

Garbling XOR Gates “For Free” in the Standard Model

verfasst von: Benny Applebaum

Erschienen in: Journal of Cryptology | Ausgabe 3/2016

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

Yao’s garbled circuit (GC) technique is a powerful cryptographic tool which allows to “encrypt” a circuit \(C\) by another circuit \({\hat{C}}\) in a way that hides all information except for the final output. Yao’s original construction incurs a constant overhead in both computation and communication per gate of the circuit \(C\) (proportional to the complexity of symmetric encryption). Kolesnikov and Schneider (ICALP 2008) introduced an optimized variant that garbles XOR gates “for free” in a way that involves no cryptographic operations and no communication. This variant has become very popular and has lead to notable performance improvements. The security of the free-XOR optimization was originally proved in the random oracle model. Despite some partial progress (Choi et al., TCC 2012), the question of replacing the random oracle with a standard cryptographic assumption has remained open. We resolve this question by showing that the free-XOR approach can be realized in the standard model under the learning parity with noise (LPN) assumption. Our result is obtained in two steps:

We show that the random oracle can be replaced with a symmetric encryption, which remains secure under a combined form of related-key (RK) and key-dependent message (KDM) attacks.

We show that such a symmetric encryption can be constructed based on the LPN assumption.

As an additional contribution, we prove that the combination of RK and KDM security is nontrivial in the following sense: There exists an encryption scheme which achieves RK security and KDM security separately, but breaks completely at the presence of combined RK-KDM attacks.

Vorheriger Artikel Leakage-Resilient Cryptography from Minimal Assumptions

Nächster Artikel A Dichotomy for Local Small-Bias Generators

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

Nur mit Berechtigung zugänglich

A seemingly weaker definition of LIN RK-KDM security restricts the KDM family to functions \(g_{M,\sigma }:s\mapsto (M+ (\sigma \cdot s))\) where \(M\) and \(s\) are of the same length \(k\). We note that a scheme that satisfies this notion can be trivially converted into a scheme that satisfies our definition (which supports \(M\) longer than \(s\)). This can be done by partitioning the long message \(M\) into \(t\) blocks \(M_1,\ldots ,M_t\) of length \(k\) each and concatenating the encryptions of these blocks. A query of the form \((f\in \Phi _{\mathsf {RKA}},g_{M,\sigma })\) can then be emulated by a linear query \((f\in \Phi _{\mathsf {RKA}},g_{M_1,1})\) and \(t-1\) fixed-message query \((f\in \Phi _{\mathsf {RKA}},g_{M_i,0})\).

This asymptotically fast implementation is based on efficient noise sampling algorithm, fast error correcting code (e.g., Spielman’s codes [43]), and fast rectangular matrix multiplication. The latter requires \(N,\ell >k^6\).

The decryption \(\mathsf {RD}\) may err with negligible probability due to the possibility that some message \(M\), whose prefix does not equal to the key \(S\), will be mapped to a ciphertext \(\mathsf {PE}_S(M)\) whose prefix equals to the key. This can be handled in several ways, e.g., by modifying the encryption algorithm so that such event never happens. We prefer the current version (with negligible error probability) for simplicity.

B. Applebaum, Randomly encoding functions: A new cryptographic paradigm (invited talk), in ICITS, pp. 25–31 (2011)

B. Applebaum, D. Cash, C. Peikert, A. Sahai, Fast cryptographic primitives and circular-secure encryption based on hard learning problems, in Advances in Cryptology—CRYPTO 2009, pp. 595–618 (2009)

B. Applebaum, D. Harnik, Y. Ishai, Semantic security under related-key attacks and applications, in ICS, pp. 45–60 (2011)

B. Applebaum, Y. Ishai, E. Kushilevitz, Computationally private randomizing polynomials and their applications. Comput. Complex. 15(2), 115–162 (2006)

B. Applebaum, Y. Ishai, E. Kushilevitz, How to garble arithmetic circuits, in Proc. 52nd FOCS, pp. 120–129 (2011)

M. Bellare, D. Cash, Pseudorandom functions and permutations provably secure against related-key attacks, in Advances in Cryptology—CRYPTO 2010, pp. 666–684 (2010)

M. Bellare, V.T. Hoang, P. Rogaway, Foundations of garbled circuits, in CCS ’12, pp. 784–796 (2012)

M. Bellare, T. Kohno, A theoretical treatment of related-key attacks: RKA-PRPs, RKA-PRFs, and applications, in Advances in Cryptology—EUROCRYPT 2003, pp. 491–506 (2003)

M. Bellare, P. Rogaway, Random oracles are practical: A paradigm for designing efficient protocols, in First ACM Conference on Computer and Communications Security, pp. 62–73 (1993)

10.

J. Black, P. Rogaway, T. Shrimpton, Encryption-scheme security in the presence of key-dependent messages, in SAC ’02, pp. 62–75 (2002)

11.

A. Blum, M. Furst, M. Kearns, R.J. Lipton, Cryptographic primitives based on hard learning problems, in Advances in Cryptology—CRYPTO 1993, pp. 278–291 (1993)

12.

A. Blum, A. Kalai, H. Wasserman, Noise-tolerant learning, the parity problem, and the statistical query model. J. ACM 50(4), 506–519 (2003)

13.

M. Blum, S. Micali, How to generate cryptographically strong sequences of pseudo-random bits. SIAM J. Comput. 13, 850–864 (1984)

14.

D. Boneh, S. Halevi, M. Hamburg, R. Ostrovsky, Circular-secure encryption from decision diffie-hellman, in Advances in Cryptology—CRYPTO 2008, pp. 108–125 (2008)

15.

F. Böhl, G.T. Davies, D. Hofheinz, Encryption schemes secure under related-key and key-dependent message attacks, in Public Key Cryptography, pp. 483–500 (2014)

16.

J. Camenisch, A. Lysyanskaya, An efficient system for non-transferable anonymous credentials with optional anonymity revocation, in Advances in Cryptology—EUROCRYPT 2001, pp. 93–118 (2001)

17.

R. Canetti, O. Goldreich, S. Halevi, The random oracle methodology, revisited. J. ACM 51(4), 557–594 (2004)

18.

S.G. Choi, J. Katz, R. Kumaresan, H.S. Zhou, On the security of the ”free-XOR” technique, in TCC ’12, pp. 39–53 (2012)

19.

H. Gilbert, M.J.B. Robshaw, Y. Seurin, How to encrypt with the LPN problem. in Automata, Languages and Programming, 35th International Colloquium, ICALP ’08, pp. 679–690 (2008)

20.

O. Goldreich, H. Krawczyk, M. Luby, On the existence of pseudorandom generators. SIAM J. Comput. 22(6), 1163–1175 (1993)

21.

O. Goldreich, S. Micali, A. Wigderson, How to play ANY mental game, in Proc. 19th STOC, pp. 218–229 (1987)

22.

J. Håstad, R. Impagliazzo, L.A. Levin, M. Luby, A pseudorandom generator from any one-way function. SIAM J. Comput. 28(4), 1364–1396 (1999)

23.

W. Henecka, S. Kögl, A.R. Sadeghi, T. Schneider, I. Wehrenberg, TASTY: Tool for automating secure two-party computations, in CCS 10’, pp. 451–462 (2010)

24.

Y. Huang, D. Evans, J. Katz, L. Malka, Faster secure two-party computation using garbled circuits, in USENIX Security Symposium, pp. 539–554 (2011).

25.

Y. Huang, C.H Shen, D. Evans, J. Katz, A. Shelat, Efficient secure computation with garbled circuits, in ICISS ’11, pp. 28–48 (2011)

26.

Y. Ishai, J. Kilian, K. Nissim, E. Petrank, Extending oblivious transfers efficiently, in Advances in Cryptology—CRYPTO 2003, pp. 145–161 (2003)

27.

Y. Ishai, E. Kushilevitz, Randomizing polynomials: A new representation with applications to round-efficient secure computation, in Proc. 41st FOCS, pp. 294–304 (2000)

28.

V. Kolesnikov, A.R. Sadeghi, T. Schneider, Improved garbled circuit building blocks and applications to auctions and computing minima, in CANS, pp. 1–20 (2009)

29.

V. Kolesnikov, T. Schneider, Improved garbled circuit: Free XOR gates and applications, in Automata, Languages and Programming, 35th International Colloquium, ICALP ’08, pp. 486–498 (2008)

30.

B. Kreuter, A. Shelat, C.H. Shen, Billion-gate secure computation with malicious adversaries, in Security’12: Proceedings of the 21st USENIX conference on Security Symposium, pp. 14–14 (2012)

31.

Y. Lindell, B. Pinkas, N. Smart, Implementing two-party computation efficiently with security against malicious adversaries, in SCN ’08, pp. 2–20 (Sep 2008)

32.

Y. Lindell, B. Pinkas, An efficient protocol for secure two-party computation in the presence of malicious adversaries, in Advances in Cryptology—EUROCRYPT 2007, pp. 52–78 (2007)

33.

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

34.

L. Malka, J. Katz, Vmcrypt—Modular software architecture for scalable secure computation, in CCS ’11, pp. 715–724 (2011)

35.

D. Malkhi, N. Nisan, B. Pinkas, Y. Sella, Fairplay—A secure two-party computation system, in Proc. of 13th USENIX Security Symposium, pp. 287–302 (2004)

36.

U.M. Maurer, Indistinguishability of random systems, in Advances in Cryptology—EUROCRYPT 2002, pp. 110–132 (2002)

37.

M. Naor, B. Pinkas, Oblivious transfer with adaptive queries, in Advances in Cryptology—CRYPTO 1999, pp. 573 –590 (1999)

38.

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

39.

J.B. Nielsen, C. Orlandi, LEGO for two-party secure computation, in Theory of Cryptography, 6th Theory of Cryptography Conference, TCC 2009, pp. 368–386 (2009)

40.

B. Pinkas, T. Schneider, N. Smart, S. Williams, Secure two-party computation is practical, in Advances in Cryptology—ASIACRYPT 2009, pp. 250–267 (2009)

41.

P. Rogaway, The Round Complexity of Secure Protocols. Ph.D. thesis, MIT (June 1991)

42.

A. Shelat, C.H. Shen, Two-output secure computation with malicious adversaries, in Advances in Cryptology—EUROCRYPT 2011, pp. 386–405 (2011)

43.

D.A. Spielman, Linear-time encodable and decodable error-correcting codes, in Proc. 27th STOC, pp. 388–397 (1995)

44.

A.C. Yao, Theory and application of trapdoor functions, in Proc. 23rd FOCS, pp. 80–91 (1982)

45.

A.C. Yao, How to generate and exchange secrets, in Proc. 27th FOCS, pp. 162–167 (1986)

Titel: Garbling XOR Gates “For Free” in the Standard Model
verfasst von: Benny Applebaum
Publikationsdatum: 01.07.2016
Verlag: Springer US
Erschienen in: Journal of Cryptology / Ausgabe 3/2016
Print ISSN: 0933-2790
Elektronische ISSN: 1432-1378
DOI: https://doi.org/10.1007/s00145-015-9201-9

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/2016

Leakage-Resilient Cryptography from Minimal Assumptions

Practical Cryptanalysis of ISO 9796-2 and EMV Signatures

Tightly Secure Signatures From Lossy Identification Schemes

A Dichotomy for Local Small-Bias Generators

An Optimally Fair Coin Toss

Premium Partner