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
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
-
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}, url = {https://eprint.iacr.org/2012/689} }