(see CAPTCHA.net, see HIPs)

Faculty: Lenore Blum, Manuel Blum, Avrim Blum;
students: Nick Hopper, Luis von Ahn, John Langford, Scott Crosby, Brighten Godfrey; Bartosz Przydatek, Chuck Rosenberg, Ke Yang; partners: Udi Manber (Yahoo); Doug Tygar, Richard Fateman (UC Berkeley); Henry Baird (Xerox Parc)

This PROBE concerns the following general problem: Design a protocol for convincing a computer that one is a member of a specific class of humans --- the singleton "Joan Smith" class, or the class of all humans, etc. --- in such a way that someone outside the class, even with access to powerful computers and numerous examples of successful authentication, cannot impersonate a member of the class .

The "Joan Smith" class: Current authentication methods for monetary transactions are notoriously weak: one gives one's social security number, address, phone number or mother's maiden name. This information is easily csaptured at public phone booths, and in any case is available to the bank clerk or broker with whom one deals. We seek a solution to the problem, "How can a human in a glass house login to a computer when she has nothing but a monitor and keyboard or a telephone and keypad only?" Glass house means that anyone can observe her login any number of times .

The class of all humans: Consider an online poll: Which is the best computer science graduate school? Graduate students can (and did!) write programs to vote thousands of times for their own school. To prevent this, we need a method to tell whether it is a script or a human that is voting. We need what we call a Completely Automatic Public Turing Test to tell Computers and Humans Apart (CAPTCHA). This is an algorithm for administering and grading a test that distinguishes humans from computers. Such an algorithm has many applications. Indeed, Udi Manber of Yahoo has arranged to use our rudimentary prototypes to solve several such Internet problems: 1) The chat room problem: how to keep (ro)bots out of chatrooms. (2) The accounts problem: how to keep bots from signing up for (numerous) accounts. (3) The spam mail problem: how to keep bots from flooding the net with spam mail.

Solutions to the above problems require the collaboration of people from widely different areas .

• Cognitive Psychology
  
• Computer Vision and Speech
  
• Artificial Intelligence. A protocol for the "class of all humans" problem is a public challenge to the AI community: "Write a program that can authenticate itself as human to this protocol." We intend to challenge AI researchers with welldefined problems that the AI community find interesting and important .
• Computational Learning Theory. Learning Theory tells which functions are learnable from examples and, crucially, which are possibly not learnable. Our authentication protocols must have the property that an eavesdropper with a powerful computer, even after observation of many successful authentications, cannot learn to impersonate "Joan Smith." -- Cryptography
• Theory of Computation. What are the right definitions and models for this problem? Computer Science theory is ideally suited to asking and answering this question

The First Workshop on Human Interactive Proofs, Palo Alto, January 2002