Fine-grained non-interactive key-exchange: constructions and lower bounds. (English) Zbl 1530.94015
Hazay, Carmit (ed.) et al., Advances in cryptology – EUROCRYPT 2023. 42nd annual international conference on the theory and applications of cryptographic techniques, Lyon, France, April 23–27, 2023. Proceedings. Part I. Cham: Springer. Lect. Notes Comput. Sci. 14004, 55-85 (2023).
Summary: In this work, we initiate a study of \(K\)-NIKE protocols in the fine-grained setting, in which there is a polynomial gap between the running time of the honest parties and that of the adversary. Our goal is to show the possibility, or impossibility, of basing such protocols on weaker assumptions than those of \(K\)-NIKE for \(K \ge 3\). Our contribution is threefold.
For the entire collection see [Zbl 1528.94002].
- ●
- We show that random oracles can be used to obtain fine-grained \(K\)-NIKE protocols for every constant \(K\). In particular, we show how to generalize Merkle’s two-party protocol to \(K\) parties in such a way that the honest parties ask \(n\) queries each, while the adversary needs \(n^{K/(K-1)}\) queries to the random oracle to find the key.
- ●
- We then improve the security by further using algebraic structures, while avoiding pairings. In particular, we show that there is a 4-party NIKE in Shoup’s generic group model with a quadratic gap between the number of queries by the honest parties vs. that of the adversary.
- ●
- Finally, we show a limitation of using purely algebraic methods for obtaining 3-NIKE. In particular, we show that any \(n\)-query 3-NIKE protocol in Maurer’s generic group model can be broken by a \(O(n^2)\)-query attacker. Maurer’s GGM is more limited compared with Shoup’s both for the parties and the adversary, as there are no explicit labels for the group elements. Despite being more limited, this model still captures the Diffie Hellman protocol. Prior to our work, it was open to break 3-NIKE protocols in Maurer’s model with any polynomial number of queries.
For the entire collection see [Zbl 1528.94002].
MSC:
| 94A60 | Cryptography |
References:
| [1] | Brzuska, C., Couteau, G.: On building fine-grained one-way functions from strong average-case hardness. In: Dunkelman, O., Dziembowski, S. (eds.) EUROCRYPT 2022, Part II. LNCS, vol. 13276, pp. 584-613. Springer, Heidelberg (2022). doi:10.1007/978-3-031-07085-3_20 · Zbl 1497.68209 |
| [2] | Biham, E.; Goren, YJ; Ishai, Y.; Canetti, R., Basing weak public-key cryptography on strong one-way functions, Theory of Cryptography, 55-72 (2008), Heidelberg: Springer, Heidelberg · Zbl 1162.94339 · doi:10.1007/978-3-540-78524-8_4 |
| [3] | Brassard, G.; Høyer, P.; Kalach, K.; Kaplan, M.; Laplante, S.; Salvail, L.; Rogaway, P., Merkle puzzles in a quantum world, Advances in Cryptology - CRYPTO 2011, 391-410 (2011), Heidelberg: Springer, Heidelberg · Zbl 1287.94057 · doi:10.1007/978-3-642-22792-9_22 |
| [4] | Brakerski, Z.; Jain, A.; Komargodski, I.; Passelègue, A.; Wichs, D.; Catalano, D.; De Prisco, R., Non-trivial witness encryption and null-iO from standard assumptions, Security and Cryptography for Networks, 425-441 (2018), Cham: Springer, Cham · Zbl 1517.94074 · doi:10.1007/978-3-319-98113-0_23 |
| [5] | Barak, B.; Mahmoody-Ghidary, M.; Halevi, S., Merkle puzzles are optimal — an O(n^2)-query attack on any key exchange from a random oracle, Advances in Cryptology - CRYPTO 2009, 374-390 (2009), Heidelberg: Springer, Heidelberg · Zbl 1252.94046 · doi:10.1007/978-3-642-03356-8_22 |
| [6] | Barak, B.; Mahmoody-Ghidary, M., Merkle’s key agreement protocol is optimal: an \(O(n^2)\) attack on any key agreement from random oracles, J. Cryptol., 30, 3, 699-734 (2017) · Zbl 1377.94034 · doi:10.1007/s00145-016-9233-9 |
| [7] | Barak, B., Mahmoody-Ghidary, M.: Lower bounds on signatures from symmetric primitives. In: 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), pp. 680-688. IEEE (2007) |
| [8] | Ball, M., Rosen, A., Sabin, M., Vasudevan, P.N.: Average-case fine-grained hardness. In: 49th ACM STOC, pp. 483-496. ACM Press, June 2017 · Zbl 1369.68214 |
| [9] | Ball, M.; Rosen, A.; Sabin, M.; Vasudevan, PN; Shacham, H.; Boldyreva, A., Proofs of work from worst-case assumptions, Advances in Cryptology - CRYPTO 2018, 789-819 (2018), Cham: Springer, Cham · Zbl 1444.94044 · doi:10.1007/978-3-319-96884-1_26 |
| [10] | Boneh, D.; Zhandry, M.; Garay, JA; Gennaro, R., Multiparty key exchange, efficient traitor tracing, and more from indistinguishability obfuscation, Advances in Cryptology - CRYPTO 2014, 480-499 (2014), Heidelberg: Springer, Heidelberg · Zbl 1310.94130 · doi:10.1007/978-3-662-44371-2_27 |
| [11] | Campanelli, M.; Gennaro, R.; Beimel, A.; Dziembowski, S., Fine-grained secure computation, Theory of Cryptography, 66-97 (2018), Cham: Springer, Cham · Zbl 1430.94061 · doi:10.1007/978-3-030-03810-6_3 |
| [12] | Diffie, W.; Hellman, ME, New directions in cryptography, IEEE Trans. Inf. Theory, 22, 6, 644-654 (1976) · Zbl 0435.94018 · doi:10.1109/TIT.1976.1055638 |
| [13] | Dinur, I.; Hasson, B.; Nissim, K.; Waters, B., Distributed Merkle’s puzzles, Theory of Cryptography, 310-332 (2021), Cham: Springer, Cham · Zbl 1511.94088 · doi:10.1007/978-3-030-90453-1_11 |
| [14] | Döttling, N.; Hartmann, D.; Hofheinz, D.; Kiltz, E.; Schäge, S.; Ursu, B.; Nissim, K.; Waters, B., On the impossibility of purely algebraic signatures, Theory of Cryptography, 317-349 (2021), Cham: Springer, Cham · Zbl 1511.94178 · doi:10.1007/978-3-030-90456-2_11 |
| [15] | Degwekar, Akshay; Vaikuntanathan, Vinod; Vasudevan, Prashant Nalini; Robshaw, Matthew; Katz, Jonathan, Fine-Grained Cryptography, Advances in Cryptology - CRYPTO 2016, 533-562 (2016), Heidelberg: Springer, Heidelberg · Zbl 1406.94042 · doi:10.1007/978-3-662-53015-3_19 |
| [16] | Egashira, S.; Wang, Y.; Tanaka, K., Fine-grained cryptography revisited, J. Cryptol., 34, 3, 23 (2021) · Zbl 1469.94094 · doi:10.1007/s00145-021-09390-3 |
| [17] | Freire, ESV; Hofheinz, D.; Kiltz, E.; Paterson, KG; Kurosawa, K.; Hanaoka, G., Non-Interactive Key Exchange, Public-Key Cryptography - PKC 2013, 254-271 (2013), Heidelberg: Springer, Heidelberg · Zbl 1314.94069 · doi:10.1007/978-3-642-36362-7_17 |
| [18] | G. Fuchsbauer, E. Kiltz, and J. Loss. The algebraic group model and its applications. Cryptology ePrint Archive, Paper 2017/620, 2017. https://eprint.iacr.org/2017/620 · Zbl 1430.94068 |
| [19] | Guo, S.; Kamath, P.; Rosen, A.; Sotiraki, K., Limits on the efficiency of (ring) LWE-based non-interactive key exchange, J. Cryptol., 35, 1, 1 (2022) · Zbl 1479.94183 · doi:10.1007/s00145-021-09406-y |
| [20] | Joux, Antoine; Bosma, Wieb, A one round protocol for tripartite Diffie-Hellman, Algorithmic Number Theory, 385-393 (2000), Heidelberg: Springer, Heidelberg · Zbl 1029.94026 · doi:10.1007/10722028_23 |
| [21] | LaVigne, Rio; Lincoln, Andrea; Vassilevska Williams, Virginia; Boldyreva, Alexandra; Micciancio, Daniele, Public-key cryptography in the fine-grained setting, Advances in Cryptology - CRYPTO 2019, 605-635 (2019), Cham: Springer, Cham · Zbl 1509.94106 · doi:10.1007/978-3-030-26954-8_20 |
| [22] | Maurer, Ueli; Smart, Nigel P., Abstract models of computation in cryptography, Cryptography and Coding, 1-12 (2005), Heidelberg: Springer, Heidelberg · Zbl 1122.94040 · doi:10.1007/11586821_1 |
| [23] | Merkle, R.: C.s. 244 project proposal. Facsimile (1974). http://www.merkle.com/1974 |
| [24] | Merkle, RC, Secure communications over insecure channels, Commun. ACM, 21, 4, 294-299 (1978) · Zbl 1342.94085 · doi:10.1145/359460.359473 |
| [25] | Pollard, J.M.: A monte Carlo method for factorization. BIT 15, 331-334 (1975). http://cr.yp.to/bib/entries.html#1975/pollard · Zbl 0312.10006 |
| [26] | Shanks, D.: Class number, a theory of factorization, and genera. In: Proceedings of Symposium Mathematical Society, pp. 41-440 (1971) · Zbl 0223.12006 |
| [27] | Shoup, V.; Fumy, W., Lower bounds for discrete logarithms and related problems, Advances in Cryptology — EUROCRYPT ’97, 256-266 (1997), Heidelberg: Springer, Heidelberg · doi:10.1007/3-540-69053-0_18 |
| [28] | Wang, Y., Pan, J.: Non-interactive zero-knowledge proofs with fine-grained security. In: EUROCRYPT 2022, Part II. LNCS, vol. 13276, pp. 305-335. Springer, Heidelberg (2022). doi:10.1007/978-3-031-07085-3_11 · Zbl 1497.94126 |
| [29] | Zhandry, M.: To label, or not to label (in generic groups). In: Dodis, Y., Shrimpton, T. (eds.) CRYPTO 2022. LNCS, vol. 13509, pp. 66-96. Springer, Cham (2022). doi:10.1007/978-3-031-15982-4_3 · Zbl 1517.94169 |
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.
