TY - GEN
T1 - Correcting subverted random oracles
AU - Russell, Alexander
AU - Tang, Qiang
AU - Yung, Moti
AU - Zhou, Hong Sheng
N1 - Publisher Copyright:
© 2018, International Association for Cryptologic Research.
PY - 2018
Y1 - 2018
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85052373454&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85052373454&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-96881-0_9
DO - 10.1007/978-3-319-96881-0_9
M3 - Conference contribution
AN - SCOPUS:85052373454
SN - 9783319968803
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 241
EP - 271
BT - Advances in Cryptology – CRYPTO 2018 - 38th Annual International Cryptology Conference, 2018, Proceedings
A2 - Boldyreva, Alexandra
A2 - Shacham, Hovav
PB - Springer Verlag
T2 - 38th Annual International Cryptology Conference, CRYPTO 2018
Y2 - 19 August 2018 through 23 August 2018
ER -