Uncheatable Distributed Computations
Philippe Golle and Ilya Mironov.
Computationally expensive tasks that can be parallelized are most
efficiently completed by distributing the computation among a large number
of processors. The growth of the Internet has made it possible to invite
the participation of just about any computer in such distributed
computations. This introduces the potential for cheating by untrusted
participants. In a commercial setting where participants get paid for
their contribution, there is incentive for dishonest participants to claim
credit for work they have not done. In this paper, we propose security
schemes that defend against this threat with very little overhead. Our
weaker scheme discourages cheating by ensuring that it does not pay off,
while our stronger schemes let participants prove that they have done
(almost) all the work they were assigned with high probability.