Human Computation

Most of my time is spent inventing novel techniques for utilizing the computational abilities (or "cycles") of humans.


One family of techniques is CAPTCHA, automated tests that humans can pass but that current computer programs cannot. CAPTCHAs take advantage of the power of human cycles in order to differentiate people from computers, and have many applications in practical security. The previous results of my joint work with Manuel Blum, for instance, are used by Yahoo! to ensure that only humans obtain free email accounts.

Another family is exemplified by my work on The ESP Game. ESP is a seductive online game -- many people play over 40 hours a week! -- and when people play they help determine the content of images on the Web by providing meaningful labels for them. If the game is played as much as other popular online games, all images on the Web can be labeled in just a few weeks. Attaching proper labels to all images on the Web would allow for more accurate image search, would improve the accessibility of Web sites, and would help Web browsers block pornography. This approach to labeling images is simple but novel: rather than using computer vision techniques that don't work well, we encourage people to do the work for us by taking advantage of their desire to be entertained. The ESP Game has collected over 10 million labels for images on the Web.

More recently, along with my students Roy Liu, Mihir Kedia and Shiry Ginosar, I have developed other games that allow human computation. So far one of them, Peekaboom, has been released to a general audience and already collected millions of data points.

Here are the (updated) slides for my keynote talk on this subject at IAAI/IJCAI 2003.

Papers:


Luis von Ahn
Games With a Purpose
In IEEE Computer Magazine


Luis von Ahn, Ruoran Liu and Manuel Blum
Peekaboom: A Game for Locating Objects in Images
In ACM CHI 2006


Luis von Ahn, S. Ginosar, M. Kedia, R. Liu and M. Blum
Improving Accessibility of the Web with a Computer
Game.
In ACM CHI Notes 2006


Luis von Ahn, Mihir Kedia and Manuel Blum
Verbosity: A Game for Collecting Common-Sense Facts
In ACM CHI Notes 2006


Luis von Ahn and Laura Dabbish
Labeling Images with a Computer Game
In ACM CHI 2004


Luis von Ahn, Manuel Blum and John Langford
How Lazy Cryptographers do AI
In Communications of the ACM, Feb. 2004


Luis von Ahn, Manuel Blum, Nick Hopper and John Langford
CAPTCHA: Using Hard AI Problems for Security
In Eurocrypt 2003


 

Foundations of Cryptography/Security

In the past, I have also worked on theoretical cryptography and security. Nick Hopper, John Langford and I were the first to provide rigorous definitions of steganography in the computational setting and the first to prove that private-key steganography is indeed possible. (Informally, steganography is the process of sending a secret message from Alice to Bob in such a way that an eavesdropper -- who listens to all communications -- cannot even tell that a secret message is being sent. For instance, steganography could be the process of encoding a secret message in the pixels of a JPEG image. Steganography has been studied extensively in the last 20 years, but surprisingly, it was not until our work that anybody showed a system for steganography which is provably unbreakable by computationally bounded adversaries under cryptographic assumptions.) In follow-up work, Nick Hopper and I gave the first rigorous definitions of public-key steganography and showed that public-key steganography is also possible. More recently, we are investigating using provably secure steganography to achieve what we call Covert Computation.


Covert two-party computation allows two parties to determine, for example, whether they are romantically interested in each other without embarassing themselves: only if they are both interested do they find out if the other person is even trying to ask the question. (See the slides for my presentation at STOC on this topic.)

I am also interested in anonymous communication and usable security. Potentially the biggest security threats to our computing systems are the users. Humans forget passwords, reveal secrets, disable security measures for convenience, leave their identifying information unattended, etc. I work on a study of security that does not neglect humans simply because they cannot be precisely modeled or are difficult to deal with. It would be extremely important, for example, to design an alternative to passwords that is easy for humans, cheap, and secure even against an eavesdropper who can see multiple authentications.


Papers:


Luis von Ahn, Nicholas Hopper and John Langford
Covert Two-Party Computation
In STOC 2005


Luis von Ahn and Nicholas Hopper
Public-Key Steganography
In Eurocrypt 2004


Luis von Ahn, Andrew Bortz and Nicholas Hopper
k-Anonymous Message Transmission
In ACM CCS 2003


Nicholas Hopper, John Langford and Luis Von Ahn
Provably Secure Steganography
In CRYPTO 2002

Back Home   © 2006 Luis von Ahn, all rights reserved.