# ICS 269, Fall 2003: Theory Seminar

## 17 Oct 2003:

Modeling Hash Functions as Random Oracles in Cryptography:
New Surprising Results

Stanislaw Jarecki

Modeling hash functions as random oracles is a heuristic which gives some
evidence that a cryptographic scheme is secure. We'll show examples of
such arguments, but also show some counterintuitive results arrived at in
this model. Namely, we'll show that a straighforward implementation of an
RSA-based signature scheme is only loosely related (in its security) to
the RSA problem, while a new scheme which essentially adds only one more
bit to the signature does suddenly become as difficult as the underlying
RSA problem. How can one bit change so much?