Calvin Lab Room 116
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.