Are there any textbook-style material on black-box separations in cryptography? I tried to read the paper of Impagliazzo and Rudich but couldn't get much of it.

A previous StackExchange entry gives a list of papers on the topic. But I wonder if the topic is covered by introductory-level notes. For example, the intuition behind a PRG is fairly popular. However the intuition behind separation wasn't clear to me from the papers. While I could understand some of the details, I didn't have a clear idea what the overall goal was. Or, for example, I couldn't get the technique of separating a construction from a given primitive compared to that of establishing a lower bound on certain parameters in the construction.

I believe one reason for lack of introductory resources could be that the topic is considered advanced, e.g., despite not being so recent, it's not covered in classical textbooks. Perhaps I'm missing some of these pointers. But otherwise it would be a good idea to compile such an introduction in the comments.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.