### On Instantiating the Algebraic Group Model from Falsifiable Assumptions

Thomas Agrikola, Dennis Hofheinz, and Julia Kastner

##### Abstract

We provide a standard-model implementation (of a relaxation) of the algebraic group model (AGM, [Fuchsbauer, Kiltz, Loss, CRYPTO 2018]). Specifically, we show that every algorithm that uses our group is algebraic, and hence must know'' a representation of its output group elements in terms of its input group elements. Here, must know'' means that a suitable extractor can extract such a representation efficiently. We stress that our implementation relies only on falsifiable assumptions in the standard model, and in particular does not use any knowledge assumptions. As a consequence, our group allows to transport a number of results obtained in the AGM into the standard model, under falsifiable assumptions. For instance, we show that in our group, several Diffie-Hellman-like assumptions (including computational Diffie-Hellman) are equivalent to the discrete logarithm assumption. Furthermore, we show that our group allows to prove the Schnorr signature scheme tightly secure in the random oracle model. Our construction relies on indistinguishability obfuscation, and hence should not be considered as a practical group itself. However, our results show that the AGM is a realistic computational model (since it can be instantiated in the standard model), and that results obtained in the AGM are also possible with standard-model groups.

Note: Corrected some typos.

Available format(s)
Category
Foundations
Publication info
A major revision of an IACR publication in EUROCRYPT 2020
Keywords
indistinguishability obfuscationalgebraic group modelSchnorr signatures
Contact author(s)
thomas agrikola @ gmail com
thomas agrikola @ kit edu
julia kastner @ inf ethz ch
History
2020-04-09: last of 3 revisions
See all versions
Short URL
https://ia.cr/2020/070

CC BY

BibTeX

@misc{cryptoeprint:2020/070,
author = {Thomas Agrikola and Dennis Hofheinz and Julia Kastner},
title = {On Instantiating the Algebraic Group Model from Falsifiable Assumptions},
howpublished = {Cryptology ePrint Archive, Paper 2020/070},
year = {2020},
note = {\url{https://eprint.iacr.org/2020/070}},
url = {https://eprint.iacr.org/2020/070}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.