Why does it matter for a signature scheme to be without random oracles?

Question

There is a profusion of articles proposing signature schemes without random oracles (see for yourself). What does that mean, and why does it matter?

Answer 1

A "random oracle" is essentially a perfect hash function. It's a device that takes a message of any length and maps it randomly to a message of a fixed length such that the same input always produces the same output. Random oracles don't exist. For algorithms that require them, cryptographic hash functions are used instead. However, cryptographic hash functions are not really random oracles and any flaws in the hash function could translate into vulnerabilities in the signature scheme.

The simplest way to make a signature scheme is to begin by hashing the thing you need to sign to a fixed length. Since signature schemes generally aren't also trying to design hash functions, they just assume a random oracle to perform this function and then they demonstrate their security properties assuming a random oracle is used.

Signature algorithms that don't require random oracles don't require you to hash the thing you are signing. They operate on a message of arbitrary length, reducing it to a fixed-length signature as part of their own operation. Because you don't have to substitute a hash function for a random oracle, there is no risk that the hashing function will add new vulnerabilities to the signature scheme.

For example, say you have a signature scheme that requires a random oracle, and the signature scheme has been proven to have no vulnerabilities. You use MD5 as the random oracle. Oops, we can now generate MD5 collisions, so someone can now forge two different messages that have the same signature too easily. All the security properties of the signature algorithm aren't going to help you because the hash function isn't a random oracle and introduced vulnerabilities a random oracle (since it's theoretically perfect) doesn't have.