Correcting Subverted Random Oracles

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.