5
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • $\begingroup$ What is the difference between an essay outline and an essay? What is the difference between a book and the blurb on the back of a book? $\endgroup$ – J.D. Jul 4 '16 at 11:30
  • $\begingroup$ It is I who downvoted. $\endgroup$ – fkraiem Jul 4 '16 at 11:36
  • $\begingroup$ The question in the edit is better. $\endgroup$ – fkraiem Jul 4 '16 at 11:38
11
$\begingroup$

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?

  1. Sometimes the full proof is just a difference of obvious details and not good to publish
  2. 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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thank you for the answer. I'm wondering if you can refer me to some of your papers that you use full proof especially the simulation-based proof, so I can read them and learn how to write the full proof. $\endgroup$ – user153465 Jul 4 '16 at 18:16
  • $\begingroup$ Luckily, I recently wrote a tutorial on how to write simulation-based proofs, and it indeed contains very full and detailed proofs. See eprint.iacr.org/2016/046.pdf. $\endgroup$ – Yehuda Lindell Jul 4 '16 at 18:23
  • $\begingroup$ What about PhD thesis? Must a PhD thesis contain a full proof or sketch would suffice? $\endgroup$ – user153465 Aug 19 '16 at 10:02
  • $\begingroup$ A full version should contain full proofs of everything. This doesn't mean that obvious details should be included. It's difficult for new researchers to know where to draw the line, but this is the role of the advisor. $\endgroup$ – Yehuda Lindell Aug 21 '16 at 8:32
1
$\begingroup$

Why do most of papers in the well-known conferences provide only the proof sketch?

Space constraints, mostly (the paper has to fit in a certain number of pages). Often, the full proofs are given in the preprint version, available from the author's home page or the ePrint archive.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Look for the Appendix ;-) $\endgroup$ – ddddavidee Jul 4 '16 at 12:09
  • $\begingroup$ To elaborate a bit: Often the full proof will appear in an appendix in the submission version provided to the peer reviewers, though they aren't required to vet appendix material. The appendices disappear in the conference version to meet page constraints, than reappear in the self-published "full version". A bit of a mess. $\endgroup$ – Seth Jul 4 '16 at 17:42

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.