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
-
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},
url = {https://eprint.iacr.org/2021/240}
}
