Random Oracle with Auxiliary Input, Revisited
Siyao Guo


In this work we revisit security proofs for various cryptographic primitives in the random oracle model (ROM) with auxiliary input: a (computationally unbounded) attacker A can compute arbitrary S bits of leakage z = z(O) about the random oracle O before attacking the system, and then use additional T oracle queries to O during the attack. This model was explicitly studied by Unruh in 2007 (CRYPTO 2007), but dates back to the seminal paper of Hellman in 1980 about time-space tradeoffs for inverting random functions, and has natural applications in settings where traditional random oracle proofs are not useful: (a) security against non-uniform attackers; (b) space-time tradeoffs; (c) security against preprocessing; (d) resilience to backdoors in hash functions. We obtain the following results:

Joint work with Yevgeniy Dodis and Jonathan Katz.