International Association for Cryptologic Research

International Association
for Cryptologic Research


Algebraic Group Model with Oblivious Sampling

Helger Lipmaa , University of Tartu, Tartu, Estonia
Roberto Parisella , Simula UiB
Janno Siim , Simula UiB
Search ePrint
Search Google
Presentation: Slides
Conference: TCC 2023
Abstract: 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 propose AGM with oblivious sampling (AGMOS), a variant of the AGM where the adversary has additional access to an oracle that allows sampling group elements obliviously from some distribution. We separate AGM and AGMOS by classifying the family of ``total knowledge-of-exponent'' assumptions, showing that while they are all secure in the AGM (even insecure ones), most are not secure in the AGMOS if the DL holds. 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.
  title={Algebraic Group Model with Oblivious Sampling},
  author={Helger Lipmaa and Roberto Parisella and Janno Siim},