CryptoDB
Correcting Subverted Random Oracles
| Authors: | |
|---|---|
| Download: |
|
| 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
BibTeX
@inproceedings{crypto-2018-28840,
title={Correcting Subverted Random Oracles},
booktitle={Advances in Cryptology – CRYPTO 2018},
series={Lecture Notes in Computer Science},
publisher={Springer},
volume={10992},
pages={241-271},
doi={10.1007/978-3-319-96881-0_9},
author={Alexander Russell and Qiang Tang and Moti Yung and Hong-Sheng Zhou},
year=2018
}