Paper 2026/384
The Structured Generic-Group Model
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.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- A major revision of an IACR publication in EUROCRYPT 2026
- Contact author(s)
-
henrycg @ cs berkeley edu
ahenz @ csail mit edu
dwu4 @ cs utexas edu - History
- 2026-02-26: approved
- 2026-02-24: received
- See all versions
- Short URL
- https://ia.cr/2026/384
- License
-
CC BY
BibTeX
@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}
}
