How can I timestamp my paper without violating double-blind review?
The most typical way to time-stamp a piece of work is to place it in a public repository: arXiv is a good example when it applies; many institutions also have a technical memo or technical report system in place. Although this may technically violate certain interpretations of double-blind submissions, as noted in the comments blinding of authorship is pretty iffy in many cases. Moreover, in practice this will only be violated if the reviewers actively go looking, particularly if you put it in an institutional repository rather than a global one like arXiv. I would thus advise that if you are worried about date-stamping, just do it and let the double-blind nitpickers complain if they even notice.
One other consideration: certain publications (particularly certain journals) do have a policy against accepting material that is already available online. While this is in my view an insane policy, if you find yourself dealing with such, one way to handle with it is to put up a shortened version of the work, i.e., extended abstract, as the date-stamped pre-print.
Are you really afraid that it will be plagiarized? The only people who have seen your work are the programme committee and any reviewers who saw the paper when you first submitted it. It would be very surprising if the programme committee or reviewers of what you describe as a "top-tier conference" rejected a paper and then plagiarized it.
Or are you worried that you'll be scooped, i.e., that somebody else have similar but independent work accepted by another conference or journal before you manage to get your paper published? If so, the fact that you already submitted it to a conference should be enough to demonstrate your priority. It's not just you and your co-authors who are claiming that your paper already existed in October 2014 but also the programme committee of the conference can confirm this.
Here's a version that focuses on
- making the proof watertight for legal matters
- not publicly revealing the content
(which follows from the double-blind requirement)
The legally provable way of time-stamping something (and also to legally prove the state it was in at that time) is to have a notary attest it, and/or give a copy to the notary for keeping (which allows to prove that the content was not tampered with afterwards). This kind of service is the main business and duty of a notary.
The "poor man's version" of a sealed and unopened post-stamped envelope is much cheaper, but unlike the notary attest there is no legally binding guarantee that a court would accept this.
As has been pointed out, making the content public, preferrably with a time stamp (aka publishing (!)) is the yet cheaper alternative - however IMHO it is not compatible with the double-blind requirement of the question: It is not possible to have the content + your identity + a timestamp publicly (which are the 3 pieces of information you want to connect) available to everyone but the blinded reviewers.
As for cryptographic methods, at the moment I'd consider them at a similar level to the post-stamped envelope. The legal weight of this is quite unclear to me -- if you're really concerned I'd say an encrypted email exchange with someone who states "I got this email at this and that date" is at the same level as having someone testify that they saw or got the content from you at the stated date.
I'd imagine that a notary could do the encrypted signing, but AFAIK this is a techonolgy that yet has to fully emerge:
- There has been a project called "Datennotar" (data notary) at the Fraunhofer FOKUS and the University Kiel - final reports in German are available at ISPRAT (funder).
AFAIK there are no data notaries so far in Germany. - Wikipedia says such services exist in the US. A quick search brought up some companies, but the first two web pages I tried at least to me looked incomplete in some important details: one has a contact page without any kind of address, the second has email and phone only. Over here in the EU this wouldn't be legal for any kind of business ...