In this week's seminar, I will present the CRYPTO 2013 paper by Bellare-Hoang-Keelveedhi on "Instantiating Random Oracles via UCEs", where UCE stands for Universal Computational Extractor. This is a very interesting work (in my opinion) which formalizes what it means for a concrete function to behave like a random oracle. There have been some attempts at this in the past. However, this is the first attempt to achieve wide applicability. Specifically, many classic random-oracle constructions (but not all) can be proven secure using UCEs. We will present the definitions, and see how UCEs can be used to replace random oracles in different scenarios. A number of interesting questions are raised by this work, which I will also present.
Note: this weeks GTACS will be a “reading group” format where I will be presenting work that is not mine.