Laconic oblivious transfer and its applications. (English) Zbl 1409.94866
Katz, Jonathan (ed.) et al., Advances in cryptology – CRYPTO 2017. 37th annual international cryptology conference, Santa Barbara, CA, USA, August 20–24, 2017. Proceedings. Part II. Cham: Springer. Lect. Notes Comput. Sci. 10402, 33-65 (2017).
Summary: In this work, we introduce a novel technique for secure computation over large inputs. Specifically, we provide a new oblivious transfer (OT) protocol with a laconic receiver. Laconic OT allows a receiver to commit to a large input \(D\) (of length \(M\)) via a short message. Subsequently, a single short message by a sender allows the receiver to learn \(m_{D[L]}\), where the messages \(m_0, m_1\) and the location \(L \in [M]\) are dynamically chosen by the sender. All prior constructions of OT required the receiver’s outgoing message to grow with \(D\).{
}Our key contribution is an instantiation of this primitive based on the decisional Diffie-Hellman (DDH) assumption in the common reference string (CRS) model. The technical core of this construction is a novel use of somewhere statistically binding (SSB) hashing in conjunction with hash proof systems. Next, we show applications of laconic OT to non-interactive secure computation on large inputs and multi-hop homomorphic encryption for RAM programs.
For the entire collection see [Zbl 1369.94004].
For the entire collection see [Zbl 1369.94004].
MSC:
| 94A60 | Cryptography |
References:
| [1] | Ateniese, G.; Cristofaro, E.; Tsudik, G.; Catalano, D.; Fazio, N.; Gennaro, R.; Nicolosi, A., (If) Size matters: size-hiding private set intersection, Public Key Cryptography - PKC 2011, 156-173, 2011, Heidelberg: Springer, Heidelberg · Zbl 1281.94012 · doi:10.1007/978-3-642-19379-8_10 |
| [2] | Applebaum, B.; Ishai, Y.; Kushilevitz, E.; Waters, B.; Canetti, R.; Garay, JA, Encoding functions with constant online rate or how to compress garbled circuits keys, Advances in Cryptology - CRYPTO 2013, 166-184, 2013, Heidelberg: Springer, Heidelberg · Zbl 1298.94076 · doi:10.1007/978-3-642-40084-1_10 |
| [3] | Asharov, G., Lindell, Y., Schneider, T., Zohner, M.: More efficient oblivious transfer and extensions for faster secure computation. In: ACM CCS 13 (2013) |
| [4] | Bitansky, N., Canetti, R., Chiesa, A., Tromer, E.: From extractable collision resistance to succinct non-interactive arguments of knowledge, and back again. In: ITCS (2012) · Zbl 1347.68129 |
| [5] | Beaver, D.: Correlated pseudorandomness and the complexity of private computations. In: 28th ACM STOC (1996) · Zbl 0917.94012 |
| [6] | Bitansky, N., Garg, S., Lin, H., Pass, R., Telang, S.: Succinct randomized encodings and their applications. In: 47th ACM STOC (2015) · Zbl 1321.94041 |
| [7] | Bellare, M., Hoang, V.T., Rogaway, P.: Foundations of garbled circuits. In: ACM CCS (2012) |
| [8] | Bourse, F.; Pino, R.; Minelli, M.; Wee, H.; Robshaw, M.; Katz, J., FHE circuit privacy almost for free, Advances in Cryptology - CRYPTO 2016, 62-89, 2016, Heidelberg: Springer, Heidelberg · Zbl 1391.94733 · doi:10.1007/978-3-662-53008-5_3 |
| [9] | Ben-Sasson, E.; Chiesa, A.; Genkin, D.; Tromer, E.; Virza, M.; Canetti, R.; Garay, JA, SNARKs for C: verifying program executions succinctly and in zero knowledge, Advances in Cryptology - CRYPTO 2013, 90-108, 2013, Heidelberg: Springer, Heidelberg · Zbl 1317.68050 · doi:10.1007/978-3-642-40084-1_6 |
| [10] | Brakerski, Z., Vaikuntanathan, V.: Efficient fully homomorphic encryption from (standard) LWE. In: 52nd FOCS (2011) · Zbl 1292.94038 |
| [11] | Brakerski, Z.; Vaikuntanathan, V.; Rogaway, P., Fully homomorphic encryption from ring-LWE and security for key dependent messages, Advances in Cryptology - CRYPTO 2011, 505-524, 2011, Heidelberg: Springer, Heidelberg · Zbl 1290.94051 · doi:10.1007/978-3-642-22792-9_29 |
| [12] | Cho, C., Döttling, N., Garg, S., Gupta, D., Miao, P., Polychroniadou, A.: Laconic oblivious transfer and its applications. Cryptology ePrint Archive, Report 2017/491 (2017). http://eprint.iacr.org/2017/491 |
| [13] | Canetti, R., Holmgren, J., Jain, A., Vaikuntanathan, V.: Succinct garbling and indistinguishability obfuscation for RAM programs. In: 47th ACM STOC (2015) · Zbl 1321.94050 |
| [14] | Canetti, R.; Halevi, S.; Katz, J.; Cachin, C.; Camenisch, JL, Chosen-ciphertext security from identity-based encryption, Advances in Cryptology - EUROCRYPT 2004, 207-222, 2004, Heidelberg: Springer, Heidelberg · Zbl 1122.94358 · doi:10.1007/978-3-540-24676-3_13 |
| [15] | Chase, M.; Ostrovsky, R.; Visconti, I.; Oswald, E.; Fischlin, M., Executable proofs, input-size hiding secure computation and a new ideal world, Advances in Cryptology - EUROCRYPT 2015, 532-560, 2015, Heidelberg: Springer, Heidelberg · Zbl 1403.94047 |
| [16] | Cramer, R.; Shoup, V.; Krawczyk, H., A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack, Advances in Cryptology — CRYPTO ’98, 13-25, 1998, Heidelberg: Springer, Heidelberg · Zbl 0931.94018 · doi:10.1007/BFb0055717 |
| [17] | Cramer, R.; Shoup, V.; Knudsen, LR, Universal hash proofs and a paradigm for adaptive chosen ciphertext secure public-key encryption, Advances in Cryptology — EUROCRYPT 2002, 45-64, 2002, Heidelberg: Springer, Heidelberg · Zbl 1055.94011 · doi:10.1007/3-540-46035-7_4 |
| [18] | Chase, M.; Visconti, I.; Safavi-Naini, R.; Canetti, R., Secure database commitments and universal arguments of quasi knowledge, Advances in Cryptology - CRYPTO 2012, 236-254, 2012, Heidelberg: Springer, Heidelberg · Zbl 1296.94099 · doi:10.1007/978-3-642-32009-5_15 |
| [19] | Döttling, N.; Garg, S.; Katz, J.; Shacham, H., Identity-based encryption from the diffie hellman assumption, CRYPTO 2017, Part II, 537-569, 2017, Heidelberg: Springer, Heidelberg · Zbl 1385.94033 |
| [20] | Ducas, L.; Stehlé, D.; Fischlin, M.; Coron, J-S, Sanitization of FHE ciphertexts, Advances in Cryptology - EUROCRYPT 2016, 294-310, 2016, Heidelberg: Springer, Heidelberg · Zbl 1384.94057 · doi:10.1007/978-3-662-49890-3_12 |
| [21] | Feige, U., Lapidot, D., Shamir, A.: Multiple non-interactive zero knowledge proofs based on a single random string (extended abstract). In: 31st FOCS (1990) |
| [22] | Gentry, C.: Fully homomorphic encryption using ideal lattices. In: 41st ACM STOC (2009) · Zbl 1304.94059 |
| [23] | Garg, S.; Gentry, C.; Halevi, S.; Johansson, T.; Nguyen, PQ, Candidate multilinear maps from ideal lattices, Advances in Cryptology - EUROCRYPT 2013, 1-17, 2013, Heidelberg: Springer, Heidelberg · Zbl 1300.94055 · doi:10.1007/978-3-642-38348-9_1 |
| [24] | Garg, S., Gentry, C., Halevi, S., Raykova, M., Sahai, A., Waters, B.: Candidate indistinguishability obfuscation and functional encryption for all circuits. In: 54th FOCS (2013) |
| [25] | Garg, S.; Gupta, D.; Miao, P.; Pandey, O.; Hirt, M.; Smith, A., Secure multiparty RAM computation in constant rounds, Theory of Cryptography, 491-520, 2016, Heidelberg: Springer, Heidelberg · Zbl 1406.94055 · doi:10.1007/978-3-662-53641-4_19 |
| [26] | Garg, S., Gentry, C., Sahai, A., Waters, B.: Witness encryption and its applications. In: 45th ACM STOC (2013) · Zbl 1293.94066 |
| [27] | Gentry, C.; Halevi, S.; Lu, S.; Ostrovsky, R.; Raykova, M.; Wichs, D.; Nguyen, PQ; Oswald, E., Garbled RAM revisited, Advances in Cryptology - EUROCRYPT 2014, 405-422, 2014, Heidelberg: Springer, Heidelberg · Zbl 1332.94067 · doi:10.1007/978-3-642-55220-5_23 |
| [28] | Gentry, C., Halevi, S., Raykova, M., Wichs, D.: Outsourcing private RAM computation. In: 55th FOCS (2014) |
| [29] | Gentry, C.; Halevi, S.; Vaikuntanathan, V.; Rabin, T., i-hop homomorphic encryption and rerandomizable yao circuits, Advances in Cryptology - CRYPTO 2010, 155-172, 2010, Heidelberg: Springer, Heidelberg · Zbl 1280.94061 · doi:10.1007/978-3-642-14623-7_9 |
| [30] | Gordon, S.D., Katz, J., Kolesnikov, V., Krell, F., Malkin, T., Raykova, M., Vahlis, Y.: Secure two-party computation in sublinear (amortized) time. In: ACM CCS (2012) |
| [31] | Goldwasser, S.; Kalai, YT; Popa, RA; Vaikuntanathan, V.; Zeldovich, N.; Canetti, R.; Garay, JA, How to run turing machines on encrypted data, Advances in Cryptology - CRYPTO 2013, 536-553, 2013, Heidelberg: Springer, Heidelberg · Zbl 1311.94082 · doi:10.1007/978-3-642-40084-1_30 |
| [32] | Garg, S., Lu, S., Ostrovsky, R.: Black-box garbled RAM. In: 56th FOCS (2015) |
| [33] | Garg, S., Lu, S., Ostrovsky, R., Scafuro, A.: Garbled RAM from one-way functions. In: 47th ACM STOC (2015) · Zbl 1321.94061 |
| [34] | Goldreich, O., Micali, S., Wigderson, A.: How to play any mental game or A completeness theorem for protocols with honest majority. In: 19th ACM STOC (1987) |
| [35] | Goldreich, O.: Towards a theory of software protection and simulation by oblivious RAMs. In: 19th ACM STOC (1987) |
| [36] | Groth, J.; Ostrovsky, R.; Sahai, A.; Dwork, C., Non-interactive zaps and new techniques for NIZK, Advances in Cryptology - CRYPTO 2006, 97-111, 2006, Heidelberg: Springer, Heidelberg · Zbl 1129.94024 · doi:10.1007/11818175_6 |
| [37] | Gentry, C.; Sahai, A.; Waters, B.; Canetti, R.; Garay, JA, Homomorphic encryption from learning with errors: conceptually-simpler, asymptotically-faster, attribute-based, Advances in Cryptology - CRYPTO 2013, 75-92, 2013, Heidelberg: Springer, Heidelberg · Zbl 1310.94148 · doi:10.1007/978-3-642-40041-4_5 |
| [38] | Hubacek, P., Wichs, P.: On the communication complexity of secure function evaluation with long output. In: ITCS (2015) |
| [39] | Ishai, Y.; Kilian, J.; Nissim, K.; Petrank, E.; Boneh, D., Extending oblivious transfers efficiently, Advances in Cryptology - CRYPTO 2003, 145-161, 2003, Heidelberg: Springer, Heidelberg · Zbl 1122.94422 · doi:10.1007/978-3-540-45146-4_9 |
| [40] | Ishai, Y.; Kushilevitz, E.; Ostrovsky, R.; Prabhakaran, M.; Sahai, A.; Paterson, KG, Efficient non-interactive secure computation, Advances in Cryptology - EUROCRYPT 2011, 406-425, 2011, Heidelberg: Springer, Heidelberg · Zbl 1290.94151 · doi:10.1007/978-3-642-20465-4_23 |
| [41] | Ishai, Y.; Paskin, A.; Vadhan, SP, Evaluating branching programs on encrypted data, Theory of Cryptography, 575-594, 2007, Heidelberg: Springer, Heidelberg · Zbl 1156.94354 · doi:10.1007/978-3-540-70936-7_31 |
| [42] | Ishai, Y.; Prabhakaran, M.; Sahai, A.; Wagner, D., Founding cryptography on oblivious transfer – efficiently, Advances in Cryptology - CRYPTO 2008, 572-591, 2008, Heidelberg: Springer, Heidelberg · Zbl 1183.94037 · doi:10.1007/978-3-540-85174-5_32 |
| [43] | Kilian, J.: Founding cryptography on oblivious transfer. In: 20th ACM STOC (1988) |
| [44] | Kolesnikov, V.; Kumaresan, R.; Canetti, R.; Garay, JA, Improved OT extension for transferring short secrets, Advances in Cryptology - CRYPTO 2013, 54-70, 2013, Heidelberg: Springer, Heidelberg · Zbl 1316.94080 · doi:10.1007/978-3-642-40084-1_4 |
| [45] | Koppula, V., Lewko, A.B., Waters, B.: Indistinguishability obfuscation for turing machines with unbounded memory. In: 47th ACM STOC (2015) · Zbl 1321.94069 |
| [46] | Lindell, Y.; Nissim, K.; Orlandi, C.; Sako, K.; Sarkar, P., Hiding the input-size in secure two-party computation, Advances in Cryptology - ASIACRYPT 2013, 421-440, 2013, Heidelberg: Springer, Heidelberg · Zbl 1326.94110 · doi:10.1007/978-3-642-42045-0_22 |
| [47] | Lu, S.; Ostrovsky, R.; Johansson, T.; Nguyen, PQ, How to garble RAM programs?, Advances in Cryptology - EUROCRYPT 2013, 719-734, 2013, Heidelberg: Springer, Heidelberg · Zbl 1300.68027 · doi:10.1007/978-3-642-38348-9_42 |
| [48] | Lindell, Y.; Pinkas, B., A proof of security of Yao’s protocol for two-party computation, J. Cryptol., 22, 161-188, 2009 · Zbl 1159.94364 · doi:10.1007/s00145-008-9036-8 |
| [49] | Micali, S., Rabin, M.O., Kilian, J.: Zero-knowledge sets. In: 44th FOCS (2003) |
| [50] | Ostrovsky, R.; Paskin-Cherniavsky, A.; Paskin-Cherniavsky, B.; Garay, JA; Gennaro, R., Maliciously circuit-private FHE, Advances in Cryptology - CRYPTO 2014, 536-553, 2014, Heidelberg: Springer, Heidelberg · Zbl 1343.94075 · doi:10.1007/978-3-662-44371-2_30 |
| [51] | Okamoto, T.; Pietrzak, K.; Waters, B.; Wichs, D.; Iwata, T.; Cheon, JH, New realizations of somewhere statistically binding hashing and positional accumulators, Advances in Cryptology - ASIACRYPT 2015, 121-145, 2015, Heidelberg: Springer, Heidelberg · Zbl 1396.94093 · doi:10.1007/978-3-662-48797-6_6 |
| [52] | Ostrovsky, R., Shoup, V.: Private information storage (extended abstract). In: 29th ACM STOC (1997) |
| [53] | Ostrovsky, R.: Efficient computation on oblivious RAMs. In: 22nd ACM STOC (1990) |
| [54] | Rabin, M.O.: How to exchange secrets with oblivious transfer (1981) |
| [55] | Villar, JL; Wang, X.; Sako, K., Optimal reductions of some decisional problems to the rank problem, Advances in Cryptology - ASIACRYPT 2012, 80-97, 2012, Heidelberg: Springer, Heidelberg · Zbl 1292.94147 · doi:10.1007/978-3-642-34961-4_7 |
| [56] | Wang, X.S., Huang, Y., Chan, T.-H.H., Shelat, A., Shi, E.: Oblivious RAM for secure computation. In: ACM CCS (2014) |
| [57] | Yao, A.C.-C.: Protocols for secure computations (extended abstract). In: 23rd FOCS (1982) |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
