A framework for statistically sender private OT with optimal rate. (English) Zbl 1531.94030
Handschuh, Helena (ed.) et al., Advances in cryptology – CRYPTO 2023. 43rd annual international cryptology conference, CRYPTO 2023, Santa Barbara, CA, USA, August 20–24, 2023. Proceedings. Part I. Cham: Springer. Lect. Notes Comput. Sci. 14081, 548-576 (2023).
Summary: Statistical sender privacy (SSP) is the strongest achievable security notion for two-message oblivious transfer (OT) in the standard model, providing statistical security against malicious receivers and computational security against semi-honest senders. In this work we provide a novel construction of SSP OT from the Decisional Diffie-Hellman (DDH) and the Learning Parity with Noise (LPN) assumptions achieving (asymptotically) optimal amortized communication complexity, i.e. it achieves rate 1. Concretely, the total communication complexity for \(k\) OT instances is \(2k(1+o(1))\), which (asymptotically) approaches the information-theoretic lower bound. Previously, it was only known how to realize this primitive using heavy rate-1 FHE techniques (Z. Brakerski et al. [Lect. Notes Comput. Sci. 11892, 407–437 (2019; Zbl 1455.94132)], C. Gentry and S. Halevi [ibid. 11892, 438–464 (2019; Zbl 1455.94158)]).
At the heart of our construction is a primitive called statistical co-PIR, essentially a a public key encryption scheme which statistically erases bits of the message in a few hidden locations. Our scheme achieves nearly optimal ciphertext size and provides statistical security against malicious receivers. Computational security against semi-honest senders holds under the DDH assumption.
For the entire collection see [Zbl 1529.94004].
At the heart of our construction is a primitive called statistical co-PIR, essentially a a public key encryption scheme which statistically erases bits of the message in a few hidden locations. Our scheme achieves nearly optimal ciphertext size and provides statistical security against malicious receivers. Computational security against semi-honest senders holds under the DDH assumption.
For the entire collection see [Zbl 1529.94004].
MSC:
| 94A60 | Cryptography |
References:
| [1] | Aggarwal, D., Döttling, N., Dujmovic, J., Hajiabadi, M., Malavolta, G., Obremski, M.: Algebraic restriction codes and their applications. In: Braverman, M. (ed.) 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), vol. 215, pp. 1-15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Dagstuhl, Germany (2022). https://drops.dagstuhl.de/opus/volltexte/2022/15598 · Zbl 07777566 |
| [2] | Aiello, B.; Ishai, Y.; Reingold, O.; Pfitzmann, B., Priced oblivious transfer: how to sell digital goods, Advances in Cryptology — EUROCRYPT 2001, 119-135 (2001), Heidelberg: Springer, Heidelberg · Zbl 0981.94042 · doi:10.1007/3-540-44987-6_8 |
| [3] | Applebaum, B., Garbled circuits as randomized encodings of functions: a primer, Tutorials on the Foundations of Cryptography, 1-44 (2017), Cham: Springer, Cham · Zbl 1497.94074 · doi:10.1007/978-3-319-57048-8_1 |
| [4] | Applebaum, B., Ishai, Y., Kushilevitz, E.: Cryptography in \(NC^0\). In: 45th FOCS, pp. 166-175. IEEE Computer Society Press, October 2004 |
| [5] | Badrinarayanan, S.; Fernando, R.; Jain, A.; Khurana, D.; Sahai, A.; Canteaut, A.; Ishai, Y., Statistical ZAP arguments, Advances in Cryptology - EUROCRYPT 2020, 642-667 (2020), Cham: Springer, Cham · Zbl 1479.94120 · doi:10.1007/978-3-030-45727-3_22 |
| [6] | Badrinarayanan, S.; Garg, S.; Ishai, Y.; Sahai, A.; Wadia, A.; Takagi, T.; Peyrin, T., Two-message witness indistinguishability and secure computation in the plain model from new assumptions, Advances in Cryptology - ASIACRYPT 2017, 275-303 (2017), Cham: Springer, Cham · Zbl 1417.94040 · doi:10.1007/978-3-319-70700-6_10 |
| [7] | Badrinarayanan, S.; Patranabis, S.; Sarkar, P.; Kiltz, E.; Vaikuntanathan, V., Statistical security in two-party computation revisited, Theory of Cryptography, 181-210 (2022), Cham: Springer Nature Switzerland, Cham · Zbl 1528.68131 · doi:10.1007/978-3-031-22365-5_7 |
| [8] | Bitansky, N., Freizeit, S.: Statistically sender-private OT from LPN and derandomization. Cryptology ePrint Archive, Paper 2022/185 (2022). https://eprint.iacr.org/2022/185 · Zbl 1517.94065 |
| [9] | Boyle, E., Couteau, G., Gilboa, N., Ishai, Y.: Compressing vector OLE. In: Lie, D., Mannan, M., Backes, M., Wang, X. (eds.) ACM CCS 2018, pp. 896-912. ACM Press, October 2018 |
| [10] | Boyle, E., et al.: Efficient two-round OT extension and silent non-interactive secure computation. In: Cavallaro, L., Kinder, J., Wang, X., Katz, J. (eds.) ACM CCS 2019, pp. 291-308. ACM Press, November 2019 |
| [11] | Boyle, E.; Couteau, G.; Gilboa, N.; Ishai, Y.; Kohl, L.; Scholl, P.; Boldyreva, A.; Micciancio, D., Efficient pseudorandom correlation generators: silent OT extension and more, Advances in Cryptology - CRYPTO 2019, 489-518 (2019), Cham: Springer, Cham · Zbl 1498.68048 · doi:10.1007/978-3-030-26954-8_16 |
| [12] | Boyle, E., Couteau, G., Gilboa, N., Ishai, Y., Kohl, L., Scholl, P.: Correlated pseudorandom functions from variable-density LPN. In: 61st FOCS, pp. 1069-1080. IEEE Computer Society Press, November 2020 · Zbl 1501.94033 |
| [13] | Boyle, E.; Couteau, G.; Gilboa, N.; Ishai, Y.; Kohl, L.; Scholl, P.; Micciancio, D.; Ristenpart, T., Efficient pseudorandom correlation generators from ring-LPN, Advances in Cryptology - CRYPTO 2020, 387-416 (2020), Cham: Springer, Cham · Zbl 1501.94033 · doi:10.1007/978-3-030-56880-1_14 |
| [14] | Boyle, E.; Couteau, G.; Meyer, P.; Kiltz, E.; Vaikuntanathan, V., Sublinear secure computation from new assumptions, Theory of Cryptography, 121-150 (2022), Cham: Springer Nature Switzerland, Cham · Zbl 1519.94063 · doi:10.1007/978-3-031-22365-5_5 |
| [15] | Boyle, E.; Gilboa, N.; Ishai, Y.; Robshaw, M.; Katz, J., Breaking the circuit size barrier for secure computation under DDH, Advances in Cryptology - CRYPTO 2016, 509-539 (2016), Heidelberg: Springer, Heidelberg · Zbl 1384.94038 · doi:10.1007/978-3-662-53018-4_19 |
| [16] | Boyle, E.; Gilboa, N.; Ishai, Y.; Coron, J-S; Nielsen, JB, Group-based secure computation: optimizing rounds, communication, and computation, Advances in Cryptology - EUROCRYPT 2017, 163-193 (2017), Cham: Springer, Cham · Zbl 1415.94414 · doi:10.1007/978-3-319-56614-6_6 |
| [17] | Brakerski, Z.; Branco, P.; Döttling, N.; Garg, S.; Malavolta, G.; Pass, R.; Pietrzak, K., Constant ciphertext-rate non-committing encryption from standard assumptions, Theory of Cryptography, 58-87 (2020), Cham: Springer, Cham · Zbl 1479.94135 · doi:10.1007/978-3-030-64375-1_3 |
| [18] | Brakerski, Z.; Branco, P.; Döttling, N.; Pu, S.; Dunkelman, O.; Dziembowski, S., Batch-OT with optimal rate, Advances in Cryptology - EUROCRYPT 2022, 157-186 (2022), Cham: Springer International Publishing, Cham · Zbl 1496.94030 · doi:10.1007/978-3-031-07085-3_6 |
| [19] | Brakerski, Z.; Döttling, N.; Beimel, A.; Dziembowski, S., Two-message statistically sender-private OT from LWE, Theory of Cryptography, 370-390 (2018), Cham: Springer, Cham · Zbl 1430.94060 · doi:10.1007/978-3-030-03810-6_14 |
| [20] | Brakerski, Z.; Döttling, N.; Garg, S.; Malavolta, G.; Hofheinz, D.; Rosen, A., Leveraging linear decryption: rate-1 fully-homomorphic encryption and time-lock puzzles, Theory of Cryptography, 407-437 (2019), Cham: Springer, Cham · Zbl 1455.94132 · doi:10.1007/978-3-030-36033-7_16 |
| [21] | Brakerski, Z.; Koppula, V.; Mour, T.; Micciancio, D.; Ristenpart, T., NIZK from LPN and trapdoor hash via correlation intractability for Approximable relations, Advances in Cryptology - CRYPTO 2020, 738-767 (2020), Cham: Springer, Cham · Zbl 1504.94110 · doi:10.1007/978-3-030-56877-1_26 |
| [22] | Chase, M.; Garg, S.; Hajiabadi, M.; Li, J.; Miao, P.; Nissim, K.; Waters, B., Amortizing rate-1 OT and applications to PIR and PSI, Theory of Cryptography, 126-156 (2021), Cham: Springer, Cham · Zbl 1511.94069 · doi:10.1007/978-3-030-90456-2_5 |
| [23] | Döttling, N.; Garg, S.; Ishai, Y.; Malavolta, G.; Mour, T.; Ostrovsky, R.; Boldyreva, A.; Micciancio, D., Trapdoor hash functions and their applications, Advances in Cryptology - CRYPTO 2019, 3-32 (2019), Cham: Springer, Cham · Zbl 1436.94054 · doi:10.1007/978-3-030-26954-8_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, pp. 40-49. IEEE Computer Society Press, October 2013 · Zbl 1348.94048 |
| [25] | Garg, S.; Hajiabadi, M.; Ostrovsky, R.; Pass, R.; Pietrzak, K., Efficient range-trapdoor functions and applications: rate-1 OT and more, Theory of Cryptography, 88-116 (2020), Cham: Springer, Cham · Zbl 1479.94176 · doi:10.1007/978-3-030-64375-1_4 |
| [26] | Gentry, C.; Halevi, S.; Hofheinz, D.; Rosen, A., Compressible FHE with applications to PIR, Theory of Cryptography, 438-464 (2019), Cham: Springer, Cham · Zbl 1455.94158 · doi:10.1007/978-3-030-36033-7_17 |
| [27] | Goldreich, O.; Goldwasser, S.; Micali, S., How to construct random functions, J. ACM, 33, 4, 792-807 (1986) · Zbl 0596.65002 · doi:10.1145/6490.6503 |
| [28] | Goldreich, O., Micali, S., Wigderson, A.: How to play any mental game or a completeness theorem for protocols with honest majority. In: Aho, A. (ed.) 19th ACM STOC, pp. 218-229. ACM Press, May 1987 |
| [29] | Goyal, V.; Jain, A.; Jin, Z.; Malavolta, G.; Canteaut, A.; Ishai, Y., Statistical zaps and new oblivious transfer protocols, Advances in Cryptology - EUROCRYPT 2020, 668-699 (2020), Cham: Springer, Cham · Zbl 1479.94180 · doi:10.1007/978-3-030-45727-3_23 |
| [30] | Halevi, S.; Kalai, YT, Smooth projective hashing and two-message oblivious transfer, J. Cryptol., 25, 1, 158-193 (2012) · Zbl 1272.94033 · doi:10.1007/s00145-010-9092-8 |
| [31] | 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 |
| [32] | Ishai, Y., Kushilevitz, E.: Randomizing polynomials: a new representation with applications to round-efficient secure computation. In: 41st FOCS, pp. 294-304. IEEE Computer Society Press, November 2000 |
| [33] | Ishai, Y.; Kushilevitz, E.; Widmayer, P.; Eidenbenz, S.; Triguero, F.; Morales, R.; Conejo, R.; Hennessy, M., Perfect Constant-round secure computation via perfect randomizing polynomials, Automata, Languages and Programming, 244-256 (2002), Heidelberg: Springer, Heidelberg · Zbl 1056.68088 · doi:10.1007/3-540-45465-9_22 |
| [34] | Ishai, Y., Kushilevitz, E., Ostrovsky, R., Sahai, A.: Cryptography with constant computational overhead. In: Ladner, R.E., Dwork, C. (eds.) 40th ACM STOC, pp. 433-442. ACM Press, May 2008 · Zbl 1231.94050 |
| [35] | 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 |
| [36] | Jain, A.; Jin, Z.; Canteaut, A.; Standaert, F-X, Non-interactive zero knowledge from sub-exponential DDH, Advances in Cryptology - EUROCRYPT 2021, 3-32 (2021), Cham: Springer, Cham · Zbl 1479.94194 · doi:10.1007/978-3-030-77870-5_1 |
| [37] | Jain, A.; Kalai, YT; Khurana, D.; Rothblum, R.; Katz, J.; Shacham, H., Distinguisher-dependent simulation in two rounds and its applications, Advances in Cryptology - CRYPTO 2017, 158-189 (2017), Cham: Springer, Cham · Zbl 1409.94880 · doi:10.1007/978-3-319-63715-0_6 |
| [38] | Kalai, YT; Khurana, D.; Sahai, A.; Nielsen, JB; Rijmen, V., Statistical witness indistinguishability (and more) in two messages, Advances in Cryptology - EUROCRYPT 2018, 34-65 (2018), Cham: Springer, Cham · Zbl 1415.94444 · doi:10.1007/978-3-319-78372-7_2 |
| [39] | Kalai, Y.T., Lombardi, A., Vaikuntanathan, V., Wichs, D.: Boosting batch arguments and ram delegation. Cryptology ePrint Archive, Paper 2022/1320 (2022). https://eprint.iacr.org/2022/1320 |
| [40] | Khurana, D.; Mughees, MH; Pass, R.; Pietrzak, K., On statistical security in two-party computation, Theory of Cryptography, 532-561 (2020), Cham: Springer, Cham · Zbl 1485.94099 · doi:10.1007/978-3-030-64378-2_19 |
| [41] | Khurana, D., Sahai, A.: How to achieve non-malleability in one or two rounds. In: Umans, C. (ed.) 58th FOCS, pp. 564-575. IEEE Computer Society Press, October 2017 |
| [42] | Micciancio, D.; Sorrell, J.; Moriai, S.; Wang, H., Simpler statistically sender private oblivious transfer from ideals of cyclotomic integers, Advances in Cryptology - ASIACRYPT 2020, 381-407 (2020), Cham: Springer, Cham · Zbl 1511.94137 · doi:10.1007/978-3-030-64834-3_13 |
| [43] | 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 |
| [44] | 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 |
| [45] | Peikert, C., Waters, B.: Lossy trapdoor functions and their applications. In: Ladner, R.E., Dwork, C. (eds.) 40th ACM STOC, pp. 187-196. ACM Press, May 2008 · Zbl 1228.94027 |
| [46] | Rabin, M.O.: How to exchange secrets with oblivious transfer. Cryptology ePrint Archive (2005) |
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.
