Cryptography Using Captcha Puzzles

A

Captcha

is a puzzle that is easy for humans but hard to solve for computers. A formal framework, modelling

Captcha

puzzles (as hard AI problems), was introduced by Ahn, Blum, Hopper, and Langford ([1], Eurocrypt 2003). Despite their attractive features and wide adoption in practice, the use of

Captcha

puzzles for general cryptographic applications has been limited.

In this work, we explore various ways to formally model

Captcha

puzzles and their human component and explore new applications for

Captcha

. We show that by defining

Captcha

with additional (strong but realistic) properties, it is possible to broaden

Captcha

applicability, including using it to learning a machine’s “secret internal state.” To facilitate this, we introduce the notion of an human-extractable

Captcha

, which we believe may be of independent interest. We show that this type of

Captcha

yields a

constant round

protocol for

fully

concurrent non-malleable zero-knowledge. To enable this we also define and construct a

Captcha

-based commitment scheme which admits “straight line” extraction. We also explore

Captcha

definitions in the setting of Universal Composability (UC). We show that there are two (incomparable) ways to model

Captcha

within the UC framework that lead to different results. In particular, we show that in the so called

indirect access model

, for every polynomial time functionality

$\ensuremath{\mathcal{F}}$

there exists a protocol that UC-realizes

$\ensuremath{\mathcal{F}}$

using human-extractable

Captcha

, while for the so-called

direct access model

, UC is impossible, even with the help of human-extractable

Captcha

.

The security of our constructions using human-extractable

Captcha

is proven against the (standard) class of all polynomial time adversaries. In contrast, most previous works guarantee security only against a very limited class of adversaries, called the

conservative

adversaries.