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
|
|