Paper 2020/1144

Algebraic Distinguishers: From Discrete Logarithms to Decisional Uber Assumptions

Lior Rotem and Gil Segev


The algebraic group model, introduced by Fuchsbauer, Kiltz and Loss (CRYPTO '18), is a substantial relaxation of the generic group model capturing algorithms that may exploit the representation of the underlying group. This idealized yet realistic model was shown useful for reasoning about cryptographic assumptions and security properties defined via computational problems. However, it does not generally capture assumptions and properties defined via decisional problems. As such problems play a key role in the foundations and applications of cryptography, this leaves a significant gap between the restrictive generic group model and the standard model. We put forward the notion of algebraic distinguishers, strengthening the algebraic group model by enabling it to capture decisional problems. Within our framework we then reveal new insights on the algebraic interplay between a wide variety of decisional assumptions. These include the decisional Diffie-Hellman assumption, the family of Linear assumptions in multilinear groups, and the family of Uber assumptions in bilinear groups. Our main technical results establish that, from an algebraic perspective, these decisional assumptions are in fact all polynomially equivalent to either the most basic discrete logarithm assumption or to its higher-order variant, the $q$-discrete logarithm assumption. On the one hand, these results increase the confidence in these strong decisional assumptions, while on the other hand, they enable to direct cryptanalytic efforts towards either extracting discrete logarithms or significantly deviating from standard algebraic techniques.

Available format(s)
Publication info
A major revision of an IACR publication in TCC 2020
Algebraic Group ModelGeneric Group ModelDiscrete LogAssumptions
Contact author(s)
lior rotem @ cs huji ac il
2020-09-25: last of 3 revisions
2020-09-21: received
See all versions
Short URL
Creative Commons Attribution


      author = {Lior Rotem and Gil Segev},
      title = {Algebraic Distinguishers: From Discrete Logarithms to Decisional Uber Assumptions},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1144},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.