------------------------------------------------------------------- INVITATION Dear Colleague -- You are cordially invited to attend this workshop, which has grown out of recent experiments at CMU, PARC, UC Berkeley, and elsewhere. We feel that this might be a good moment to bring together researchers interested in the topic, to map out our most promising technical directions. We would very much appreciate hearing any comments you may have on our statement of scope. Also, please feel free to suggest people to invite (we wish to hold the number to 30). All the best, -- Manuel Blum & Henry Baird -------------------------------------------------------------------- CALL FOR PARTICIPATION Workshop on Human Interactive Proofs January 9-11, 2002 Palo Alto, California (Immediately following these meetings: - 13th ACM-SIAM SODA, Jan 6-8, San Francisco; and - SIAM Sessions at Joint Mathematics Meetings, Jan 6-7, San Diego.) Organizers: Manuel Blum, CS Dept, CMU Henry Baird, Xerox PARC Human Interactive Proofs (HIPs) are protocols for convincing a computer over a network that you are a member of a specific group of humans, in such a way that: - you can easily authenticate yourself without providing biometrics such as fingerprints or employing mechanical aids such as PDAs, laptops, smartcards -- even pencil and paper; and - no one outside the group can be authenticated even after observing a large number of successful authentications. HIPs could be useful for many kinds of groups, e.g. (a) the group of *all* humans; (b) groups each consisting of a *single* person; (c) small subgroups, e.g. employees of an organization; (d) adults (versus children). A HIP for the group of all humans distinguishes people from computers, so it is a kind of Turing Test that is graded by a computer. We call such a test a CAPTCHA, "Completely Automated Probabilistic Public Turing Test to tell Computers and Humans Apart." CAPTCHAs can be used to prevent computer programs (or 'bots') from infesting chat rooms, looting databases, grabbing large numbers of free e-mail accounts, voting thousands of times in online polls, etc. Some CAPTCHAs have already been built and a few are in use (e.g. by Yahoo! and PayPal): these typically exploit gaps in cognitive ability between humans and computers. e.g. recognition of speech or images. A HIP for an individual is a protocol that serves the purposes of a personal password or biometric such as a fingerprint. Current authentication methods for computer systems, web pages, or monetary transactions are weak in some ways. Passwords, social security numbers, phone numbers, mother's maiden names, and PINs all can be easily stolen or shared and are routinely known to others, e.g. system administrators, who may abuse them. Biometrics require special hardware and do not provide universal coverage. We call a HIP for individuals a HUMANOID: "HUMAN Oriented ID". This Workshop, the first on this topic, will explore these and related questions: - How do we construct human interactive proofs? - Is there evidence that some HIPs are inherently impossible to construct? - Are there useful & feasible HIPs besides HUMANOIDs and CAPTCHAs? - What can humans do easily in their heads? - What are the current and near-term limits to what computers can do? - How can we make use of the things that humans can do but computers can't, in order to expand our current computational abilities? - Which gaps in ability between humans and computers, or between one group of human users and another, can be detected on-line, fully automatically, efficiently, and reliably? - By what methods can one prove that a CAPTCHA is easy for a human but hard for a computer to pass? - Which Turing tests will be resistant to attack or reverse engineering, even if their algorithms are published? - Is there a general way to transform unsolved AI problems into CAPTCHAs? - Which CAPTCHA tests are likely to pass the broadest class of people, including children, non-English speakers, and naive web users? - For CAPTCHAs based on degraded images of text (the most common in current use), how best to choose: . text, typefaces, degradation parameters; and . amount of context to show (morphological, lexical, etc)? Attendance will be by invitation only. The invitees include experts in theoretical computer science, algorithms, security, cryptography, cognitive science, artificial intelligence, machine learning, pattern recognition, computer vision, and speech understanding. Each attendee must submit a 1-5 page abstract in advance, which will be distributed at the meeting, and everyone will be expected to participate actively in plenary talks, panel discussions, and/or break-out working groups. The two-and-a-half days should allow time for both formal and informal discussion, leading to the drawing up of a consensus list of urgent open problems, theoretical issues, and well-characterized, usable engineering solutions. The workshop locale is the famed Xerox Palo Alto Research Center in the heart of Silicon Valley, located a 45 minutes' drive south of San Francisco and 1-1/2 hour's flight north of San Diego. For advice on travel, hotels, etc, please feel free to contact PARC Administrative Assistant Jeanette Figueroa figueroa@parc.xerox.com +1-650-812-4705 There will be no registration fee. Attendees will make their own travel and hotel arrangements. Lunches may be purchased at the PARC cafeteria. On-site proceedings, continental breakfasts, and coffee/tea/ juice breaks will be provided courtesy of PARC. Deadlines --------- November 15 Indicate your intention to attend, by email to Manuel Blum mblum@cs.cm.edu December 15 Send a 1-5 page abstract (ASCII, PDF, PostScript, MSWord) to: Henry Baird baird@parc.xerox.com Workshop Schedule (tentative) ----------------- Wed, Jan 9 8:00-9:00 9:00-9:15 welcome: M. Blum & H. Baird 9:15-12:00 survey & definition talks 12:00-1:00 1:00-3:00 panel discussion; plenary talks 3:00-3:30 3:30-5:00 plenary talks Thu, Jan 10 8:30-9:00 9:00-12:00 plenary talks 12:00-1:00 1:00-1:30 pick working-group topics 1:30-3:00 working group discussions 3:00-3:30 3:30-5:00 read-out from working groups Fri, Jan 11 8:30-9:00 9:00-10:00 panel discussion: The Way Forward 10:00-11:30 draw up list of open problems, sound engineering methods, etc 11:30-12:00 plan for follow-up workshop (summer 2002, Pittsburgh?) 12:00 Sponsorship ----------- This workshop is funded in part by the Aladdin Center at CMU: http://www.cs.cmu.edu/~aladdin Aladdin is a project which attempts to provide mathematical understanding of fundamental issues in Computer Science, and to use this understanding to produce better algorithms, protocols and systems. The workshop also is supported and hosted by the Document Image Decoding research area of Xerox PARC: http://www.parc.xerox.com/istl/groups/did which focuses on algorithms for document image anaylysis with a special emphasis on the inference of statistical models of shape, image quality, and language and optimal decoding of images with respect to these models.