Welcome to the resource topic for 2021/240
Title:
The Relationship Between Idealized Models Under Computationally Bounded Adversaries
Authors: Mark Zhandry, 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.
ePrint: https://eprint.iacr.org/2021/240
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .