Abstract
The Fuchsbauer, Kiltz, and Loss (Crypto 2018) claim that (some) hardness results in the algebraic group model imply the same hardness results in the generic group model was recently called into question by Katz, Zhang, and Zhou (Asiacrypt 2022). The latter gave an interpretation of the claim under which it is incorrect. We give an alternate interpretation under which it is correct, using natural frameworks for capturing generic and algebraic models for arbitrary algebraic structures. Most algebraic analyses in the literature can be captured by our frameworks, making the claim correct for them.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Recall that Shoup’s GGM treats each group element as uniquely represented by a string (chosen either at random or in the “worst-case”). Maurer’s GGM has no unique representations; group elements are instead referenced using (non-unique) pointers into a table. In either case, oracles are provided for performing group operations.
- 2.
- 3.
The standard (and algebraic) model quantifies the encoding function before algorithms are chosen and restrict attention to encodings from which group operations can be efficiently computed. The type-safe model is independent of the encoding.
- 4.
We use this for relating our notion of algebraic with that of FKL.
- 5.
The last is perhaps not as philosophically relevant, but in practice certainly plays a role in which models are used.
- 6.
We loosely think here of “bug” as a catchall term for any sort of gap, error, omission, imprecision, etc. in analysis.
- 7.
We sometimes discuss examples from previous works that do not distinguish between group elements and the bitstring representation. We then follow the notational convention of the work.
- 8.
Here we are paraphrasing FKL and make no claims about the precise intended interpretation of this phrase.
- 9.
Note that \(B^{2b-1}\in \{B,B^{-1}\}\).
- 10.
Shoup-style generic models will change this assumption of how \(U.\sigma \) is quantified, either at random or in the worst case. In this setting, it is less confusing to refer to unrestricted, rather than standard algorithms.
- 11.
We refer to them both as “standard” and “unrestricted” to avoid Shoup generic models using “standard” algorithms.
- 12.
Note that input \(X'\) is a bitstring, not a group element.
- 13.
We typically think of \(U.\sigma \) quantified before algebraic algorithms. Quantifying the reduction first makes for a stronger statement.
- 14.
Assume it sets \(a_2=0\) if there is only one solution and \(a_1=0\) if there are none.
- 15.
Asymptotically, if the \(\varDelta \)’s are polynomial and \(\varepsilon \) is negligible whenever \(\mathcal {A}\) is polynomially efficient.
References
Agrikola, T., Hofheinz, D., Kastner, J.: On instantiating the algebraic group model from falsifiable assumptions. In: Canteaut, A., Ishai, Y. (eds.) EUROCRYPT 2020. LNCS, vol. 12106, pp. 96–126. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-45724-2_4
Bacho, R., Loss, J.: On the adaptive security of the threshold BLS signature scheme. In: Yin, H., Stavrou, A., Cremers, C., Shi, E. (eds.) ACM CCS 2022, pp. 193–207. ACM Press, Los Angeles, CA, USA (2022). https://doi.org/10.1145/3548606.3560656
Barkan-Vered, W., Harding, F., Keller, J., Xu, J.: On the non-malleability of ECVRF in the algebraic group model. Cryptology ePrint Archive, Paper 2023/1004 (2023). https://eprint.iacr.org/2023/1004
Bauer, B., Fuchsbauer, G., Loss, J.: A classification of computational assumptions in the algebraic group model. In: Micciancio, D., Ristenpart, T. (eds.) CRYPTO 2020. LNCS, vol. 12171, pp. 121–151. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-56880-1_5
Bellare, M., Rogaway, P.: The security of triple encryption and a framework for code-based game-playing proofs. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 409–426. Springer, Heidelberg (2006). https://doi.org/10.1007/11761679_25
Canetti, R., Goldreich, O., Halevi, S.: The random oracle methodology, revisited (preliminary version). In: 30th ACM STOC, pp. 209–218. ACM Press, Dallas, TX, USA (1998). https://doi.org/10.1145/276698.276741
Couteau, G., Hartmann, D.: Shorter non-interactive zero-knowledge arguments and ZAPs for algebraic languages. In: Micciancio, D., Ristenpart, T. (eds.) CRYPTO 2020. LNCS, vol. 12172, pp. 768–798. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-56877-1_27
Dent, A.W.: Adapting the weaknesses of the random oracle model to the generic group model. In: Zheng, Y. (ed.) ASIACRYPT 2002. LNCS, vol. 2501, pp. 100–109. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-36178-2_6
Diffie, W., Hellman, M.E.: New directions in cryptography. IEEE Trans. Inf. Theory 22(6), 644–654 (1976). https://doi.org/10.1109/TIT.1976.1055638
Döttling, N., Hartmann, D., Hofheinz, D., Kiltz, E., Schäge, S., Ursu, B.: On the impossibility of purely algebraic signatures. In: Nissim, K., Waters, B. (eds.) TCC 2021. LNCS, vol. 13044, pp. 317–349. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-90456-2_11
Ducas, L.: Conception of a language for cryptographic reductions. Master thesis, in french (2009). https://homepages.cwi.nl/~ducas/stage2009/
Duman, J., Hartmann, D., Kiltz, E., Kunzweiler, S., Lehmann, J., Riepel, D.: Generic models for group actions. In: Boldyreva, A., Kolesnikov, V. (eds.) PKC 2023, Part I. LNCS, vol. 13940, pp. 406–435. Springer, Heidelberg, Germany, Atlanta, GA, USA (2023). https://doi.org/10.1007/978-3-031-31368-4_15
Fuchsbauer, G., Kiltz, E., Loss, J.: The algebraic group model and its applications. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018. LNCS, vol. 10992, pp. 33–62. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-96881-0_2
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. LNCS, vol. 12106, pp. 63–95. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-45724-2_3
Jager, T., Schwenk, J.: On the Equivalence of generic group models. In: Baek, J., Bao, F., Chen, K., Lai, X. (eds.) ProvSec 2008. LNCS, vol. 5324, pp. 200–209. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-88733-1_14
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, Germany, Virtual Event (2022). https://doi.org/10.1007/978-3-030-97131-1_16
Maurer, U.: Abstract models of computation in cryptography. In: Smart, N.P. (ed.) Cryptography and Coding 2005. LNCS, vol. 3796, pp. 1–12. Springer, Heidelberg (2005). https://doi.org/10.1007/11586821_1
Meier, L.: Idealized models for free (podcast) (2023). https://cronokirby.substack.com/p/idealized-models-for-free
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_1
Ristenpart, T., Shacham, H., Shrimpton, T.: Careful with composition: limitations of the indifferentiability framework. In: Paterson, K.G. (ed.) EUROCRYPT 2011. LNCS, vol. 6632, pp. 487–506. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-20465-4_27
Rotem, L., Segev, G., Shahaf, I.: Generic-group delay functions require hidden-order groups. In: Canteaut, A., Ishai, Y. (eds.) EUROCRYPT 2020. LNCS, vol. 12107, pp. 155–180. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-45727-3_6
Schul-Ganz, G., Segev, G.: Accumulators in (and beyond) generic groups: non-trivial batch verification requires interaction. In: Pass, R., Pietrzak, K. (eds.) TCC 2020. LNCS, vol. 12551, pp. 77–107. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-64378-2_4
Schul-Ganz, G., Segev, G.: Generic-group identity-based encryption: a tight impossibility result. In: Tessaro, S. (ed.) 2nd Conference on Information-Theoretic Cryptography (ITC 2021). Leibniz International Proceedings in Informatics (LIPIcs), vol. 199, pp. 26:1–26:23. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany (2021). https://doi.org/10.4230/LIPIcs.ITC.2021.26
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_18
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, Germany, Santa Barbara, CA, USA (2022). https://doi.org/10.1007/978-3-031-15982-4_3
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, Germany, Taipei, Taiwan (2022). https://doi.org/10.1007/978-3-031-22972-5_11
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2024 International Association for Cryptologic Research
About this paper
Cite this paper
Jaeger, J., Mohan, D.I. (2024). Generic and Algebraic Computation Models: When AGM Proofs Transfer to the GGM. In: Reyzin, L., Stebila, D. (eds) Advances in Cryptology – CRYPTO 2024. CRYPTO 2024. Lecture Notes in Computer Science, vol 14924. Springer, Cham. https://doi.org/10.1007/978-3-031-68388-6_2
Download citation
DOI: https://doi.org/10.1007/978-3-031-68388-6_2
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-68387-9
Online ISBN: 978-3-031-68388-6
eBook Packages: Computer ScienceComputer Science (R0)
