Correcting subverted random oracles

Alexander Russell, Qiang Tang, Moti Yung, Hong Sheng Zhou

Research output: Chapter in Book/Report/Conference proceedingConference contribution

18 Scopus citations


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.

Original languageEnglish (US)
Title of host publicationAdvances in Cryptology – CRYPTO 2018 - 38th Annual International Cryptology Conference, 2018, Proceedings
EditorsAlexandra Boldyreva, Hovav Shacham
PublisherSpringer Verlag
Number of pages31
ISBN (Print)9783319968803
StatePublished - 2018
Event38th Annual International Cryptology Conference, CRYPTO 2018 - Santa Barbara, United States
Duration: Aug 19 2018Aug 23 2018

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10992 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other38th Annual International Cryptology Conference, CRYPTO 2018
Country/TerritoryUnited States
CitySanta Barbara

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Correcting subverted random oracles'. Together they form a unique fingerprint.

Cite this