The main differences between Sketch of Proof and Full proof My question in general is:

Question 1: What are the differences between sketch of proof and full proof?



In simulation-based proof, in semi-honest model, we construct a view that is computationally indistinguishable from real view. Then we argue that the two views are computationally indistinguishable. 

Question 2: Why is this approach "only sketch" of proof?

Question 3: What would the full proof be like (in reduction format)?

Edit: Why do most of papers in the well-known conferences provide only the proof sketch?
The answer to this question is not straightforward and has a lot to do with the "conference culture" of computer science. Unlike other fields, the main publication venues for CS are conferences and not journals. This isn't to say that journals don't have an important role; rather, you don't follow journals to see what research is being done - you follow conferences. (Note that also unlike other fields, conference papers ARE peer reviewed. So, some basic validation has already been done.) Journals are mainly there to validate correctness in a more rigorous way. Much has been said about the advantages and disadvantages of this culture and there are certainly both. Conference culture enables a very fast dissemination process, but it also means that people work towards deadlines and don't always have full proofs.

Ideally, one would expect researchers to have full proofs of security and then cut them down to proof sketches in the conference version. However, in many cases, this just isn't true, and this can lead to errors. Note that even when writing full proofs you can have errors, and I've had my fair share of published mistakes. However, at least I try to do my best in writing a full proof (which also makes it easier to spot the mistake if it's there). To be honest, though, I haven't written full proofs for all my papers as well, and I too am negligent in that.

Having said all of the above, some things are so obvious to the experienced researcher that writing them out in full is actually a disservice. We all know how a standard hybrid argument works, and therefore writing it out will only fill up the paper with useless details that don't help at all in understanding the result. My recommendation is to always write out the full hybrid to check that there is no subtlety. Then, if it turns out to truly be standard, writing "the full proofs follows a standard hybrid" is not only OK but also better. So, sometimes proof sketches are not laziness or lack of rigor, but a way to make a proof more readable to the experienced reader (and the inexperience would be best served by learning this in Goldreich's book anyway).

In summary, why aren't proof sketches always written?


Sometimes the full proof is just a difference of obvious details and not good to publish
More often, it's due to the conference and not journal culture. This can be due to the fact that the researchers are working to a tight deadline and never wrote a full proof [VERY BAD IN MY OPINION] or due to the fact that the conference limits the page numbers and so it can't be put in [ALSO PRETTY BAD].


The right thing to do scientifically is to have a full proof (modulo details that are not worth putting in as in the previous item) and then cut it down to a proof sketch for the conference version. In this case, a full version should always be put on your homepage or ePrint, and if it's an important result then it should be sent to a journal.

One last point, conference papers are now rarely actually printed, making the page limit quite unnecessary. Of course, it's not possible to review the entire paper in the conference refereeing procedure, but the published version can be considerably longer and numerous conferences are doing this. Still, in many cases, it's not long enough for a truly full version and this should be posted as mentioned above.