Uncheatable Distributed Computations

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 did not do. 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 most of
the work they were assigned with high probability.