Random Oracles With(out) Programmability
Marc Fischlin, Anja Lehmann, Thomas Ristenpart, Thomas Shrimpton, Martijn Stam, and Stefano Tessaro
This paper investigates the Random Oracle Model (ROM) feature known as programmability, which allows security reductions in the ROM to dynamically choose the range points of an ideal hash function. This property is interesting for at least two reasons: first, because of its seeming artificiality (no standard model hash function is known to support such adaptive programming); second, the only known security reductions for many important cryptographic schemes rely fundamentally on programming. We provide formal tools to study the role of programmability in provable security. This includes a framework describing three levels of programming in reductions (none, limited, and full). We then prove that no black-box reductions can be given for FDH signatures when only limited programming is allowed, giving formal support for the intuition that full programming is fundamental to the provable security of FDH. We also show that Shoup's trapdoor-permutation-based key-encapsulation is provably CCA-secure with limited programmability, but no black-box reduction succeeds when no programming at all is permitted. Our negative results use a new concrete-security variant of Hsiao and Reyzin's two-oracle separation technique.
BibTeX Citation
@inproceedings{FLRSST10,
author = {Marc Fischlin and Anja Lehmann and Thomas Ristenpart and Thomas Shrimpton and Martijn Stam and Stefano Tessaro},
title = {Random Oracles With(out) Programmability},
editor = {Masayuki Abe},
booktitle = {Advances in Cryptology --- ASIACRYPT 2010},
pages = 303--320,
series = {Lecture Notes in Computer Science},
volume = 6477,
year = 2010,
month = 12,
publisher = {Springer-Verlag},
}