Paper 2021/240

The Relationship Between Idealized Models Under Computationally Bounded Adversaries

Mark Zhandry and Cong Zhang

Abstract

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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. Minor revision.
Keywords
IndifferentiabilityRandom oracle modelGeneric Group Model
Contact author(s)
congresearch @ gmail com
czhang20 @ umd edu
mzhandry @ princeton edu
History
2021-03-02: received
Short URL
https://ia.cr/2021/240
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/240,
      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{https://eprint.iacr.org/2021/240}},
      url = {https://eprint.iacr.org/2021/240}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.