Random Oracle with Auxiliary Input, Revisited
Siyao Guo

Abstract:

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:

• Unruh introduced a very simple-to-use technique called pre-sampling, allowing one to replace the original oracle O with leakage z = z(O) by another random oracle P and same leakage z(O), where P is completely fresh and random, except P is allowed to agree with O on a small set of points. The goal is to minimize the best security loss as a function of the number of common points P. Unruh showed that this loss is at most O(\sqrt{ST/P}), and conjectured that a better proof can make this security loss negligible for a sufficiently large polynomial P. We disprove this conjecture by showing that the improvement can never exceed O(ST/P).
• We establish new security bounds for basic primitives (one-way, collision-resistant and pseudorandom functions, generators, and message authentication codes). Our bounds are nearly optimal, always substantially beat the provable version of pre-sampling, and are never worse (and often better!) than the dream version of pre-sampling. At the heart of our results is the compression technique of Gennaro and Trevisan, and its extensions by De, Trevisan and Tulsiani.
• We prove that salting provably defeats/mitigates preprocessing for a variety of applications of hash functions, including one-way functions, pseudorandom functions/generators, and message authentication codes. In each case, using (at most) n bits of salt, where n is the length of the secret key, we get the same security O(T/2^n) in the ROM with auxiliary input as we get without auxiliary input.

Joint work with Yevgeniy Dodis and Jonathan Katz.