Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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

share|improve this question

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
    
Would it be accurate to summarize as: Because the link between cryptographic hash functions and random oracles is tenuous, avoiding the ROM allows for more practical confidence in a scheme/proof? –  B-Con Jun 29 '12 at 21:13
1  
@B-Con: I think there's a some opinion in that summary that some might not agree with. But I think that's essentially correct. Any proofs of the security of the signature scheme don't have to end with, "... assuming your hash function is a random oracle, which of course it never will be." –  David Schwartz Jun 29 '12 at 21:17
    
Ah, thanks. I was afraid that this (absent) random oracle could be a slightly different beast than the one used in RSA-FDH; but you reassure me that the term is used in the same meaning. I'll wait a few days before accepting the answer, just in case some other opinion surfaces. –  fgrieu Jun 30 '12 at 9:41

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.