Abstract: In the random oracle (RO) model (Bellare and Rogaway, CCS 1993), to analyze security of a scheme one heuristically models its hash functions (e.g., SHA256) as *truly random* functions accessible only via oracles. The RO model had much success in enabling security proofs for highly practical schemes that have held up in practice, but nobody really knows why. Particularly, researchers have exhibited ``pathological'' schemes that are secure in the RO model but completely insecure in practice.
We posit that the difference for the RO model schemes that have held up in practice is there actually exists relatively inefficient yet sufficient hash functions for their needs. Such schemes are called *instantiable.* The pathological schemes mentioned above do not have this property. We show that it is satisfied by two celebrated RO model ``encryption transforms'' called OAEP (Bellare and Rogaway, EUROCRYPT 1994) and Fujisaki-Okamoto (EUROCRYPT 1998). At a technical level, we make use of extremely lossy functions, due to Zhandry (CRYPTO 2016).
The CICS Theory Seminar is free and open to the public. If you are interested in giving a talk, please email Cameron Musco or Rik Sengupta. Note that in addition to being a public lecture series, this is also a one-credit graduate seminar (CompSci 891M) that can be taken repeatedly for credit.