Paper 2023/1601
The Uber-Knowledge Assumption: A Bridge to the AGM
Abstract
The generic-group model (GGM) and the algebraic-group model (AGM) have been exceptionally successful in proving the security of many classical and modern cryptosystems. These models, however, come with standard-model uninstantiability results, raising the question whether the schemes analyzed under them can be based on firmer standard-model footing. We formulate the uber-knowledge (UK) assumption, a standard-model assumption that naturally extends the uber-assumption family to knowledge-type problems. We justify the soundness of the UK assumption in both the bilinear GGM and the bilinear AGM. Along the way we extend these models to account for hashing into groups, an adversarial capability that is available in many concrete groups---In contrast to standard assumptions, hashing may affect the validity of knowledge assumptions. These results, in turn, enable a modular approach to security in the GGM and the AGM. As example applications, we use the UK assumption to prove knowledge soundness of Groth16 and of KZG polynomial commitments in the standard model, where for the former we reuse the existing proof in the AGM without hashing.
Note: Corrected claims that the uber-knowledge assumption implies several other knowledge assumptions, and provided formal proofs.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Preprint.
- Keywords
- Knowledge assumptionStandard modelGeneric-group modelAlgebraic-group modelGroth16KZG commitment
- Contact author(s)
-
balthazar bauer @ ens fr
pooya farshim @ gmail com
patrick harasser @ tu-darmstadt de
mkohlwei @ ed ac uk - History
- 2024-03-13: last of 2 revisions
- 2023-10-16: received
- See all versions
- Short URL
- https://ia.cr/2023/1601
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2023/1601,
author = {Balthazar Bauer and Pooya Farshim and Patrick Harasser and Markulf Kohlweiss},
title = {The Uber-Knowledge Assumption: A Bridge to the {AGM}},
howpublished = {Cryptology {ePrint} Archive, Paper 2023/1601},
year = {2023},
url = {https://eprint.iacr.org/2023/1601}
}
