This is a proof that I've gone back to many times over the last few years and while I can read it and easily verify the steps, it seems like it's a proof, where I will always essentially forget the details, i.e. if I read it today, I would struggle to write down a full proof tomorrow without actually spending quite a bit of effort. I'm talking about the proof that's e.g. in Goldreich's Foundations of Crypto book, which I believe is standard (I've never seen a different proof).

As complexity theory is not my field, I would hope that people who are more experienced in the field could make sense of the proof by answering the following questions:

  1. What part of the proof are completely standard techniques?

  2. What part of the proof if any is a "trick".

The basic idea is easy: Given a weak one-way function, repeat it many times, so that any inverter of the repeated function needs to invert all the pieces. Dealing with the lack of independence in processing the components in the inversion is then the tricky part and I'm hoping that there's a way to split it up into standard arguments. At least understanding it in useful pieces that might be applicable elsewhere would be nice, if possible.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.