Paper 2021/240

The Relationship Between Idealized Models Under Computationally Bounded Adversaries

Mark Zhandry and Cong Zhang


The random oracle, generic group, and generic bilinear map models (ROM, GGM, GBM, respectively) are fundamental heuristics used to justify new computational assumptions and prove the security of efficient cryptosystems. While known to be invalid in some contrived settings, the heuristics generally seem reasonable for real-world applications. In this work, we ask: \emph{which heuristics are closer to reality?} Or conversely, which heuristics are a larger leap? We answer this question through the framework of computational indifferentiability, showing that the ROM is a strictly ``milder'' heuristic than the GGM, which in turn is strictly milder than the GBM. While this may seem like the expected outcome, we explain why it does not follow from prior works and is not the a priori obvious conclusion. In order to prove our results, we develop new ideas for proving computational indifferentiable separations.

Available format(s)
Publication info
Preprint. Minor revision.
IndifferentiabilityRandom oracle modelGeneric Group Model
Contact author(s)
congresearch @ gmail com
czhang20 @ umd edu
mzhandry @ princeton edu
2021-03-02: received
Short URL
Creative Commons Attribution


      author = {Mark Zhandry and Cong Zhang},
      title = {The Relationship Between Idealized Models Under Computationally Bounded Adversaries},
      howpublished = {Cryptology ePrint Archive, Paper 2021/240},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.