The Structured Generic-Group Model

Henry Corrigan-Gibbs, Alexandra Henzinger, and David J. Wu

To appear in: EUROCRYPT
May 10-14, 2026, Rome, Italy

Materials

• IACR ePrint: 2026/384

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.