|
|
|
|
|
by matthewdgreen
2910 days ago
|
|
Random oracles are a model for reasoning about hash functions, so generally speaking they have the same “API” as whatever type of hash function you’d use in the real world. Most commonly that means they take in an arbitrary-length input and output a fixed-size digest. So yes, by the pigeonhole principle they will have collisions. One major difference is that “the oracle implements a random function” implicitly guarantees several security properties that otherwise you’d have to assume as complexity assumptions. For example, a random function has collision resistance due to the simple fact that outputs are distributed randomly and therefore finding a collision should take (on average!) many queries to the oracle. With standard hash functions, you have to assume collision resistance. |
|