Cryptography Using Captcha Puzzles
A Captcha is a puzzle that is easy for humans but hard to solve for computers. A formal framework, modeling Captcha puzzles (as hard AI problems), was introduced by Ahn, Blum, Hopper, and Langford. Despite their attractive features and wide adoption in practice, the use of Captcha puzzles for general cryptographic applications has been limited. In this paper, the authors explore various ways to formally model Captcha puzzles and their human component and explore new applications for Captcha. They 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, they introduce the notion of a human-extractable Captcha, which they believe, may be of independent interest.