Paper 2023/1504
Algebraic Group Model with Oblivious Sampling
, University of Tartu, Simula UiB, Norway, Simula UiB, NorwayAbstract
In the algebraic group model (AGM), an adversary has to return with each group element a linear representation with respect to input group elements. In many groups, it is easy to sample group elements obliviously without knowing such linear representations. Since the AGM does not model this, it can be used to prove the security of spurious knowledge assumptions. We show several well-known zk-SNARKs use such assumptions. We propose AGM with oblivious sampling (AGMOS), an AGM variant where the adversary can access an oracle that allows sampling group elements obliviously from some distribution. We show that AGM and AGMOS are different by studying the family of ``total knowledge-of-exponent'' assumptions, showing that they are all secure in the AGM, but most are not secure in the AGMOS if the DL holds. We show an important separation in the case of the KZG commitment scheme. We show that many known AGM reductions go through also in the AGMOS, assuming a novel falsifiable assumption TOFR. We prove that TOFR is secure in a version of GGM with oblivious sampling.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- A major revision of an IACR publication in TCC 2023
- Keywords
- Admissible encodingalgebraic group modelelliptic-curve hashingFindRepKZG extractablityoblivious sampling
- Contact author(s)
-
helger lipmaa @ gmail com
robertoparisella @ hotmail it
jannosiim @ gmail com - History
- 2023-10-03: approved
- 2023-10-02: received
- See all versions
- Short URL
- https://ia.cr/2023/1504
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2023/1504,
author = {Helger Lipmaa and Roberto Parisella and Janno Siim},
title = {Algebraic Group Model with Oblivious Sampling},
howpublished = {Cryptology ePrint Archive, Paper 2023/1504},
year = {2023},
note = {\url{https://eprint.iacr.org/2023/1504}},
url = {https://eprint.iacr.org/2023/1504}
}
