Rafail Ostrovsky - Publications

Cryptography Using Captcha Puzzles

Abishek Kumarasubramanian, Rafail Ostrovsky, Omkant Pandey, Akshay Wadia


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]), Eurocrypto 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 ecplore various ways to formally model CAPTCHA puzzles and their human component and explore new applications fo CAPTCHA. We show that by defining CAPTCHA with additional (strong but realistic) properties, it is possiable to broadedn CAPTCHA applicability, including using it to leaning a machine's “secret internal state”. To facilitate this, we introduce the notion of an human-extractable CAPTCHA, which we belive may be of independent intrest. We show that this type of CAPTCHA yields a constant round protocol forfullynon malleable zero-knowledge. To enable this we also define and construct a CAPTCHA-based commitment scheme which admits “straightLine” extraction. We also explore CAPTCHA-definitions in the setting of Universal Compostability (UC). We show that there are two (incomparable) ways to model CAPTCHA within the UC framework that lead to diffrent results. In particular, we show that in the so called indirect access model, for every polynomial time functionality\ ensurenathF there exists a protocol that UC-realizes\ ensuremathF 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.

comment: Public Key Cryptography 2013: 89-106

Fetch PDF file of the paper

Back to Publications List