eprint.iacr.org will be offline for approximately an hour for routine maintenance at 11pm UTC on Tuesday, April 16. We lost some data between April 12 and April 14, and some authors have been notified that they need to resubmit their papers.

Paper 2017/937

Random Oracles and Non-Uniformity

Sandro Coretti
Yevgeniy Dodis
Siyao Guo
John Steinberger

We revisit security proofs for various cryptographic primitives in the auxiliary-input random-oracle model (AI-ROM), in which an attacker $A$ can compute arbitrary $S$ bits of leakage about the random oracle $\mathcal O$ before attacking the system and then use additional $T$ oracle queries to $\mathcal O$ during the attack. This model 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 the AI-ROM: Unruh (CRYPTO '07) introduced the pre-sampling technique, which generically reduces security proofs in the AI-ROM to a much simpler $P$-bit-fixing random-oracle model (BF-ROM), where the attacker can arbitrarily fix the values of $\mathcal O$ on some $P$ coordinates, but then the remaining coordinates are chosen at random. Unruh's security loss for this transformation is $\sqrt{ST/P}$. We improve this loss to the optimal value $O(ST/P)$, which implies nearly tight bounds for a variety of indistinguishability applications in the AI-ROM. While the basic pre-sampling technique cannot give tight bounds for unpredictability applications, we introduce a novel "multiplicative version" of pre-sampling, which allows to dramatically reduce the size of $P$ of the pre-sampled set to $P=O(ST)$ and yields nearly tight security bounds for a variety of unpredictability applications in the AI-ROM. Qualitatively, it validates Unruh's "polynomial pre-sampling conjecture"---disproved in general by Dodis et al. (EUROCRYPT '17)---for the special case of unpredictability applications. Using our techniques, we reprove nearly all AI-ROM bounds obtained by Dodis et al. (using a much more laborious compression technique), but we also apply it to many settings where the compression technique is either inapplicable (e.g., computational reductions) or appears intractable (e.g., Merkle-Damgard hashing). We show that for any salted Merkle-Damgard hash function with m-bit output there exists a collision-finding circuit of size $\Theta(2^{m/3})$ (taking salt as the input), which is significantly below the $2^{m/2}$ birthday security conjectured against uniform attackers. We build two general compilers showing how to generically extend the security of applications proven in the traditional ROM to the AI-ROM. One compiler simply prepends a public salt to the random oracle and shows that salting generically provably defeats preprocessing. Overall, our results make it much easier to get concrete security bounds in the AI-ROM. These bounds in turn give concrete conjectures about the security of these applications (in the standard model) against non-uniform attackers.

Note: Fixed a bug in earlier versions of the proofs for the multiplicative presampling part of Lemma 1 (special thanks to Patrick Harasser for pointing out that bug)

Available format(s)
Publication info
A minor revision of an IACR publication in EUROCRYPT 2018
Random-Oracle Model Non-Uniformity Space-Time Tradeoffs Collision-Resistance
Contact author(s)
corettis @ gmail com
dodis @ cs nyu edu
sg191 @ nyu edu
jpsteinb @ gmail com
2022-08-09: last of 2 revisions
2017-09-27: received
See all versions
Short URL
Creative Commons Attribution


      author = {Sandro Coretti and Yevgeniy Dodis and Siyao Guo and John Steinberger},
      title = {Random Oracles and Non-Uniformity},
      howpublished = {Cryptology ePrint Archive, Paper 2017/937},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/937}},
      url = {https://eprint.iacr.org/2017/937}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.