International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Correcting Subverted Random Oracles

Alexander Russell
Qiang Tang
Moti Yung
Hong-Sheng Zhou
DOI: 10.1007/978-3-319-96881-0_9 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: CRYPTO 2018
Abstract: The random oracle methodology has proven to be a powerful tool for designing and reasoning about cryptographic schemes, and can often act as an effective bridge between theory and practice. In this paper, we focus on the basic problem of correcting faulty—or adversarially corrupted—random oracles, so that they can be confidently applied for such cryptographic purposes.We prove that a simple construction can transform a “subverted” random oracle—which disagrees with the original one at a negligible fraction of inputs—into a construction that is indifferentiable from a random function. Our results permit future designers of cryptographic primitives in typical kleptographic settings (i.e., with adversaries who may subvert the implementation of cryptographic algorithms but undetectable via blackbox testing) to use random oracles as a trusted black box, in spite of not trusting the implementation. Our analysis relies on a general rejection re-sampling lemma which is a tool of possible independent interest.
Video from CRYPTO 2018
  title={Correcting Subverted Random Oracles},
  booktitle={Advances in Cryptology – CRYPTO 2018},
  series={Lecture Notes in Computer Science},
  author={Alexander Russell and Qiang Tang and Moti Yung and Hong-Sheng Zhou},