The cost of adaptivity in security games on graphs. (English) Zbl 1511.94115
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, 550-581 (2021).
Summary: The security of cryptographic primitives and protocols against adversaries that are allowed to make adaptive choices (e.g., which parties to corrupt or which queries to make) is notoriously difficult to establish. A broad theoretical framework was introduced by Z. Jafargholi et al. [Lect. Notes Comput. Sci. 10401, 133–163 (2017; Zbl 1407.94123)] for this purpose. In this paper we initiate the study of lower bounds on loss in adaptive security for certain cryptographic protocols considered in the framework. We prove lower bounds that almost match the upper bounds (proven using the framework) for proxy re-encryption, prefix-constrained PRFs and generalized selective decryption, a security game that captures the security of certain group messaging and broadcast encryption schemes. Those primitives have in common that their security game involves an underlying graph that can be adaptively built by the adversary.
Some of our lower bounds only apply to a restricted class of black-box reductions which we term “oblivious” (the existing upper bounds are of this restricted type), some apply to the broader but still restricted class of non-rewinding reductions, while our lower bound for proxy re-encryption applies to all black-box reductions. The fact that some of our lower bounds seem to crucially rely on obliviousness or at least a non-rewinding reduction hints to the exciting possibility that the existing upper bounds can be improved by using more sophisticated reductions. Our main conceptual contribution is a two-player multi-stage game called the Builder-Pebbler Game. We can translate bounds on the winning probabilities for various instantiations of this game into cryptographic lower bounds for the above-mentioned primitives using oracle separation techniques.
For the entire collection see [Zbl 1508.94003].
Some of our lower bounds only apply to a restricted class of black-box reductions which we term “oblivious” (the existing upper bounds are of this restricted type), some apply to the broader but still restricted class of non-rewinding reductions, while our lower bound for proxy re-encryption applies to all black-box reductions. The fact that some of our lower bounds seem to crucially rely on obliviousness or at least a non-rewinding reduction hints to the exciting possibility that the existing upper bounds can be improved by using more sophisticated reductions. Our main conceptual contribution is a two-player multi-stage game called the Builder-Pebbler Game. We can translate bounds on the winning probabilities for various instantiations of this game into cryptographic lower bounds for the above-mentioned primitives using oracle separation techniques.
For the entire collection see [Zbl 1508.94003].
MSC:
| 94A60 | Cryptography |
| 05C57 | Games on graphs (graph-theoretic aspects) |
| 91A43 | Games involving graphs |
Citations:
Zbl 1407.94123References:
| [1] | Alwen, J., et al.: Keep the dirt: tainted TreeKEM, adaptively and actively secure continuous group key agreement. Cryptology ePrint Archive, Report 2019/1489 (2019). https://eprint.iacr.org/2019/1489 |
| [2] | Alwen, J.; Coretti, S.; Dodis, Y.; Tselekounis, Y.; Micciancio, D.; Ristenpart, T., Security analysis and improvements for the IETF MLS standard for group messaging, Advances in Cryptology - CRYPTO 2020, 248-277 (2020), Cham: Springer, Cham · Zbl 1501.94024 · doi:10.1007/978-3-030-56784-2_9 |
| [3] | Alwen, J., Serbinenko, V.: High parallel complexity graphs and memory-hard functions. In: Servedio, R.A., Rubinfeld, R. (eds.) 47th ACM STOC, pp. 595-603. ACM Press, June 2015 · Zbl 1321.68374 |
| [4] | Bellare, M.; Hoang, VT; Rogaway, P.; Wang, X.; Sako, K., Adaptively secure garbling with applications to one-time programs and secure outsourcing, Advances in Cryptology - ASIACRYPT 2012, 134-153 (2012), Heidelberg: Springer, Heidelberg · Zbl 1292.94027 · doi:10.1007/978-3-642-34961-4_10 |
| [5] | Bellare, M.; Hofheinz, D.; Yilek, S.; Joux, A., Possibility and impossibility results for encryption and commitment secure under selective opening, Advances in Cryptology - EUROCRYPT 2009, 1-35 (2009), Heidelberg: Springer, Heidelberg · Zbl 1239.94033 · doi:10.1007/978-3-642-01001-9_1 |
| [6] | Bennett, CH, Time/space trade-offs for reversible computation, SIAM J. Comput., 18, 4, 766-776 (1989) · Zbl 0676.68010 · doi:10.1137/0218053 |
| [7] | Black, J.; Rogaway, P.; Shrimpton, T.; Nyberg, K.; Heys, H., Encryption-scheme security in the presence of key-dependent messages, Selected Areas in Cryptography, 62-75 (2003), Heidelberg: Springer, Heidelberg · Zbl 1027.68594 · doi:10.1007/3-540-36492-7_6 |
| [8] | Blaze, M.; Bleumer, G.; Strauss, M.; Nyberg, K., Divertible protocols and atomic proxy cryptography, Advances in Cryptology — EUROCRYPT’98, 127-144 (1998), Heidelberg: Springer, Heidelberg · Zbl 0929.68048 · doi:10.1007/BFb0054122 |
| [9] | Boneh, D.; Venkatesan, R.; Nyberg, K., Breaking RSA may not be equivalent to factoring, Advances in Cryptology — EUROCRYPT’98, 59-71 (1998), Heidelberg: Springer, Heidelberg · Zbl 0922.94008 · doi:10.1007/BFb0054117 |
| [10] | Boneh, D.; Waters, B.; Sako, K.; Sarkar, P., Constrained pseudorandom functions and their applications, Advances in Cryptology - ASIACRYPT 2013, 280-300 (2013), Heidelberg: Springer, Heidelberg · Zbl 1314.94057 · doi:10.1007/978-3-642-42045-0_15 |
| [11] | Boyle, E.; Goldwasser, S.; Ivan, I.; Krawczyk, H., Functional signatures and pseudorandom functions, Public-Key Cryptography - PKC 2014, 501-519 (2014), Heidelberg: Springer, Heidelberg · Zbl 1290.94145 · doi:10.1007/978-3-642-54631-0_29 |
| [12] | Canetti, R., Feige, U., Goldreich, O., Naor, M.: Adaptively secure multi-party computation. In: 28th ACM STOC, pp. 639-648. ACM Press, May 1996 · Zbl 0922.68048 |
| [13] | Canetti, R., Garay, J.A., Itkis, G., Micciancio, D., Naor, M., Pinkas, B.: Multicast security: a taxonomy and some efficient constructions. In: IEEE INFOCOM 1999, New York, NY, USA, pp. 708-716, 21-25 March 1999 |
| [14] | Chung, F.; Diaconis, P.; Graham, R., Combinatorics for the east model, Adv. Appl. Math., 27, 1, 192-206 (2001) · Zbl 1006.82014 · doi:10.1006/aama.2001.0728 |
| [15] | Coron, J-S; Bellare, M., On the exact security of full domain hash, Advances in Cryptology — CRYPTO 2000, 229-235 (2000), Heidelberg: Springer, Heidelberg · Zbl 0995.94533 · doi:10.1007/3-540-44598-6_14 |
| [16] | Dwork, C., Naor, M., Reingold, O., Stockmeyer, L.J.: Magic functions. In: 40th FOCS, pp. 523-534. IEEE Computer Society Press, October 1999 |
| [17] | Dwork, C.; Naor, M.; Wee, H.; Shoup, V., Pebbling and proofs of work, Advances in Cryptology - CRYPTO 2005, 37-54 (2005), Heidelberg: Springer, Heidelberg · Zbl 1145.68427 · doi:10.1007/11535218_3 |
| [18] | Dziembowski, S.; Kazana, T.; Wichs, D.; Ishai, Y., One-time computable self-erasing functions, Theory of Cryptography, 125-143 (2011), Heidelberg: Springer, Heidelberg · Zbl 1295.94061 · doi:10.1007/978-3-642-19571-6_9 |
| [19] | Fuchsbauer, G.; Jafargholi, Z.; Pietrzak, K.; Gennaro, R.; Robshaw, M., A quasipolynomial reduction for generalized selective decryption on trees, Advances in Cryptology - CRYPTO 2015, 601-620 (2015), Heidelberg: Springer, Heidelberg · Zbl 1375.94125 · doi:10.1007/978-3-662-47989-6_29 |
| [20] | Fuchsbauer, G.; Kamath, C.; Klein, K.; Pietrzak, K.; Lin, D.; Sako, K., Adaptively secure proxy re-encryption, Public-Key Cryptography - PKC 2019, 317-346 (2019), Cham: Springer, Cham · Zbl 1509.94087 · doi:10.1007/978-3-030-17259-6_11 |
| [21] | Fuchsbauer, G.; Konstantinov, M.; Pietrzak, K.; Rao, V.; Sarkar, P.; Iwata, T., Adaptive security of constrained PRFs, Advances in Cryptology - ASIACRYPT 2014, 82-101 (2014), Heidelberg: Springer, Heidelberg · Zbl 1317.94107 · doi:10.1007/978-3-662-45608-8_5 |
| [22] | Garg, S.; Ostrovsky, R.; Srinivasan, A.; Shacham, H.; Boldyreva, A., Adaptive garbled RAM from laconic oblivious transfer, Advances in Cryptology - CRYPTO 2018, 515-544 (2018), Cham: Springer, Cham · Zbl 1457.94135 · doi:10.1007/978-3-319-96878-0_18 |
| [23] | Garg, S.; Srinivasan, A.; Nielsen, JB; Rijmen, V., Adaptively secure garbling with near optimal online complexity, Advances in Cryptology - EUROCRYPT 2018, 535-565 (2018), Cham: Springer, Cham · Zbl 1428.94073 · doi:10.1007/978-3-319-78375-8_18 |
| [24] | Gennaro, R.; Gertner, Y.; Katz, J.; Trevisan, L., Bounds on the efficiency of generic cryptographic constructions, SIAM J. Comput., 35, 1, 217-246 (2005) · Zbl 1087.94019 · doi:10.1137/S0097539704443276 |
| [25] | Gennaro, R., Trevisan, L.: Lower bounds on the efficiency of generic cryptographic constructions. In: 41st FOCS, pp. 305-313. IEEE Computer Society Press, November 2000 |
| [26] | Gentry, C., Wichs, D.: Separating succinct non-interactive arguments from all falsifiable assumptions. In: Fortnow, L., Vadhan, S.P. (eds.) 43rd ACM STOC, pp. 99-108. ACM Press, June 2011 · Zbl 1288.94063 |
| [27] | Goldreich, O.; Goldwasser, S.; Micali, S.; Blakley, GR; Chaum, D., On the cryptographic applications of random functions (extended abstract), Advances in Cryptology, 276-288 (1985), Heidelberg: Springer, Heidelberg · Zbl 1359.94599 · doi:10.1007/3-540-39568-7_22 |
| [28] | Hefetz, D., Krivelevich, M., Stojakovic, M., Szabó, T.: Positional Games. Birkhäuser Basel (2014) · Zbl 1314.91003 |
| [29] | Hemenway, B.; Jafargholi, Z.; Ostrovsky, R.; Scafuro, A.; Wichs, D.; Robshaw, M.; Katz, J., Adaptively secure garbled circuits from one-way functions, Advances in Cryptology - CRYPTO 2016, 149-178 (2016), Heidelberg: Springer, Heidelberg · Zbl 1406.94063 · doi:10.1007/978-3-662-53015-3_6 |
| [30] | Impagliazzo, R., Rudich, S.: Limits on the provable consequences of one-way permutations. In: 21st ACM STOC, pp. 44-61. ACM Press, May 1989 |
| [31] | Jafargholi, Z.; Kamath, C.; Klein, K.; Komargodski, I.; Pietrzak, K.; Wichs, D.; Katz, J.; Shacham, H., Be adaptive, avoid overcommitting, Advances in Cryptology - CRYPTO 2017, 133-163 (2017), Cham: Springer, Cham · Zbl 1407.94123 · doi:10.1007/978-3-319-63688-7_5 |
| [32] | Jafargholi, Z.; Wichs, D.; Hirt, M.; Smith, A., Adaptive security of Yao’s garbled circuits, Theory of Cryptography, 433-458 (2016), Heidelberg: Springer, Heidelberg · Zbl 1406.94068 · doi:10.1007/978-3-662-53641-4_17 |
| [33] | Kamath, C., Klein, K., Pietrzak, K., Walter, M.: The cost of adaptivity in security games on graphs. Cryptology ePrint Archive, Report 2021/059 (2021). https://eprint.iacr.org/2021/059 |
| [34] | Kamath, C.; Klein, K.; Pietrzak, K.; Wichs, D.; Malkin, T.; Peikert, C., Limits on the adaptive security of Yao’s garbling, Advances in Cryptology - CRYPTO 2021, 486-515 (2021), Cham: Springer, Cham · Zbl 1486.94113 · doi:10.1007/978-3-030-84245-1_17 |
| [35] | Katsumata, S.; Nishimaki, R.; Yamada, S.; Yamakawa, T.; Canteaut, A.; Ishai, Y., Compact NIZKs from standard assumptions on bilinear maps, Advances in Cryptology - EUROCRYPT 2020, 379-409 (2020), Cham: Springer, Cham · Zbl 1531.68035 · doi:10.1007/978-3-030-45727-3_13 |
| [36] | Kiayias, A., Papadopoulos, S., Triandopoulos, N., Zacharias, T.: Delegatable pseudorandom functions and applications. In: Sadeghi, A.-R., Gligor, V.D., Yung, M. (eds.) ACM CCS 2013, pp. 669-684. ACM Press, November 2013 |
| [37] | Kim, J.H., Simon, D.R., Tetali, P.: Limits on the efficiency of one-way permutation-based hash functions. In: 40th FOCS, pp. 535-542. IEEE Computer Society Press, October 1999 |
| [38] | Kowalczyk, L.; Wee, H.; Ishai, Y.; Rijmen, V., Compact adaptively secure ABE for \(\sf NC^1\) from k-Lin, Advances in Cryptology - EUROCRYPT 2019, 3-33 (2019), Cham: Springer, Cham · Zbl 1470.94094 · doi:10.1007/978-3-030-17653-2_1 |
| [39] | Král’ovič, R.; Pacholski, L.; Ružička, P., Time and space complexity of reversible pebbling, SOFSEM 2001: Theory and Practice of Informatics, 292-303 (2001), Heidelberg: Springer, Heidelberg · Zbl 1052.68041 · doi:10.1007/3-540-45627-9_26 |
| [40] | Lewko, A.; Waters, B.; Nguyen, PQ; Oswald, E., Why proving HIBE systems secure is difficult, Advances in Cryptology - EUROCRYPT 2014, 58-76 (2014), Heidelberg: Springer, Heidelberg · Zbl 1326.94109 · doi:10.1007/978-3-642-55220-5_4 |
| [41] | Nielsen, JB; Yung, M., Separating random oracle proofs from complexity theoretic proofs: the non-committing encryption case, Advances in Cryptology — CRYPTO 2002, 111-126 (2002), Heidelberg: Springer, Heidelberg · Zbl 1027.68601 · doi:10.1007/3-540-45708-9_8 |
| [42] | Nordström, J.: New wine into old wineskins: a survey of somepebbling classics with supplemental results (2015) |
| [43] | Panjwani, S.; Vadhan, SP, Tackling adaptive corruptions in multicast encryption protocols, Theory of Cryptography, 21-40 (2007), Heidelberg: Springer, Heidelberg · Zbl 1129.94033 · doi:10.1007/978-3-540-70936-7_2 |
| [44] | Papadimitriou, CH, Games against nature, J. Comput. Syst. Sci., 31, 2, 288-301 (1985) · Zbl 0583.68020 · doi:10.1016/0022-0000(85)90045-5 |
| [45] | Pass, R.; Sahai, A., Unprovable security of perfect NIZK and non-interactive non-malleable commitments, Theory of Cryptography, 334-354 (2013), Heidelberg: Springer, Heidelberg · Zbl 1315.94099 · doi:10.1007/978-3-642-36594-2_19 |
| [46] | Paterson, M.S., Hewitt, C.E.: Comparative schematology. In: Record of the Project MAC Conference on Concurrent Systems and Parallel Computation, pp. 119-127. ACM, New York, NY, USA (1970) |
| [47] | Reingold, O.; Trevisan, L.; Vadhan, S.; Naor, M., Notions of reducibility between cryptographic primitives, Theory of Cryptography, 1-20 (2004), Heidelberg: Springer, Heidelberg · Zbl 1197.94202 · doi:10.1007/978-3-540-24638-1_1 |
| [48] | Rudich, S.: Limits on the provable consequences of one-way functions. Ph.D. thesis, EECS Department, University of California, Berkeley, December 1988 |
| [49] | Savage, J.E.: Models of Computation - Exploring the Power of Computing. Addison-Wesley, Boston (1998) · Zbl 0890.68059 |
| [50] | Simon, DR; Nyberg, K., Finding collisions on a one-way street: can secure hash functions be based on general assumptions?, Advances in Cryptology — EUROCRYPT’98, 334-345 (1998), Heidelberg: Springer, Heidelberg · Zbl 0919.94032 · doi:10.1007/BFb0054137 |
| [51] | Wallner, D.M., Harder, E.J., Agee, R.C.: Key management for multicast: issues and architectures. Internet Draft, September 1998. http://www.ietf.org/ID.html |
| [52] | Wong, CK; Gouda, MG; Lam, SS, Secure group communications using key graphs, IEEE/ACM Trans. Netw., 8, 1, 16-30 (2000) · doi:10.1109/90.836475 |
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.
