nach oben

Erschienen in:

2023 | OriginalPaper | Buchkapitel

Generic-Group Lower Bounds via Reductions Between Geometric-Search Problems: With and Without Preprocessing

verfasst von : Benedikt Auerbach, Charlotte Hoffmann, Guillermo Pascual-Perez

Erschienen in: Theory of Cryptography

Verlag: Springer Nature Switzerland

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

The generic-group model (\( \textrm{GGM}\)) aims to capture algorithms working over groups of prime order that only rely on the group operation, but do not exploit any additional structure given by the concrete implementation of the group. In it, it is possible to prove information-theoretic lower bounds on the hardness of problems like the discrete logarithm (DL) or computational Diffie-Hellman (CDH). Thus, since its introduction, it has served as a valuable tool to assess the concrete security provided by cryptographic schemes based on such problems. A work on the related algebraic-group model (AGM) introduced a method, used by many subsequent works, to adapt \( \textrm{GGM}\) lower bounds for one problem to another, by means of conceptually simple reductions.

In this work, we propose an alternative approach to extend \( \textrm{GGM}\) bounds from one problem to another. Following an idea by Yun [EC15], we show that, in the \( \textrm{GGM}\), the security of a large class of problems can be reduced to that of geometric search-problems. By reducing the security of the resulting geometric-search problems to variants of the search-by-hypersurface problem, for which information theoretic lower bounds exist, we give alternative proofs of several results that used the AGM approach.

The main advantage of our approach is that our reduction from geometric search-problems works, as well, for the \(\textrm{GGM}\) with preprocessing (more precisely the bit-fixing \( \textrm{GGM}\) introduced by Coretti, Dodis and Guo [Crypto18]). As a consequence, this opens up the possibility of transferring preprocessing \( \textrm{GGM}\) bounds from one problem to another, also by means of simple reductions. Concretely, we prove novel preprocessing bounds on the hardness of the d-strong discrete logarithm, the d-strong Diffie-Hellman inversion, and multi-instance CDH problems, as well as a large class of Uber assumptions. Additionally, our approach applies to Shoup’s GGM without additional restrictions on the query behavior of the adversary, while the recent works of Zhang, Zhou, and Katz [AC22] and Zhandry [Crypto22] highlight that this is not the case for the AGM approach.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel On the Cost of Post-compromise Security in Concurrent Continuous Group-Key Agreement

Nächstes Kapitel Holographic SNARGs for P and Batch-NP from (Polynomially Hard) Learning with Errors

We refer to these problems as geometric search-problems, since queries of this type can be seen as testing whether the hypersurface in \( \mathbb {Z}_p^t \) defined by \( \hat{F} \) contains \( \vec {x} \) or not.

Alternatively, one could also make this requirement explicit by changing the inputs to \( \textrm{Eval}\) to be a vector \( (a_0,\dots ,a_k)\in \mathbb {Z}_p^k \) and return whether \( \vec {x} \) lies on the hypersurface defined by \( a_0+\sum _{i=1}^k a_iF_i \). The requirement for solutions \( \hat{F}_i \) could be adapted accordingly.

As is the case for \( \textrm{Eval}\), oracle \( \textrm{Dec}\) corresponds to evaluating containment in a hypersurface, albeit, one of degree possibly higher than the ones in the linear span of the input polynomials. Thus, one could incorporate \( \textrm{Dec}_{W_i} \) into \( \textrm{Eval}\) by expanding the range of admissible polynomials for the latter from \( \textrm{Span}(1,F_1,\dots ,F_k) \) to also include polynomials of the form \( W_i(F'_1,\dots ,F'_{s_i})\in \mathbb {Z}_p[X_1,\dots ,X_t] \) for \( F'_j\in \textrm{Span}(1,F_1,\dots ,F_k) \). However, we decided to keep the oracles separated in order to have a clearer conceptual distinction between the group-operation oracle and decisional oracles.

We measure the running time of generic algorithms by their query count. So, both sampling from \( \mathcal {R}\) and checking whether \( \sigma \in \mathcal {R}\) need not be efficiently computable. We use this approach for ease of exposition, but point out that these operations can easily be adapted to be done efficiently by sampling \( \mathcal {R}\) on the fly.

Abdalla, M., Barbosa, M., Bradley, T., Jarecki, S., Katz, J., Xu, J.: Universally composable relaxed password authenticated key exchange. In: Micciancio, D., Ristenpart, T. (eds.) CRYPTO 2020, Part I. LNCS, vol. 12170, pp. 278–307. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-56784-2_10CrossRef

Auerbach, B., Giacon, F., Kiltz, E.: Everybody’s a target: scalability in public-key encryption. In: Canteaut, A., Ishai, Y. (eds.) EUROCRYPT 2020, Part III. LNCS, vol. 12107, pp. 475–506. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-45727-3_16CrossRefMATH

Auerbach, B., Hoffmann, C., Pascual-Perez, G.: Generic-group lower bounds via reductions between geometric-search problems: With and without preprocessing. Cryptology ePrint Archive, Paper 2023/808 (2023). https://eprint.iacr.org/2023/808

Bauer, B., Farshim, P., Harasser, P., O’Neill, A.: Beyond Uber: instantiating generic groups via PGGs. In: Kiltz, E., Vaikuntanathan, V. (eds.) TCC 2022, Part III. LNCS, vol. 13749, pp. 212–242. Springer, Heidelberg (Nov (2022). https://doi.org/10.1007/978-3-031-22368-6_8CrossRef

Bauer, B., Fuchsbauer, G., Loss, J.: A classification of computational assumptions in the algebraic group model. In: Micciancio, D., Ristenpart, T. (eds.) CRYPTO 2020, Part III. LNCS, vol. 12171, pp. 121–151. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-56880-1_5CrossRefMATH

Bernstein, D.J., Lange, T.: Non-uniform cracks in the concrete: the power of free precomputation. In: Sako, K., Sarkar, P. (eds.) ASIACRYPT 2013, Part II. LNCS, vol. 8270, pp. 321–340. Springer, Heidelberg (Dec (2013)CrossRef

Blocki, J., Lee, S.: On the multi-user security of short Schnorr signatures with preprocessing. In: Dunkelman, O., Dziembowski, S. (eds.) EUROCRYPT 2022, Part II. LNCS, vol. 13276, pp. 614–643. Springer, Heidelberg (May / Jun (2022). https://doi.org/10.1007/978-3-031-07085-3_21CrossRef

Boneh, D., Boyen, X.: Efficient selective-ID secure identity based encryption without random oracles. In: Cachin, C., Camenisch, J. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 223–238. Springer, Heidelberg (May (2004). https://doi.org/10.1007/978-3-540-24676-3_14CrossRef

Boneh, D., Boyen, X.: Short signatures without random oracles. In: Cachin, C., Camenisch, J. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 56–73. Springer, Heidelberg (May (2004). https://doi.org/10.1007/978-3-540-24676-3_4CrossRef

10.

Boneh, D., Boyen, X., Goh, E.-J.: Hierarchical identity based encryption with constant size ciphertext. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 440–456. Springer, Heidelberg (2005). https://doi.org/10.1007/11426639_26CrossRef

11.

Boneh, D., Lynn, B., Shacham, H.: Short signatures from the Weil pairing. J. Cryptol. 17(4), 297–319 (2004)MathSciNetCrossRefMATH

12.

Boneh, D., Venkatesan, R.: Breaking RSA may not be equivalent to factoring. In: Nyberg, K. (ed.) EUROCRYPT 1998. LNCS, vol. 1403, pp. 59–71. Springer, Heidelberg (1998). https://doi.org/10.1007/BFb0054117CrossRef

13.

Boyen, X.: The uber-assumption family (invited talk). In: Galbraith, S.D., Paterson, K.G. (eds.) PAIRING 2008. LNCS, vol. 5209, pp. 39–56. Springer, Heidelberg (Sep (2008). https://doi.org/10.1007/978-3-540-85538-5_3CrossRef

14.

Coretti, S., Dodis, Y., Guo, S.: Non-uniform bounds in the random-permutation, ideal-cipher, and generic-group models. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018, Part I. LNCS, vol. 10991, pp. 693–721. Springer, Heidelberg (Aug (2018). https://doi.org/10.1007/978-3-319-96884-1_23CrossRefMATH

15.

Corrigan-Gibbs, H., Kogan, D.: The discrete-logarithm problem with preprocessing. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018, Part II. LNCS, vol. 10821, pp. 415–447. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78375-8_14CrossRef

16.

Fuchsbauer, G., Kiltz, E., Loss, J.: The algebraic group model and its applications. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018, Part II. LNCS, vol. 10992, pp. 33–62. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-96881-0_2CrossRef

17.

Fuchsbauer, G., Plouviez, A., Seurin, Y.: Blind Schnorr signatures and signed ElGamal encryption in the algebraic group model. In: Canteaut, A., Ishai, Y. (eds.) EUROCRYPT 2020, Part II. LNCS, vol. 12106, pp. 63–95. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-45724-2_3CrossRefMATH

18.

Ghoshal, A., Tessaro, S.: State-restoration soundness in the algebraic group model. In: Malkin, T., Peikert, C. (eds.) CRYPTO 2021, Part III. LNCS, vol. 12827, pp. 64–93. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-84252-9_3CrossRefMATH

19.

Kastner, J., Loss, J., Xu, J.: On pairing-free blind signature schemes in the algebraic group model. In: Hanaoka, G., Shikata, J., Watanabe, Y. (eds.) PKC 2022, Part II. LNCS, vol. 13178, pp. 468–497. Springer, Heidelberg (Mar (2022). https://doi.org/10.1007/978-3-030-97131-1_16CrossRef

20.

Lee, H.T., Cheon, J.H., Hong, J.: Accelerating ID-based encryption based on trapdoor DL using pre-computation. Cryptology ePrint Archive, Paper 2011/187 (2011). https://eprint.iacr.org/2011/187

21.

Maurer, U.M.: Abstract models of computation in cryptography (invited paper). In: Smart, N.P. (ed.) Cryptography and Coding 2005. LNCS, vol. 3796, pp. 1–12. Springer, Heidelberg (Dec (2005). https://doi.org/10.1007/11586821_1CrossRefMATH

22.

Mihalcik, J.P.: An analysis of algorithms for solving discrete logarithms in fixed groups. Master’s thesis, Naval Postgraduate School (2010). https://calhoun.nps.edu/bitstream/handle/10945/5395/10Mar_Mihalcik.pdf

23.

Mizuide, T., Takayasu, A., Takagi, T.: Tight reductions for Diffie-Hellman variants in the algebraic group model. In: Matsui, M. (ed.) CT-RSA 2019. LNCS, vol. 11405, pp. 169–188. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-12612-4_9CrossRefMATH

24.

Okamoto, T., Pointcheval, D.: The gap-problems: a new class of problems for the security of cryptographic schemes. In: Kim, K. (ed.) PKC 2001. LNCS, vol. 1992, pp. 104–118. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-44586-2_8CrossRef

25.

Paillier, P., Vergnaud, D.: Discrete-log-based signatures may not be equivalent to discrete log. In: Roy, B. (ed.) ASIACRYPT 2005. LNCS, vol. 3788, pp. 1–20. Springer, Heidelberg (2005). https://doi.org/10.1007/11593447_1CrossRef

26.

Rotem, L., Segev, G.: Algebraic distinguishers: from discrete logarithms to decisional uber assumptions. In: Pass, R., Pietrzak, K. (eds.) TCC 2020, Part III. LNCS, vol. 12552, pp. 366–389. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-64381-2_13CrossRef

27.

Rupp, A., Leander, G., Bangerter, E., Dent, A.W., Sadeghi, A.-R.: Sufficient conditions for intractability over black-box groups: generic lower bounds for generalized DL and DH problems. In: Pieprzyk, J. (ed.) ASIACRYPT 2008. LNCS, vol. 5350, pp. 489–505. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-89255-7_30CrossRef

28.

Shoup, V.: Lower bounds for discrete logarithms and related problems. In: Fumy, W. (ed.) EUROCRYPT 1997. LNCS, vol. 1233, pp. 256–266. Springer, Heidelberg (1997). https://doi.org/10.1007/3-540-69053-0_18CrossRef

29.

Unruh, D.: Random oracles and auxiliary input. In: Menezes, A. (ed.) CRYPTO 2007. LNCS, vol. 4622, pp. 205–223. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-74143-5_12CrossRef

30.

Ying, J.H.M., Kunihiro, N.: Bounds in various generalized settings of the discrete logarithm problem. In: Gollmann, D., Miyaji, A., Kikuchi, H. (eds.) ACNS 2017. LNCS, vol. 10355, pp. 498–517. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-61204-1_25CrossRef

31.

Yun, A.: Generic hardness of the multiple discrete logarithm problem. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015, Part II. LNCS, vol. 9057, pp. 817–836. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46803-6_27CrossRef

32.

Zhandry, M.: To label, or not to label (in generic groups). In: Dodis, Y., Shrimpton, T. (eds.) CRYPTO 2022, Part III. LNCS, vol. 13509, pp. 66–96. Springer, Heidelberg (Aug (2022). https://doi.org/10.1007/978-3-031-15982-4_3CrossRefMATH

33.

Zhang, C., Zhou, H.S., Katz, J.: An analysis of the algebraic group model. In: Agrawal, S., Lin, D. (eds.) ASIACRYPT 2022, Part IV. LNCS, vol. 13794, pp. 310–322. Springer, Heidelberg (Dec (2022). https://doi.org/10.1007/978-3-031-22972-5_11CrossRef

Titel: Generic-Group Lower Bounds via Reductions Between Geometric-Search Problems: With and Without Preprocessing
verfasst von: Benedikt Auerbach
Charlotte Hoffmann
Guillermo Pascual-Perez
Verlag: Springer Nature Switzerland
Buch: Theory of Cryptography
Print ISBN: 978-3-031-48620-3

Electronic ISBN: 978-3-031-48621-0

Copyright-Jahr: 2023
DOI: https://doi.org/10.1007/978-3-031-48621-0_11

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner