Random Oracles are Practical: A Paradigm for Designing Efficient Protocols

Random Oracles are Practical: A Paradigm for Designing Efficient Protocols

Bellare, Mihir, and Phillip Rogaway
Proceedings of the 1st ACM Conference on Computer and Communications Security (1993): 62-73
https://doi.org/10.1145/168588.168596

“Cryptographic theory has provided a potentially invaluable notion for cryptographic practice: the idea of provable security. Unfortunately, theoretical work often seems to gain provable security only at the cost of efficiency. This is due in part to the following. Theorists view certain primitives (e.g., one-way functions) as “basic” and build more powerful primitives (e.g., pseudorandom functions) out of them in inefficient ways; but in practice, powerful primitives are readily available and the so-called basic ones seem to be no easier to implement. In fact theorists deny themselves the capabilities of practical primitives which satisfy not only the strongest kinds of assumptions they like to make, but even have strengths which have not been defined or formalized.”

— Bellare & Rogaway