Garbling XOR gates “for free” in the standard model. (English) Zbl 1348.94030

Summary: A. Yao’s garbled circuit (GC) technique [How to generate and exchange secrets, IEEE 27th Ann. Symp. FOCS 1986, 162–167 (1986)] 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). V. Kolesnikov and T. Schneider [ICALP 2008, Lect. Notes Comput. Sci. 5126, 486–498 (2008; Zbl 1155.94374)] 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 [S. G. Choi et al., TCC 2012, Lect. Notes Comput. Sci. 7194, 39–53 (2012; Zbl 1303.94075)], 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.


94A60 Cryptography


Full Text: DOI Link


[1] B. Applebaum, Randomly encoding functions: A new cryptographic paradigm (invited talk), in ICITS, pp. 25-31 (2011) · Zbl 1295.94007
[2] 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) · Zbl 1252.94044
[3] B. Applebaum, D. Harnik, Y. Ishai, Semantic security under related-key attacks and applications, in ICS, pp. 45-60 (2011)
[4] B. Applebaum, Y. Ishai, E. Kushilevitz, Computationally private randomizing polynomials and their applications. Comput. Complex.15(2), 115-162 (2006) · Zbl 1143.94009
[5] B. Applebaum, Y. Ishai, E. Kushilevitz, How to garble arithmetic circuits, in Proc. 52nd FOCS, pp. 120-129 (2011) · Zbl 1292.94186
[6] M. Bellare, D. Cash, Pseudorandom functions and permutations provably secure against related-key attacks, in Advances in Cryptology—CRYPTO 2010, pp. 666-684 (2010) · Zbl 1283.94050
[7] M. Bellare, V.T. Hoang, P. Rogaway, Foundations of garbled circuits, in CCS ’12, pp. 784-796 (2012)
[8] 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) · Zbl 1038.94520
[9] 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) · Zbl 1027.68594
[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) · Zbl 0870.94021
[12] A. Blum, A. Kalai, H. Wasserman, Noise-tolerant learning, the parity problem, and the statistical query model. J. ACM50(4), 506-519 (2003) · Zbl 1325.68114
[13] M. Blum, S. Micali, How to generate cryptographically strong sequences of pseudo-random bits. SIAM J. Comput.13, 850-864 (1984) · Zbl 0547.68046
[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) · Zbl 1183.94025
[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) · Zbl 1335.94034
[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) · Zbl 0981.94043
[17] R. Canetti, O. Goldreich, S. Halevi, The random oracle methodology, revisited. J. ACM51(4), 557-594 (2004) · Zbl 1204.94063
[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) · Zbl 1303.94075
[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) · Zbl 1155.94368
[20] O. Goldreich, H. Krawczyk, M. Luby, On the existence of pseudorandom generators. SIAM J. Comput.22(6), 1163-1175 (1993) · Zbl 0795.94011
[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) · Zbl 0940.68048
[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) · Zbl 1122.94422
[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) · Zbl 1287.94078
[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) · Zbl 1155.94374
[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) · Zbl 1180.68152
[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) · Zbl 1141.94362
[33] Y. Lindell, B. Pinkas, A proof of security of yao’s protocol for two-party computation. J. Cryptol.22(2), 161-188 (2009) · Zbl 1159.94364
[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) · Zbl 1055.94021
[37] M. Naor, B. Pinkas, Oblivious transfer with adaptive queries, in Advances in Cryptology—CRYPTO 1999, pp. 573 -590 (1999) · Zbl 0942.94011
[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) · Zbl 1213.94124
[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) · Zbl 1267.94091
[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) · Zbl 1282.68086
[43] D.A. Spielman, Linear-time encodable and decodable error-correcting codes, in Proc. 27th STOC, pp. 388-397 (1995) · Zbl 1058.94525
[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)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.