Statistically sender-private OT from LPN and derandomization. (English) Zbl 1517.94065
Dodis, Yevgeniy (ed.) et al., Advances in cryptology – CRYPTO 2022. 42nd annual international cryptology conference, CRYPTO 2022, Santa Barbara, CA, USA, August 15–18, 2022. Proceedings. Part III. Cham: Springer. Lect. Notes Comput. Sci. 13509, 625-653 (2022).
Summary: We construct a two-message oblivious transfer protocol with statistical sender privacy (SSP OT) based on the Learning Parity with Noise (LPN) Assumption and a standard Nisan-Wigderson style derandomization assumption. Beyond being of interest on their own, SSP OT protocols have proven to be a powerful tool toward minimizing the round complexity in a wide array of cryptographic applications from proofs systems, through secure computation protocols, to hard problems in statistical zero knowledge (SZK).
The protocol is plausibly post-quantum secure. The only other constructions with plausible post quantum security are based on the Learning with Errors (LWE) Assumption. Lacking the geometric structure of LWE, our construction and analysis rely on a different set of techniques.
Technically, we first construct an SSP OT protocol in the common random string model from LPN alone, and then derandomize the common random string. Most of the technical difficulty lies in the first step. Here we prove a robustness property of the inner product randomness extractor to a certain type of linear splitting attacks. A caveat of our construction is that it relies on the so called low noise regime of LPN. This aligns with our current complexity-theoretic understanding of LPN, which only in the low noise regime is known to imply hardness in SZK.
For the entire collection see [Zbl 1514.94003].
The protocol is plausibly post-quantum secure. The only other constructions with plausible post quantum security are based on the Learning with Errors (LWE) Assumption. Lacking the geometric structure of LWE, our construction and analysis rely on a different set of techniques.
Technically, we first construct an SSP OT protocol in the common random string model from LPN alone, and then derandomize the common random string. Most of the technical difficulty lies in the first step. Here we prove a robustness property of the inner product randomness extractor to a certain type of linear splitting attacks. A caveat of our construction is that it relies on the so called low noise regime of LPN. This aligns with our current complexity-theoretic understanding of LPN, which only in the low noise regime is known to imply hardness in SZK.
For the entire collection see [Zbl 1514.94003].
Keywords:
two-message oblivious transfer protocol; learning parity with noise; Nisan-Wigderson style derandomizationReferences:
| [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, LIPIcs, Berkeley, CA, USA, 31 January-3 February 2022, vol. 215, pp. 2:1-2:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022) · Zbl 07829234 |
| [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] | Alekhnovich, M.: More on average case versus approximation complexity. In: Proceedings of 44th Symposium on Foundations of Computer Science (FOCS 2003), Cambridge, MA, USA, 11-14 October 2003, pp. 298-307. IEEE Computer Society (2003) |
| [4] | Ananth, P.; Jain, A.; Kalai, Y.; Reyzin, L., On secure two-party computation in three rounds, Theory of Cryptography, 612-644 (2017), Cham: Springer, Cham · Zbl 1410.94040 · doi:10.1007/978-3-319-70500-2_21 |
| [5] | 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 |
| [6] | Badrinarayanan, S.; Goyal, V.; Jain, A.; Kalai, YT; Khurana, D.; Sahai, A.; Shacham, H.; Boldyreva, A., Promise zero knowledge and its applications to round optimal MPC, Advances in Cryptology - CRYPTO 2018, 459-487 (2018), Cham: Springer, Cham · Zbl 1436.94035 · doi:10.1007/978-3-319-96881-0_16 |
| [7] | Badrinarayanan, S.; Goyal, V.; Jain, A.; Khurana, D.; Sahai, A.; Kalai, Y.; Reyzin, L., Round optimal concurrent MPC via strong simulation, Theory of Cryptography, 743-775 (2017), Cham: Springer, Cham · Zbl 1410.94042 · doi:10.1007/978-3-319-70500-2_25 |
| [8] | Ball, M.; Dachman-Soled, D.; Kulkarni, M.; Lin, H.; Malkin, T.; Ishai, Y.; Rijmen, V., Non-malleable codes against bounded polynomial time tampering, Advances in Cryptology - EUROCRYPT 2019, 501-530 (2019), Cham: Springer, Cham · Zbl 1470.94076 · doi:10.1007/978-3-030-17653-2_17 |
| [9] | Banaszczyk, W.: New bounds in some transference theorems in the geometry of numbers. Mathematische Annalen 296(4), 625-636 (1993) · Zbl 0786.11035 |
| [10] | Barak, B., Ong, S.J., Vadhan, S.P.: Derandomization in cryptography. SIAM J. Comput. 37(2), 380-400 (2007) · Zbl 1141.94008 |
| [11] | Bartusek, J., Garg, S., Srinivasan, A., Zhang, Y.: Reusable two-round MPC from LPN. IACR Cryptology ePrint Archive, p. 316 (2021) |
| [12] | Bitansky, N., Freizeit, S.: Statistically sender-private OT from LPN and derandomization. Cryptology ePrint Archive, Paper 2022/185 (2022). http://eprint.iacr.org/2022/185 |
| [13] | Bitansky, N., Khurana, D., Paneth, O.: Weak zero-knowledge beyond the black-box barrier. In: Charikar, M., Cohen, E. (eds.) Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, 23-26 June 2019, pp. 1091-1102. ACM (2019) · Zbl 1434.94059 |
| [14] | Bitansky, N.; Vaikuntanathan, V.; Kushilevitz, E.; Malkin, T., Indistinguishability obfuscation: from approximate to exact, Theory of Cryptography, 67-95 (2016), Heidelberg: Springer, Heidelberg · Zbl 1388.94034 · doi:10.1007/978-3-662-49096-9_4 |
| [15] | Bitansky, N.; Vaikuntanathan, V.; Coron, J-S; Nielsen, JB, A note on perfect correctness by derandomization, Advances in Cryptology - EUROCRYPT 2017, 592-606 (2017), Cham: Springer, Cham · Zbl 1415.94411 · doi:10.1007/978-3-319-56614-6_20 |
| [16] | Blum, A.; Furst, M.; Kearns, M.; Lipton, RJ; Stinson, DR, Cryptographic primitives based on hard learning problems, Advances in Cryptology — CRYPTO’ 93, 278-291 (1994), Heidelberg: Springer, Heidelberg · Zbl 0870.94021 · doi:10.1007/3-540-48329-2_24 |
| [17] | Blum, A., Kalai, A., Wasserman, H.: Noise-tolerant learning, the parity problem, and the statistical query model. J. ACM 50(4), 506-519 (2003) · Zbl 1325.68114 |
| [18] | 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 |
| [19] | 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 |
| [20] | Brakerski, Z., Langlois, A., Peikert, C., Regev, O., Stehlé, D.: Classical hardness of learning with errors. In: Boneh, D., Roughgarden, T., Feigenbaum, J. (eds.) Symposium on Theory of Computing Conference, STOC 2013, Palo Alto, CA, USA, 1-4 June 2013, pp. 575-584. ACM (2013) · Zbl 0714.65036 |
| [21] | Brakerski, Z.; Lombardi, A.; Segev, G.; Vaikuntanathan, V.; Nielsen, JB; Rijmen, V., Anonymous IBE, leakage resilience and circular security from new assumptions, Advances in Cryptology - EUROCRYPT 2018, 535-564 (2018), Cham: Springer, Cham · Zbl 1423.94056 · doi:10.1007/978-3-319-78381-9_20 |
| [22] | Brakerski, Z.; Lyubashevsky, V.; Vaikuntanathan, V.; Wichs, D.; Ishai, Y.; Rijmen, V., Worst-case hardness for LPN and cryptographic hashing via code smoothing, Advances in Cryptology - EUROCRYPT 2019, 619-635 (2019), Cham: Springer, Cham · Zbl 1512.94168 · doi:10.1007/978-3-030-17659-4_21 |
| [23] | Brakerski, Z., Vaikuntanathan, V.: Efficient fully homomorphic encryption from (standard) LWE. In: Ostrovsky, R. (ed.) IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, 22-25 October 2011, pp. 97-106. IEEE Computer Society (2011) · Zbl 1292.94038 |
| [24] | Döttling, N., Garg, S., Hajiabadi, M., Masny, D., Wichs, D.: Two-round oblivious transfer from CDH or LPN. IACR Cryptology ePrint Archive, p. 414 (2019) · Zbl 1492.94091 |
| [25] | 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 |
| [26] | Dwork, C., Naor, M.: Zaps and their applications. In: 41st Annual Symposium on Foundations of Computer Science, FOCS 2000, Redondo Beach, California, USA, 12-14 November 2000, pp. 283-293. IEEE Computer Society (2000) · Zbl 1125.94019 |
| [27] | Even, S., Goldreich, O., Lempel, A.: A randomized protocol for signing contracts. Commun. ACM 28(6), 637-647 (1985) · Zbl 0538.94011 |
| [28] | Gentry, C.: Fully homomorphic encryption using ideal lattices. In: Mitzenmacher, M. (ed.) Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, 31 May-2 June 2009, pp. 169-178. ACM (2009) · Zbl 1304.94059 |
| [29] | Gutfreund, D., Shaltiel, R., Ta-Shma, A.: Uniform hardness versus randomness tradeoffs for arthur-merlin games. In: 18th Annual IEEE Conference on Computational Complexity (Complexity 2003), Aarhus, Denmark, 7-10 July 2003, pp. 33-47. IEEE Computer Society (2003) · Zbl 1085.68055 |
| [30] | Halevi, S., Kalai, Y.T.: Smooth projective hashing and two-message oblivious transfer. J. Cryptol. 25(1), 158-193 (2012) · Zbl 1272.94033 |
| [31] | Hubácek, P., Naor, M., Yogev, E.: The journey from NP to TFNP hardness. In: Papadimitriou, C.H. (ed.) 8th Innovations in Theoretical Computer Science Conference, ITCS 2017. LIPIcs, Berkeley, CA, USA, vol. 67, pp. 60:1-60:21. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017) · Zbl 1402.68067 |
| [32] | 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 |
| [33] | 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 |
| [34] | Katz, J., Shin, J.S., Smith, A.D.: Parallel and concurrent security of the HB and hb \({}^{\text{+}}\) protocols. J. Cryptol. 23(3), 402-421 (2010) · Zbl 1201.94090 |
| [35] | Khurana, D.; Kalai, Y.; Reyzin, L., Round optimal concurrent non-malleability from polynomial hardness, Theory of Cryptography, 139-171 (2017), Cham: Springer, Cham · Zbl 1412.94186 · doi:10.1007/978-3-319-70503-3_5 |
| [36] | Khurana, D., Sahai, A.: How to achieve non-malleability in one or two rounds. In: Umans, C. (ed.) 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, 15-17 October 2017, pp. 564-575. IEEE Computer Society (2017) |
| [37] | Kiltz, E.; Pietrzak, K.; Cash, D.; Jain, A.; Venturi, D.; Paterson, KG, Efficient authentication from hard learning problems, Advances in Cryptology - EUROCRYPT 2011, 7-26 (2011), Heidelberg: Springer, Heidelberg · Zbl 1281.94083 · doi:10.1007/978-3-642-20465-4_3 |
| [38] | Lautemann, C.: BPP and the polynomial hierarchy. Inf. Process. Lett. 17(4), 215-217 (1983) · Zbl 0515.68042 |
| [39] | Matsui, M.; Helleseth, T., Linear cryptanalysis method for DES cipher, Advances in Cryptology — EUROCRYPT ’93, 386-397 (1994), Heidelberg: Springer, Heidelberg · Zbl 0951.94519 · doi:10.1007/3-540-48285-7_33 |
| [40] | Miltersen, P.B., Vinodchandran, N.V.: Derandomizing Arthur-Merlin games using hitting sets. In: 40th Annual Symposium on Foundations of Computer Science, FOCS 1999, New York, NY, USA, 17-18 October 1999, pp. 71-80. IEEE Computer Society (1999) · Zbl 1085.68058 |
| [41] | Naor, M., Pinkas, B.: Efficient oblivious transfer protocols. In: Rao Kosaraju, S. (ed.) Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, Washington, DC, USA, 7-9 January 2001, pp. 448-457. ACM/SIAM (2001) · Zbl 0991.94045 |
| [42] | 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 |
| [43] | Peikert, C.: Public-key cryptosystems from the worst-case shortest vector problem: extended abstract. In: Mitzenmacher, M (ed.) Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, 31 May-2 June 2009, pp. 333-342. ACM (2009) · Zbl 1304.94079 |
| [44] | Pietrzak, K.; Bieliková, M.; Friedrich, G.; Gottlob, G.; Katzenbeisser, S.; Turán, G., Cryptography from learning parity with noise, SOFSEM 2012: Theory and Practice of Computer Science, 99-114 (2012), Heidelberg: Springer, Heidelberg · Zbl 1298.94103 · doi:10.1007/978-3-642-27660-6_9 |
| [45] | Rabin, M.O.: How to exchange secrets with oblivious transfer. IACR Cryptology ePrint Archive, p. 187 (2005) |
| [46] | Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. In: Gabow, H.N., Fagin, R. (ed.) Proceedings of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, MD, USA, 22-24 May 2005, pp. 84-93. ACM (2005) · Zbl 1192.94106 |
| [47] | Yu, Y.; Zhang, J.; Malkin, T.; Peikert, C., Smoothing out binary linear codes and worst-case sub-exponential hardness for LPN, Advances in Cryptology - CRYPTO 2021, 473-501 (2021), Cham: Springer, Cham · Zbl 1512.94151 · doi:10.1007/978-3-030-84252-9_16 |
| [48] | Yu, Y., Zhang, J., Weng, J., Guo, C., Li, X.: Collision resistant hashing from learning parity with noise. IACR Cryptology ePrint Archive, p. 1260 (2017) |
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.
