In the random oracle model, the parties are given oracle access to a random member ofa (typically huge) function family, and are assumed to have unbounded computational power(though they can only make a bounded number of oracle queries). This model provides powerfulproperties that allow proving the security of many protocols, even such that cannot be provedsecure in the standard model (under any hardness assumption). The random oracle model is alsoused to show that a given cryptographic primitive cannot be used in a black-box way to constructanother primitive; in their seminal work, Impagliazzo and Rudich [STOC ’89] showed that in therandom function model – when the function family is the set of all functions – it is impossibleto construct (secure) key-agreement protocols, yielding that key-agreement cannot be black-boxreduced to one-way functions. Their work has a long line of followup works (Simon [EC ’98],Gertner et al. [STOC ’00] and Gennaro et al. [SICOMP ’05], to name a few), showing that givenoracle access to a certain type of function family (e.g., the family that “implements” public-keyencryption) is not sufficient for building a given cryptographic primitive (e.g., oblivious transfer).Yet, in the more general sense, the following fundamental question remained open: