Paper 2023/808

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

Benedikt Auerbach, Institute of Science and Technology Austria
Charlotte Hoffmann, Institute of Science and Technology Austria
Guillermo Pascual-Perez, Institute of Science and Technology Austria

The generic-group model (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 GGM lower bounds for one problem to another, by means of conceptually simple reductions. In this work, we propose an alternative approach to extend GGM bounds from one problem to another. Following an idea by Yun (Eurocrypt '15), we show that, in the 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 GGM with preprocessing (more precisely the bit-fixing GGM introduced by Coretti, Dodis and Guo (Crypto '18)). As a consequence, this opens up the possibility of transferring preprocessing 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 (Asiacrypt '22) and Zhandry (Crypto '22) highlight that this is not the case for the AGM approach.

Available format(s)
Publication info
A minor revision of an IACR publication in TCC 2023
generic group modellower boundsdiscrete logarithm problempreprocessing
Contact author(s)
bauerbac @ ista ac at
choffman @ ista ac at
gpascual @ ista ac at
2024-02-19: last of 2 revisions
2023-06-01: received
See all versions
Short URL
Creative Commons Attribution


      author = {Benedikt Auerbach and Charlotte Hoffmann and Guillermo Pascual-Perez},
      title = {Generic-Group Lower Bounds via Reductions Between Geometric-Search Problems: With and Without Preprocessing},
      howpublished = {Cryptology ePrint Archive, Paper 2023/808},
      year = {2023},
      doi = {10.1007/978-3-031-48621-0_11},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.