Paper 2012/689

Cryptography Using CAPTCHA Puzzles

Abishek Kumarasubramanian, Rafail Ostrovsky, Omkant Pandey, and Akshay Wadia

Abstract

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 (\cite{AhnBHL03}, 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 \emph{constant round} protocol for \emph{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 \emph{indirect access model}, for every polynomial time functionality $\calf$ there exists a protocol that UC-realizes $\calf$ using human-extractable \captcha, while for the so-called \emph{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 \emph{conservative} adversaries.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. PKC 2013
Keywords
CAPTCHAUCconcurrent non-malleable zero-knowledge
Contact author(s)
abishekk @ cs ucla edu
History
2013-01-16: last of 2 revisions
2012-12-10: received
See all versions
Short URL
https://ia.cr/2012/689
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2012/689,
      author = {Abishek Kumarasubramanian and Rafail Ostrovsky and Omkant Pandey and Akshay Wadia},
      title = {Cryptography Using CAPTCHA Puzzles},
      howpublished = {Cryptology ePrint Archive, Paper 2012/689},
      year = {2012},
      note = {\url{https://eprint.iacr.org/2012/689}},
      url = {https://eprint.iacr.org/2012/689}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.