\documentclass[twocolumn]{article}

\usepackage{graphicx} 
\usepackage{amsmath}
\usepackage{amsfonts}

\newtheorem{thm}{Theorem}[section]
\numberwithin{equation}{section} %% Comment out for sequentially-numbered
\numberwithin{figure}{section} %% Comment out for sequentially-numbered
 
\begin{document}
\title{Telling Humans and Computers Apart (Automatically)\\ or\\ How Lazy
Cryptographers do AI}
\author{Luis von Ahn\footnotemark[1] \and Manuel
Blum\footnotemark[1]
\and John
Langford\footnotemark[1]
}

\maketitle

\begin{abstract} {\it Classical cryptography has often factored humans out
of the equation:  when we say Alice and Bob can communicate securely (or
authenticate, or sign, or perform a zero knowledge proof), we really mean
Alice and Bob's {\em computers} can communicate securely. This has
resulted in humans being a major security hole in practice. In this paper
we attempt to formalize the study of a cryptography that doesn't neglect
humans.  We introduce the concept of a {\sc captcha}: a program that can
differentiate between humans and computers based only on interactions over
a computer network. We also generalize this concept to the notion of Human
Interactive Proofs (HIPs), and show how HIPs generalize several previous
attempts at formalizing the role of humans in cryptography.}
\end{abstract}

\footnotetext[1]{Computer Science
Dept., Carnegie Mellon University, Pittsburgh PA 15213.
\{biglou,mblum,hopper,jcl\}@cs.cmu.edu
}

\section{Introduction}

At some point in history, after the invention of the computer, humans were
kicked out of cryptographic protocols. Today they are mostly regarded as a
problem: users choose passwords that are easy to guess, users accidentally
reveal their private keys \cite{TYGAR}, etc. In this paper we attempt to
bring the human users back into the picture. We do so by first introducing
the solution to a basic problem in human-related cryptography: telling
human users apart from computers (or `bots'). 

The applications of this line of research are almost endless. And, in
particular, the program for telling humans and computers apart described
in this paper is currently used by Yahoo to prevent `bots' from
automatically registering for free email accounts \cite{YAHOO}. 

This paper will show an interesting relationship between cryptography and
Artificial Intelligence (AI), which we think is representative of the kind
of issues that come up when dealing with human-related cryptography.  

Human-related cryptography has been studied before \cite{HOP,MN1}.  Our
contributions are as follows: We introduce a formal framework for
human-related cryptography and we introduce the concept and the
formal study of {\sc captcha}s (programs that can tell whether their user
is a human or a computer). The initial presentation of {\sc captcha}s
and the issues related to them (Section 2) will be
presented in everyday, informal language. We feel this is the best way to
introduce the concepts and issues. Section 3 will formalize our
discussion. 

\section{Gotcha!}

Intuitively, a {\sc captcha} is a program that can generate and grade test
that:  
\begin{enumerate} 
\item Most humans can pass 
\item Current computer programs cannot pass.  
\end{enumerate} 

(The words ``Most'' and ``Current'' will be precisely defined later. Bare
with us for now.) The {\sc p} in {\sc captcha} stands for Public: the code
for the program should be commented and easy to understand; additionally,
the commented code and all the data used by a {\sc captcha} should be
public. Thus a program that can generate and grade tests that distinguish
humans from computers but whose code or data are private is {\it not} a
{\sc captcha}. 

{\sc captcha} stands for ``Completely Automated Public Turing Test to Tell
Computers and Humans Apart''. Why Turing Test? Because a {\sc captcha} is
like an automated version of the Turing Test \cite{TURING}, one in which
the judge
is a computer.


\subsection{Examples}

Let's now look at few examples of {\sc captcha}s. When reading, you should
convince yourself that each of these is indeed a valid example of a {\sc
captcha}. The code and demos for all the programs described in this
section can be
found online at {\it www.captcha.net}.   

\begin{itemize}

\item {\bf Gimpy.} Consider the following program, which we will
refer to as {\sc
gimpy}
({\sc gimpy} will be our first example of a {\sc captcha}; the assertion
that {\sc gimpy} is a {\sc captcha} requires proof, but this proof will be
delayed until later---remember, this is still an informal discussion.)
{\sc gimpy} works as follows: it first picks seven words out of a
dictionary and renders the words into a distorted image (as shown in
Figure 2.1). {\sc gimpy} then presents a test to its user, which consists
of the distorted image and the directions: {\it ``type three words
appearing in
the image''}. Given the types of deformations that {\sc gimpy} uses, most
humans can read three words from the distorted image, while current
computer programs cannot.

\begin{figure}[h]
  \begin{center}
    \includegraphics*[scale=.4]{gimpy_sample.ps}
\caption{A sample {\sc gimpy} image.}
  \end{center}
\end{figure}

\item {\bf Bongo.} Another example of a {\sc captcha} is the program
we call {\sc
bongo}\footnote{{\sc bongo} is named after M.M. Bongard, who published
a book of pattern recognition problems (\cite{BP}) in 1951.}. 
{\sc bongo} asks the user to solve a visual pattern
recognition problem. In particular, it displays two series of blocks
(the {\sc Left} and the {\sc Right}). The blocks in the {\sc Left} series
differ from
those in the {\sc Right}, and the user must find the characteristic that
sets
them apart. A possible {\sc Left} and {\sc Right} series are shown below:

\begin{figure}[h]
  \begin{center}
    \includegraphics*[scale=0.8]{bongo_sample1.ps}
\caption{Sample {\sc bongo} {\sc Left} and {\sc Right} series.}
  \end{center}
\end{figure}

(These two series are different because everything in the {\sc Left} is
drawn
with thick lines, while everything in the {\sc Right} is drawn with thin
lines.)
After seeing the two series of blocks, the user is presented with four
single blocks and is asked to determine whether each block belongs to the
{\sc Right} series or to the {\sc Left}. The user passes the test if he or
she
correctly determines the side to which each of the four blocks belongs.
Try it
yourself: to which side does the isolated block in Figure 2.3 belong?

\begin{figure}[h]
  \begin{center}
    \includegraphics*[scale=0.8]{bongo_sample2.ps}
    \includegraphics*[scale=1.0]{bongo_sample3.ps}
\caption{To which side does the bottom block belong?}
  \end{center}
\end{figure}

\item {\bf Pix.} Yet another example of a {\sc captcha} is a program
that has a large
database of labeled images (like \cite{GETTY,CORBIS}). All of these images
should be
pictures of concrete objects (a horse, a table, a house, a flower, etc).
The
program picks an object
at random, finds 6 random images of that object from its database,
presents them to the user and then asks the question {\it ``what are these
pictures
of?''} (See Figure 2.4.) Current computer programs should not be able to
answer this question.

The reader might notice that this example, as stated, is not a {\sc
captcha}. Why? Because it is very easy to write a program that can answer
the question ``what are these images of?'' Remember that all the code and
data of a {\sc captcha} should be publicly available; in particular, the
image database that the previous program uses should be public. Hence,
writing a program that can answer the question is easy: search the
database for the images presented and find their label.  In order for this
program to actually be a {\sc captcha}, the images need to be randomly
distorted before being presented to the user, in such a way that searching
the database for the images is hard for computer programs. 

\item {\bf Sounds.} The final example we will consider can be thought of
as a sound version of {\sc gimpy}. The program picks a word or a sequence
of numbers at random, renders the word or the numbers into a sound clip
and distorts the clip.  It then presents the distorted sound clip to its
user and asks the user to type in the contents of the sound clip. 

\end{itemize}

The creation of {\sc captcha}s is an interesting endeavor in itself and
later we will see why it is good to have a wide variety of {\sc captcha}s.
We end this section by remarking that it is still an open problem to
create a text-based {\sc captcha} (one which doesn't use any images or
sound clips).  

\subsection{The Enemy}

We will consider {\sc captcha}s from the perspective of cryptography so we
need the notion of an enemy. In our case, {\sc The Enemy} will be the
person trying to write a program that can pass the tests generated by a
{\sc captcha}. Intuitively, we will assume that {\sc The Enemy} is an
expert programmer with:
\begin{itemize}
\item Complete knowledge of the code and data used by the {\sc captcha}
\item Full access to the web
\item A super computer
\item Lots of free time
\end{itemize}

We want to prove or give evidence that it is hard for {\sc The Enemy} to
write a program that can pass the tests generated by a {\sc captcha}.

\subsection{Reductions to Hard AI Problems}

How do we {\it prove} that computer programs will never pass the tests
generated by a {\sc captcha}? Unfortunately, we believe there is no way to
prove such a strong statement:  since humans can pass the tests, proving
that computer programs cannot pass them would show that there exist things
that humans can do but computers can't. We (the authors) believe that some
day computers will be as good as humans (and possibly better) in every
respect.

The best we can do is to present evidence that, given the current state of
technology, it is hard to write a program that can pass the tests
generated by a {\sc captcha}. We will do this by proving the following
statement: {\it Any program that passes the tests generated by a {\sc
captcha} can be used as an oracle to solve a hard unsolved Artificial
Intelligence (AI) problem.}

The previous statement requires explanation and justification.
(Hopefully, we will be able to convince the reader that a reduction to a
hard AI problem is the right notion of security for {\sc captcha}s.)

\begin{itemize} 

\item First, by ``[a] program that passes the tests generated by a {\sc
captcha}'', we mean a program (possibly probabilistic)  that has some (not
so small, but precisely defined) probability of passing a given random
test generated by the {\sc captcha}. 

\item What is a hard unsolved AI problem? Intuitively, it is an AI problem
that remains unsolved despite the fact that the AI community has been
working on it for several years. For the proof of this theorem to go
through, an AI problem needs to be {\it precisely} defined. It is a good
exercise for the reader to try to define AI problems in precise terms.     

\item Why does this give evidence that it is hard to pass the tests
generated by a {\sc captcha}? If an AI problem remains unsolved after many
intelligent people have been working on it for a long time, then it is
hard to write a program that can solve this problem. Our statement says
that it is at least as hard to write a program that can pass the tests
generated by a {\sc captcha}.

\end{itemize} 

Notice that classical cryptography is laid on a foundation similar to
ours: cryptographers only {\it assume} factoring is hard.    

At this point we can interject with a curious graph:

\subsection{P Stands for Public. Why?}

Several people (especially those outside the cryptography community)
have objected to {\sc captcha}s having publicly available code and data.
They claim that {\sc captcha}s would be more secure if the code was
hidden. Here, we will state why we
want all the code and data used by a {\sc captcha} to be publicly
available. 

\begin{itemize}

\item {\bf Hackers}. If a {\sc captcha} requires some private data in
order to be secure, then this {\sc captcha} is very vulnerable to hacker
attacks: once a hacker breaks into the system and finds this secret data,
the {\sc captcha} seizes to be secure forever. We want {\sc captcha}s to
generate tests that are hard to pass for all computers; not that are hard
to
pass for computers that don't have some secret.

\item {\bf Reverse Engineering}. {\sc The Enemy} can learn a lot about the
way a {\sc captcha} works and all the data it uses by simply taking many
of the tests generated by a {\sc captcha}. 

\item {\bf Analysis}. Moreover, there is no general way to know exactly
how much {\sc The Enemy} can learn about how a {\sc captcha} works.
Hence, we may as well assume that {\sc The Enemy} can learn {\it exactly}
how the {\sc captcha} works and then prove that {\it even in this case} it
is hard for {\sc The Enemy} to write a program that can pass the tests
generated by the {\sc captcha}

\item {\bf We're doing AI}. We {\it want} our {\sc captcha}s to be broken!
Why? Because if a {\sc captcha} is broken, then a previously unsolved AI
problem is solved. This is how lazy cryptographers do AI! We help {\sc The
Enemy} as much as we can in breaking our system. 

\end{itemize}

\subsection{Applications}

{\sc captcha}s have several applications. Here we mention just a few.

\begin{itemize} 

\item {\bf Online Polls.} Almost two years ago (we've lost the date), {\it
slashdot.com} released an online poll asking for the best school in
computer science (a dangerous question to ask over the web!). As it is the
case with most online polls, IP addresses of voters were recorded in order
to prevent single users from voting more than once. However, students at
Carnegie Mellon figured out a way to stuff the ballots and wrote programs
that voted for CMU thousands of times. CMU's score started growing
rapidly.  The next day, students at MIT wrote {\it their} own program and
the poll had become a contest between voting ``bots''. MIT finished with
21,156 votes, Carnegie Mellon with 21,032 and every other school with less
than 1,000. 

The point is that any online poll suffers from this weakness. But {\sc
captcha}s offer a solution to this problem: voters should ``prove'' they
are human before being allowed to vote. 

\item {\bf Free Email Services.} Several companies offer free email
services over the web. Most of these suffer from a specific type of
attack:  ``bots'' that sign up for thousands of email accounts a minute.
In particular, web pornography companies use such tactics to obtain free
email accounts from which they can send advertisements. A solution to this
problem is to have users solve a {\sc captcha} test before they can get an
account. Yahoo has adopted this solution, and, in fact, uses a variation
of our program {\sc gimpy}.

\item {\bf Search Engine Bots.} You may not want to have your web page
indexed. It is sometimes surprising how much others can learn about you by
just typing in your name in google or altavista. There is an {\it html}
tag to prevent bots from reading your web page. The tag, however, doesn't
guarantee that bots will not read your web page; it only serves to say
``no
bots, please''. Search engine bots, since they usually belong to large 
companies, usually respect web pages that don't want to allow
bots. However, if you want to guarantee that bots will not enter your
web-site, you need to have your viewers prove that they are indeed human
before letting them in.  

\item {\bf Shopping Agents.} Many web pages offer free shopping to their
users, along with extremely low prices. Part of the reason these companies
can offer such a service is because of advertisements. However, there are
several ``shopping bots'' available, which visit many shopping sites and
retrieve the best prices from all of them. These shopping agents are bad
for the shopping sites because users don't get to see the advertisements.
A solution to this problem is for the shopping sites to put a {\sc
captcha} test before revealing their prices, to ensure that only humans
visit their site. 

\end{itemize}

\subsection{Stealing Cycles From Humans}

Some readers might have noticed that {\sc captcha}s really aren't a good
solution the the Shopping Agent problem. Why? Because if
shopping sites display {\sc captcha} tests before allowing their users to
see the prices, the shopping agents can simply ask the human behind the
computer to solve the {\sc captcha} test. 

And, in fact, this same strategy can be used to defeat {\sc captcha}s in
many cases. We call it ``stealing cycles from humans''. Consider free
web porn companies, for instance. These companies can still obtain
thousands of free email accounts even if the email provider uses {\sc
captcha}. How? The porn companies can have bots that try to get free email
accounts, and as soon as the bots encounter a {\sc captcha} test, they
simply send the test to the porn site. Back at the porn site, there are
several thousands of users seeing free pornographic pictures, and one of
them is told: ``please solve the following test before we can show you the
next picture''. 

This leads to an interesting digression. Notice how stealing cycles from
humans works: humans were used to expand the computational abilities of
the porn company bots. In general, how can we use humans as oracles to
expand our computational abilities? Currently, there are several things
that humans can do but computers can't: recognize facial expressions from
any angle, understand language, read distorted text, recognize which
animal is in a picture. Can we use humans in some way to make computers
solve these problems in a distributed manner? A kind of SETI@home
project in which web users help to classify all books in the library of
congress. 

If you visit {\it www.hotornot.com}, for instance, you will get a picture
of a person (man or woman) and you are supposed to rate how attractive you
think the person is (on a scale from 1 to 10). After you rate the person
you get to learn what other users have said about this person and you also
get to see another person which you can rank. What's interesting about
this site is that it is very popular and catchy: the authors have seen
entire offices of graduate students rating pictures. Can these human
cycles be used for something? we can envision a program that can tell you
which is the best haircut for you: you enter it a picture of yourself and
it sends several copies of this picture to {\it www.hotornot.com}, all
with different hair styles. Whichever gets the highest ranking is the
best.

In fact, the whole idea of a {\sc captcha} can be seen under the light of
``stealing cycles''. {\sc captcha}s are the ultimate tools for stealing
cycles from intelligent people: malicious, intelligent programmers can be
put to work on hard unsolved AI problems.

\subsection{Epilogue}

The little story about {\sc captcha}s ends here. Visit {\it
www.captcha.net} to see the implementations of the examples mentioned
above. All the code and data used by these programs can also be found
there (remember, P stands for Public).

\section{Human Interactive Proofs}


\begin{thebibliography}{2}
\bibitem{MN1} Moni Naor and Benny Pinkas. Visual Authentication. In: {\it
Crypto 97}. August, 1997.
\bibitem{MN2} Moni Naor. Verification of a human in the loop or
Identification via the Turing Test. Unpublished.
\bibitem{C} Luis von Ahn, Manuel Blum, Nicholas Hopper and John
Langford. The Captcha Project {\it http://www.captcha.net}. 
\bibitem{BP} Mikhail Moiseevitch Bongard. (1970). {\it Pattern Recognition}. Rochelle
Park, N.J.: Hayden Book Co., Spartan Books.
\bibitem{HOP} Nicholas J. Hopper and Manuel Blum. Secure Human
Identification Protocols. In: {\it Asiacrypt 2001.} 
\bibitem{TYGAR} Alma Whitten and J.D. Tygar. Why Johnny Can't Encrypt.
In: {\it Proceedings of the 9th USENIX
Security Symposium} August 1999. 
\bibitem{YAHOO} Yahoo
\bibitem{ABILITY} Proofs of Ability
\bibitem{TURING} Alan M. Turing. Computing Machinery and Intelligence. In:
{\it Mind, Vol. 59, No. 236, pp. 433-460}. 1950. 
\bibitem{CORBIS} Corbis Images
\bibitem{GETTY} Getty Images

\end{thebibliography}

\end{document}




