Paper 2026/384

The Structured Generic-Group Model

Alexandra Henzinger, Massachusetts Institute of Technology

David J. Wu, The University of Texas at Austin

Abstract

This paper introduces the structured generic-group model, an extension of Shoup’s generic-group model (from Eurocrypt 1997) to capture algorithms that take advantage of some non-generic structure of the group. We show that any discrete-log algorithm in a group of prime order $q$ that exploits the structure of at most a $\delta$ fraction of group elements, in a way that we precisely define, must run in time $\Omega(\min(\sqrt{q},1/\delta))$. As an application, we prove a tight subexponential-time lower bound against discrete-log algorithms that exploit the multiplicative structure of smooth integers, but that are otherwise generic. This lower bound applies to a broad class of index-calculus algorithms. We prove similar lower bounds against algorithms that exploit the structure of small integers, smooth polynomials, and elliptic-curve points.

@misc{cryptoeprint:2026/384,
      author = {Henry Corrigan-Gibbs and Alexandra Henzinger and David J. Wu},
      title = {The Structured Generic-Group Model},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/384},
      year = {2026},
      url = {https://eprint.iacr.org/2026/384}
}