ICS Theory Group

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?