Secure distributed human computation

ABSTRACT

This paper is a preliminary exploration of secure distributed human computation. We consider the general paradigm of using large-scale distributed computation to solve difficult problems, but where humans can act as agents and provide candidate solutions. We are especially motivated by problem classes that appear to be difficult for computers to solve effectively, but are easier for humans; e.g., image analysis, speech recognition, and natural language processing. This paradigm already seems to be employed in several real-world scenarios, but we are unaware of any formal and unified attempt to study it. Nonetheless, this concept spawns interesting research questions in algorithm design, human computer interfaces, and programming language / API design, distributed systems, and cryptography, among other fields. There are also interesting implications for Internet commerce and the B24b model. We describe this research area and suggest a basic framework for the design of such systems. We analyze security and reliability against malicious parties using standard probability theory tools. We then derive design principles using standard decision-theory concepts. Finally, we list extensions and open problems.

REFERENCES

• 1: Luis von Ahn , Manuel Blum , John Langford, Telling humans and computers apart automatically, Communications of the ACM, v.47 n.2, p.56-60, February 2004 [doi>10.1145/966389.966390]
• 2: L. von Ahn, M. Blum, N. Hopper and J. Langford. CAPTCHA: Using hard AI problems for security. Eurocrypt 2003.
• 3: Luis von Ahn , Laura Dabbish, Labeling images with a computer game, Proceedings of the SIGCHI conference on Human factors in computing systems, p.319-326, April 24-29, 2004, Vienna, Austria [doi>10.1145/985692.985733]
• 4: K. J. Arrow. Social Choice and Individual Values. Coles Foundation for Research in Economics Monograph 12, 2nd edition, Yale University Press, 1963.
• 5: R. von Bitter. Mathenauts: Tales of Mathematical Wonder. Arbor House Pub Co; June 1987.
• 6: M. Blum , S. Kanna, Designing programs that check their work, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.86-97, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73015]
• 7: M. Blum , M. Luby , R. Rubinfeld, Self-testing/correcting with applications to numerical problems, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.73-83, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100225]
• 8: R. Cramer, R. Gennaro and B. Schoenmakers. A Secure and Optimally Efficient Multi-Authority Election Scheme. EUROCRYPT 97.
• 9: Cyphermint, Inc. http://www.cyphermint.com/
• 10: The Distributed Proofreader's project. http://www.pgdp.net/
• 11: X. Drèze and F. Hussherr. Internet Advertising: Is Anybody Watching? Journal of Interactive Marketing, 2003, Vol. 17 (4), 8-23.
• 12: Michael J. Fischer , Nancy A. Lynch , Michael S. Paterson, Impossibility of distributed consensus with one faulty process, Journal of the ACM (JACM), v.32 n.2, p.374-382, April 1985 [doi>10.1145/3149.214121]
• 13: The Search of Extraterrestrial Intelligence Project. University of California, Berkeley. http://setiathome.berkeley.edu.
• 14: O. Goldreich. Secure Multiparty Computation. Unpublished Manuscript. Last revised October 2003.
• 15: The Great Internet Mersenne Prime Search. http://www.mersenne.org.
• 16: Philippe Golle , Ilya Mironov, Uncheatable Distributed Computations, Proceedings of the 2001 Conference on Topics in Cryptology: The Cryptographer's Track at RSA, p.425-440, April 08-12, 2001
• 17: P. Golle and S. Stubblebine. Distributed computing with payout: task assignment for financial- and strong- security. Financial Cryptography 2001.
• 18: Nancy A. Lynch, Distributed Algorithms, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996
• 19: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
• 20: The New York Times Web Site. http://www.nytimes.com.
• 21: C. K. Prahalad and S. Hart. The Fortune at the Bottom of the Pyramid. Strategy + Business, Issue 26, Q1 2000.
• 22: Project Gutenberg. http://www.gutenberg.net/
• 23: Spam Net Web Site. http://www.cloudmark.com.
• 24: Jeanette P. Schmidt , Alan Siegel , Aravind Srinivasan, Chernoff-Hoeffding Bounds for Applications with Limited Independence, SIAM Journal on Discrete Mathematics, v.8 n.2, p.223-250, May 1995 [doi>10.1137/S089548019223872X]
• 25: S. Stubblebine and P. van Oorschot. Online Dictionary Attacks with Login Histories and Human-in-the-Loop. Financial Cryptography 2004.
• 26: Vipul's Razor Web Site. http://sourceforge.net/projects/razor.
• 27: A. Yao. Protocols for Secure Computations. IEEE Symposium on Foundations of Computer Science (FOCS) 1982.
• 28: F. Zhou, L. Zhuang, B. Zhao, L. Huang, A. D. Joseph, and J. Kubiatowicz. Approximate Object Location and Spam Filtering. ACM Middleware, 2003.

INDEX TERMS

Primary Classification:
  K. Computing Milieux
  K.4 COMPUTERS AND SOCIETY
      K.4.4 Electronic Commerce
          Subjects: Distributed commercial transactions

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.4 Parallel Architectures
          Subjects: Distributed architectures

  H. Information Systems
  H.1 MODELS AND PRINCIPLES
      H.1.2 User/Machine Systems
          Subjects: Human factors

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
  I.m MISCELLANEOUS

  K. Computing Milieux
  K.4 COMPUTERS AND SOCIETY
      K.4.4 Electronic Commerce
          Subjects: Payment schemes; Security

General Terms:
Economics, Human Factors, Security

Keywords:
B24b, human distributed computation