Random Oracles and Auxiliary Input

Dominique Unruh

Paper 2007/168

Random Oracles and Auxiliary Input

Dominique Unruh

Abstract

We introduce a variant of the random oracle model where oracle-dependent auxiliary input is allowed. In this setting, the adversary gets an auxiliary input that can contain information about the random oracle. Using simple examples we show that this model should be preferred over the classical variant where the auxiliary input is independent of the random oracle. In the presence of oracle-dependent auxiliary input, the most important proof technique in the random oracle model - lazy sampling - does not apply directly. We present a theorem and a variant of the lazy sampling technique that allows one to perform proofs in the new model almost as easily as in the old one. As an application of our approach and to illustrate how existing proofs can be adapted, we prove that RSA-OAEP is IND-CCA2 secure in the random oracle model with oracle-dependent auxiliary input.

Note: Minor corrections due to referee comments.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Published elsewhere. This is the full version of a paper appearing at Crypto 2007
Keywords: Random oracles auxiliary input proof techniques
Contact author(s): unruh @ cs uni-sb de
History: 2007-06-08: revised; 2007-05-07: received; See all versions
Short URL: https://ia.cr/2007/168
License: CC BY

BibTeX

@misc{cryptoeprint:2007/168,
      author = {Dominique Unruh},
      title = {Random Oracles and Auxiliary Input},
      howpublished = {Cryptology {ePrint} Archive, Paper 2007/168},
      year = {2007},
      url = {https://eprint.iacr.org/2007/168}
}