Oblivious transfer from trapdoor permutations in minimal rounds. (English) Zbl 1511.94077
Nissim, Kobbi (ed.) et al., Theory of cryptography. 19th international conference, TCC 2021, Raleigh, NC, USA, November 8–11, 2021. Proceedings. Part II. Cham: Springer. Lect. Notes Comput. Sci. 13043, 518-549 (2021).
Summary: Oblivious transfer (OT) is a foundational primitive within cryptography owing to its connection with secure computation. One of the oldest constructions of oblivious transfer was from certified trapdoor permutations (TDPs). However several decades later, we do not know if a similar construction can be obtained from TDPs in general.
In this work, we study the problem of constructing round optimal oblivious transfer from trapdoor permutations. In particular, we obtain the following new results (in the plain model) relying on TDPs in a black-box manner:
A key technical tool underlying our results is a new primitive we call dual witness encryption (DWE) that may be of independent interest.
For the entire collection see [Zbl 1508.94003].
In this work, we study the problem of constructing round optimal oblivious transfer from trapdoor permutations. In particular, we obtain the following new results (in the plain model) relying on TDPs in a black-box manner:
- –
- Three-round oblivious transfer protocol that guarantees indistinguishability-security against malicious senders (and semi-honest receivers).
- –
- Four-round oblivious transfer protocol secure against malicious adversaries with black-box simulation-based security.
A key technical tool underlying our results is a new primitive we call dual witness encryption (DWE) that may be of independent interest.
For the entire collection see [Zbl 1508.94003].
References:
| [1] | Bellare, M.; Yung, M.; Brickell, EF, Certifying cryptographic tools: the case of trapdoor permutations, Advances in Cryptology — CRYPTO’ 92, 442-460 (1993), Heidelberg: Springer, Heidelberg · Zbl 0817.94011 · doi:10.1007/3-540-48071-4_31 |
| [2] | Ben-Or, M., Goldwasser, S., Wigderson, A.: Completeness theorems for non-cryptographic fault-tolerant distributed computation (extended abstract). In: 20th ACM STOC, pp. 1-10. ACM Press, May 1988. doi:10.1145/62212.62213 |
| [3] | Benhamouda, F.; Lin, H.; Nielsen, JB; Rijmen, V., k-round multiparty computation from k-round oblivious transfer via garbled interactive circuits, Advances in Cryptology - EUROCRYPT 2018, 500-532 (2018), Cham: Springer, Cham · Zbl 1428.94060 · doi:10.1007/978-3-319-78375-8_17 |
| [4] | Brassard, G.; Crépeau, C.; Santha, M., Oblivious transfers and intersecting codes, IEEE Trans. Inf. Theory, 42, 6, 1769-1780 (1996) · Zbl 0873.94015 · doi:10.1109/18.556673 |
| [5] | Canetti, R., et al.: Fiat-Shamir: from practice to theory. In: Charikar, M., Cohen, E. (eds.) 51st ACM STOC, pp. 1082-1090. ACM Press, June 2019. doi:10.1145/3313276.3316380 · Zbl 1434.94060 |
| [6] | Canetti, R.; Lichtenberg, A.; Beimel, A.; Dziembowski, S., Certifying trapdoor permutations, revisited, Theory of Cryptography, 476-506 (2018), Cham: Springer, Cham · Zbl 1443.94049 · doi:10.1007/978-3-030-03807-6_18 |
| [7] | Chailloux, A.; Ciocan, DF; Kerenidis, I.; Vadhan, S.; Canetti, R., Interactive and noninteractive zero knowledge are equivalent in the help model, Theory of Cryptography, 501-534 (2008), Heidelberg: Springer, Heidelberg · Zbl 1162.94345 · doi:10.1007/978-3-540-78524-8_28 |
| [8] | Chaum, D., Crépeau, C., Damgård, I.: Multiparty unconditionally secure protocols (extended abstract). In: 20th ACM STOC, pp. 11-19. ACM Press, May 1988. doi:10.1145/62212.62214 |
| [9] | Rai Choudhuri, A.; Ciampi, M.; Goyal, V.; Jain, A.; Ostrovsky, R.; Pass, R.; Pietrzak, K., Round optimal secure multiparty computation from minimal assumptions, Theory of Cryptography, 291-319 (2020), Cham: Springer, Cham · Zbl 07496583 · doi:10.1007/978-3-030-64378-2_11 |
| [10] | Ciampi, M.; Ostrovsky, R.; Siniscalchi, L.; Visconti, I.; Kalai, Y.; Reyzin, L., Round-optimal secure two-party computation from trapdoor permutations, Theory of Cryptography, 678-710 (2017), Cham: Springer, Cham · Zbl 1410.94057 · doi:10.1007/978-3-319-70500-2_23 |
| [11] | Ciampi, M.; Parisella, R.; Venturi, D.; Galdi, C.; Kolesnikov, V., On adaptive security of delayed-input sigma protocols and Fiat-Shamir NIZKs, Security and Cryptography for Networks, 670-690 (2020), Cham: Springer, Cham · Zbl 1506.94034 · doi:10.1007/978-3-030-57990-6_33 |
| [12] | Damgård, I.; Nielsen, JB; Polychroniadou, A.; Raskin, M.; Robshaw, M.; Katz, J., On the communication required for unconditionally secure multiplication, Advances in Cryptology - CRYPTO 2016, 459-488 (2016), Heidelberg: Springer, Heidelberg · Zbl 1391.94740 · doi:10.1007/978-3-662-53008-5_16 |
| [13] | Even, S., Goldreich, O., Lempel, A.: A randomized protocol for signing contracts. In: Chaum, D., Rivest, R.L., Sherman, A.T. (eds.) CRYPTO 1982, pp. 205-210. Plenum Press, New York (1982) · Zbl 0538.94011 |
| [14] | Feige, U., Lapidot, D., Shamir, A.: Multiple non-interactive zero knowledge proofs based on a single random string (extended abstract). In: 31st FOCS. pp. 308-317. IEEE Computer Society Press, October 1990. doi:10.1109/FSCS.1990.89549 |
| [15] | Friolo, D.; Masny, D.; Venturi, D.; Hofheinz, D.; Rosen, A., A black-box construction of fully-simulatable, round-optimal oblivious transfer from strongly uniform key agreement, Theory of Cryptography, 111-130 (2019), Cham: Springer, Cham · Zbl 1455.94154 · doi:10.1007/978-3-030-36030-6_5 |
| [16] | Garg, S.; Mukherjee, P.; Pandey, O.; Polychroniadou, A.; Fischlin, M.; Coron, J-S, The exact round complexity of secure computation, Advances in Cryptology - EUROCRYPT 2016, 448-476 (2016), Heidelberg: Springer, Heidelberg · Zbl 1371.94637 · doi:10.1007/978-3-662-49896-5_16 |
| [17] | Garg, S.; Ostrovsky, R.; Visconti, I.; Wadia, A.; Cramer, R., Resettable statistical zero knowledge, Theory of Cryptography, 494-511 (2012), Heidelberg: Springer, Heidelberg · Zbl 1296.94115 · doi:10.1007/978-3-642-28914-9_28 |
| [18] | Goldberg, S.; Reyzin, L.; Sagga, O.; Baldimtsi, F.; Galbraith, SD; Moriai, S., Efficient noninteractive certification of RSA moduli and beyond, Advances in Cryptology - ASIACRYPT 2019, 700-727 (2019), Cham: Springer, Cham · Zbl 1456.94078 · doi:10.1007/978-3-030-34618-8_24 |
| [19] | Goldreich, O., Foundations of Cryptography: Basic Applications (2004), Cambridge: Cambridge University Press, Cambridge · Zbl 1068.94011 · doi:10.1017/CBO9780511721656 |
| [20] | Goldreich, O., Computational complexity: a conceptual perspective, SIGACT News, 39, 3, 35-39 (2008) · Zbl 1154.68056 · doi:10.1145/1412700.1412710 |
| [21] | Goldreich, O.: Basing non-interactive zero-knowledge on (enhanced) trapdoor permutations: the state of the art (2011) |
| [22] | Goldreich, O.; Oren, Y., Definitions and properties of zero-knowledge proof systems, J. Cryptol., 7, 1, 1-32 (1994) · Zbl 0791.94010 · doi:10.1007/BF00195207 |
| [23] | Goldreich, O.; Rothblum, RD, Enhancements of trapdoor permutations, J. Cryptol., 26, 3, 484-512 (2013) · Zbl 1372.94427 · doi:10.1007/s00145-012-9131-8 |
| [24] | Goldwasser, S., Micali, S., Rackoff, C.: The knowledge complexity of interactive proof-systems (extended abstract). In: 17th ACM STOC, pp. 291-304. ACM Press, May 1985. doi:10.1145/22145.22178 · Zbl 0900.94025 |
| [25] | Goldwasser, S.; Micali, S.; Rackoff, C., The knowledge complexity of interactive proof systems, SIAM J. Comput., 18, 1, 186-208 (1989) · Zbl 0677.68062 · doi:10.1137/0218012 |
| [26] | Haitner, I.; Naor, M., Implementing oblivious transfer using collection of dense trapdoor permutations, Theory of Cryptography, 394-409 (2004), Heidelberg: Springer, Heidelberg · Zbl 1197.94189 · doi:10.1007/978-3-540-24638-1_22 |
| [27] | Harnik, D.; Kilian, J.; Naor, M.; Reingold, O.; Rosen, A.; Cramer, R., On robust combiners for oblivious transfer and other primitives, Advances in Cryptology - EUROCRYPT 2005, 96-113 (2005), Heidelberg: Springer, Heidelberg · Zbl 1137.94346 · doi:10.1007/11426639_6 |
| [28] | 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 |
| [29] | Kakvi, SA; Kiltz, E.; May, A.; Wang, X.; Sako, K., Certifying RSA, Advances in Cryptology - ASIACRYPT 2012, 404-414 (2012), Heidelberg: Springer, Heidelberg · Zbl 1292.94087 · doi:10.1007/978-3-642-34961-4_25 |
| [30] | Katz, J.; Ostrovsky, R.; Franklin, M., Round-optimal secure two-party computation, Advances in Cryptology - CRYPTO 2004, 335-354 (2004), Heidelberg: Springer, Heidelberg · Zbl 1104.94027 · doi:10.1007/978-3-540-28628-8_21 |
| [31] | Kilian, J.: Founding cryptography on oblivious transfer. In: 20th ACM STOC, pp. 20-31. ACM Press, May 1988. doi:10.1145/62212.62215 |
| [32] | Kilian, J.: A note on efficient zero-knowledge proofs and arguments (extended abstract). In: 24th ACM STOC, pp. 723-732. ACM Press, May 1992. doi:10.1145/129712.129782 |
| [33] | Lindell, Y.; Kilian, J., Parallel coin-tossing and constant-round secure two-party computation, Advances in Cryptology — CRYPTO 2001, 171-189 (2001), Heidelberg: Springer, Heidelberg · Zbl 1002.94521 · doi:10.1007/3-540-44647-8_10 |
| [34] | Naor, M., Pinkas, B.: Efficient oblivious transfer protocols. In: Kosaraju, S.R. (ed.) 12th SODA, pp. 448-457. ACM-SIAM, January 2001 · Zbl 0991.94045 |
| [35] | Ostrovsky, R.; Richelson, S.; Scafuro, A.; Gennaro, R.; Robshaw, M., Round-optimal black-box two-party computation, Advances in Cryptology - CRYPTO 2015, 339-358 (2015), Heidelberg: Springer, Heidelberg · Zbl 1352.94056 · doi:10.1007/978-3-662-48000-7_17 |
| [36] | Ostrovsky, R., Venkatesan, R., Yung, M.: Fair games against an all-powerful adversary. In: Cai, J. (ed.) Advances in Computational Complexity Theory, Proceedings of a DIMACS Workshop, New Jersey, USA, 3-7 December 1990. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 13, pp. 155-169. DIMACS/AMS (1990). doi:10.1090/dimacs/013/09 · Zbl 0789.94008 |
| [37] | Peikert, C.; Vaikuntanathan, V.; Waters, B.; Wagner, D., A framework for efficient and composable oblivious transfer, Advances in Cryptology - CRYPTO 2008, 554-571 (2008), Heidelberg: Springer, Heidelberg · Zbl 1183.94046 · doi:10.1007/978-3-540-85174-5_31 |
| [38] | Rabin, M.O.: Digital signatures and public key functions as intractable as factorization. Technical report MIT/LCS/TR-212, Massachusetts Institute of Technology, January 1979 |
| [39] | Rothblum, R.: A taxonomy of enhanced trapdoor permutations. Electron. Colloq. Comput. Complex. (ECCC) 17, 145 (2010). http://eccc.hpi-web.de/report/2010/145 |
| [40] | Yao, A.C.C.: Protocols for secure computations (extended abstract). In: 23rd FOCS, pp. 160-164. IEEE Computer Society Press, November 1982. doi:10.1109/SFCS.1982.38 |
| [41] | Yao, A.C.C.: How to generate and exchange secrets (extended abstract). In: 27th FOCS, pp. 162-167. IEEE Computer Society Press, October 1986. doi:10.1109/SFCS.1986.25 |
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.
