Abstract
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.
Supported by Stanford Graduate Fellowship
Supported by nsf contract #CCR-9732754
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
W. Aiello, S. Bhatt, R. Ostrovsky and S. Rajagopalan. Fast verification of any remote procedure call: short witness-indistinguishable one-round proofs for NP. In Proc. of ICALP 2000, pp. 463–474.
M. Allen. Do-it-yourself climate prediction. In Nature, 401, p. 642, Oct. 1999.
J. Baldeschwieler, R. Blumofe and E. Brewer. ATLAS: An Infrastructure for Global Computing. In Proc. of the 7th ACM SIGOPS European Workshop, 1996.
A. Baratloo, M. Karaul, Z. Kedem and P. Wycko. Charlotte: Metacomputing on the Web. In Future Generation Computer Systems, 15 (5–6), pp. 559–570, 1999.
D. Bedell. Search for extraterrestrials—or extra cash. In The Dallas Morning News, 12/02/99, also available at: http://www.dallasnews.com/technology/1202ptech9pcs.htm.
M. Bellare and P. Rogaway. Random oracles are practical: a paradigm for designing efficient protocols. In Proc. of the First ACM Conf. on Computer and Communications Security, pp. 62–73, 1993.
K. Bharat and A. Broder. A technique for measuring the relative size and overlap of public Web search engines. In WWW7 / Computer Networks 30(1–7), pp. 379–388, 1998.
M. Blum and S. Kannan. Programs That Check TheirWork. In Proceedings of the Twenty First Annual ACM Symposium on Theory of Computing, 1989.
C. Cachin, S. Micali and M. Stadler. Computationally private information retrieval with polylogarithmic communication. In Proc. of EUROCRYPT’99, LNCS 1592, pp. 402–414, 1999.
J. Cai, R. Lipton, R. Sedgewick and A. Yao. Towards uncheatable bench-marks. In Proc. of 8th Annual Structure in Complexity Theory Conference, pp. 2–11, 1993.
Y. Dodis, S. Halevi and T. Rabin. A cryptographic solution to a game theoretic problem. In Proc. of CRYPTO’00, LNCS 1880, pp. 112–131, 2000.
J. Feigenbaum. Encrypting problem instances: Or..., Can you take advantage of someone without having to trust him? In Proc. of CRYPTO 1985, LNCS 218, pp. 477–488.
F. Hohl. A model of attacks of malicious hosts against mobile agents. In 4th ECOOP Workshop on Mobile Object Systems, 1998.
Y. Minsky, R. van Renesse, F. Schneider and S Stoller. Cryptographic support for fault-tolerant distributed computing. TR96-1600, Department of Computer Science, Cornell University, 1996.
F. Monrose, P. Wycko and A. Rubin. Distributed execution with remote audit. In Proc. of the Network and Distributed System Security Symposium, pp. 103–113, 1999.
N. Nisan, S. London, O. Regev and N. Camiel. Globally Distributed Computations over the Internet-the popcorn Project. In Proc. of the International conference on Distributed Computing Systems, pp. 592–601, 1998.
T. Sanders and C. Tschudin. Toward mobile cryptography. In IEEE Symposium on Security and Privacy, 1998.
L. Sarmenta and S. Hirano. Bayanihan: Building and studying volunteer computing systems using Java. In Future Generation Computer Systems, 15 (5–6), pp. 675–686, 1999.
Ed. D. Sullivan. Search Engine Sizes. Ongoing. http://www.searchenginewatch.com/reports/sizes.html
SETI@home, http://setiathome.berkeley.edu.
G. Vigna. Protecting Mobile Agents through Tracing. In Proc. of the 3rd Workshop on Mobile Object Systems, June 1997.
G. Vigna (Ed.). Mobile Agents and Security. LNCS 1419, 1998.
H. Wasserman and M. Blum. Software reliability via run-time result-checking. In Journal of the ACM, 44(6), pp. 826–849, 1997.
B. Yee. A sanctuary for mobile agents. In DARPA Workshop on Foundations for Secure Mobile Code, 26–28 March 1997, http://www-cse.ucsd.edu/users/bsy/pub/sanctuary.fsmc.ps.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Golle, P., Mironov, I. (2001). Uncheatable Distributed Computations. In: Naccache, D. (eds) Topics in Cryptology — CT-RSA 2001. CT-RSA 2001. Lecture Notes in Computer Science, vol 2020. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45353-9_31
Download citation
DOI: https://doi.org/10.1007/3-540-45353-9_31
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-41898-6
Online ISBN: 978-3-540-45353-6
eBook Packages: Springer Book Archive