ROM Reduction Failures: Reasons and Solutions
摘要
The Random Oracle Model (ROM), proposed by Bellare and Rogaway (CCS 93), is a crucial tool for providing heuristic security of well-performing cryptographic schemes utilizing hash functions. Several generic transformations, such as Encrypt-with-Hash, OAEP, and FDH, suffer from a class of ROM failures. These failures expose flaws in the existing security proofs for these generic transformations in the ROM. This paper focuses on analyzing these ROM reduction failures. To understand and address these failures, we introduce a tool named Hierarchical ROM (HROM). In this model, Random Oracles (ROs) are classified into two types: RO used in generic transformations and RO used in underlying primitives. Existing ROM reduction proofs overlook the existence of the latter ROs. When the former RO depends on the latter, the (re)programming of ROs by reductions is constrained, causing failures of existing reductions. We refine reductions in the HROM and provide a generic framework for addressing the ROM reduction failures of generic transformations.