The Random Oracle Methodology, Revisited

The Random Oracle Methodology, Revisited

February 1, 2008 | Ran Canetti, Oded Goldreich, Shai Halevi
The paper revisits the Random Oracle Model (ROM) and challenges the assumption that schemes secure in this model are also secure when implemented with real cryptographic hash functions. The main result is a negative one: there exist signature and encryption schemes secure in the ROM but insecure when implemented with any real function. The authors argue that the traditional approach of defining a single robust function for the ROM is insufficient, as no function ensemble can perfectly mimic the behavior of a random oracle. They introduce the concept of "correlation intractability," which requires that it is infeasible to find inputs that relate to outputs in a specific way. However, they show that no function ensemble can satisfy this property. This implies that schemes relying on the ROM's assumptions may not be secure in practice. The paper also demonstrates that even if a scheme is secure in the ROM, its real-world implementation using any function ensemble may be insecure. The authors use non-interactive CS-proofs and diagonalization techniques to construct such schemes, showing that the ROM does not guarantee security in the real world. The results highlight the limitations of the ROM and the need for more rigorous definitions of secure implementations.The paper revisits the Random Oracle Model (ROM) and challenges the assumption that schemes secure in this model are also secure when implemented with real cryptographic hash functions. The main result is a negative one: there exist signature and encryption schemes secure in the ROM but insecure when implemented with any real function. The authors argue that the traditional approach of defining a single robust function for the ROM is insufficient, as no function ensemble can perfectly mimic the behavior of a random oracle. They introduce the concept of "correlation intractability," which requires that it is infeasible to find inputs that relate to outputs in a specific way. However, they show that no function ensemble can satisfy this property. This implies that schemes relying on the ROM's assumptions may not be secure in practice. The paper also demonstrates that even if a scheme is secure in the ROM, its real-world implementation using any function ensemble may be insecure. The authors use non-interactive CS-proofs and diagonalization techniques to construct such schemes, showing that the ROM does not guarantee security in the real world. The results highlight the limitations of the ROM and the need for more rigorous definitions of secure implementations.
Reach us at info@study.space