Fixing Cracks in the Concrete: Random Oracles with Auxiliary Input, Revisited

We revisit security proofs for various cryptographic primitives in the random oracle model with auxiliary input (ROM-AI): an attacker A can compute arbitrary S bits of leakage  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  (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) security against preprocessing. We obtain a number of new results about ROM-AI but our main message is that ROM-AI is the “new cool kid in town”:  it nicely connects theory and practice, has a lot of exciting open questions and is still in its infancy.  In short, you should work on it! Based on joint works with Sandro Coretti, Yevgeniy Dodis and Jonathan Katz.