Paper 2026/384 Original: eprint.iacr.org/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
- Preprint.
- History
- 2026-02-24: last updated
- 2026-02-24: published
- Short URL
- https://ia.cr/2026/384
- License
- https://creativecommons.org/licenses/by/4.0/
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}
}