The Oracle's Secrets

Baker, Gill, and Solovay introduced relativization to complexity theory as a way of ruling out certain classes of argument as ways of resolving the P vs NP question and related issues. Not much later, Brassard used oracles in cryptography, showing oracles relative to which strong public-key cryptography was possible. In modern cryptography, oracle results have been used to show a variety of non-equivalence results between cryptographic tools and goals. My work with Steven Rudich showing that strong one-way functions do not suffice to construct secure key agreement protocols in a black-box manner, was one of the first such results. This talk will give a personal account of the discovery of this result, stressing anecdotes and context over technical details. If there's time, I may also describe some of the subsequent developments.