3
$\begingroup$

In a normal CAPTCHA scenario, a computer creates a challenge and a correct response to it. (The challenge is an image of distorted text, for instance, and the response is the characters depicted.) These are constructed so that hopefully a human can easily determine the response from the challenge, but a computer cannot. Ordinarily only the originating computer, which already knows the correct response, can determine whether a given response was correct.

My question: is it possible to create a CAPTCHA that computers can verify, but not solve? In other words, is it possible to create a scenario that looks like this:

Computer A generates a challenge, sends it to Human B and Computer C

Computer C cannot feasibly determine the correct response, other than by brute-force search (which can hopefully be made impractical by the size of the response.)

Human B can feasibly determine the correct response. ("Feasibly" is not easy to define. We need the response to be much bigger than normal CAPTCHAs in order to deter simple brute-force searching by computers, so "as easy as a normal CAPTCHA" is going to be impossible. But it's not out of the realm of possibility to make a human type in a large response. It'd just be really annoying. A few hundred printable characters can get to 2048 bits, for instance. So as a rough definition: it's allowed it to be annoying as hell, but it has to at least be feasible for a person. Assume the person's physical and mental abilities are roughly average for a literate computer user.)

If Human B sends Computer C the correct response, Computer C can feasibly verify that the response is correct, without contacting computer A or having any prior knowledge other than the challenge.

Would it be possible, under today's technology and knowledge, to create such a protocol?

Furthermore, would it be possible to design the protocol such that even Computer A can't determine the correct response to the challenge it just generated without human input--and Computer C can verify that Computer A could not have known the response without a human providing the solution? If this all this can be achieved, then the result is analogous to the "proof of work" seen in bitcoin and other protocols. Instead of a proof of computational work, we'd have a proof of human work--the combination of the challenge and correct response would constitute proof that a human spent some marginal amount of effort. This proof would then be verifiable by any computer. Is such a thing even remotely plausible?

Of course, at some point in the future computers will probably overtake humans altogether. Once that happens, there will not be any problems that are feasible for a human but not a computer, and therefore no CAPTCHAs or CAPTCHA-like protocols will be possible.

But what about under currently known human and computer abilities?

$\endgroup$
2
  • 1
    $\begingroup$ I'm not sure this question has an answer: you are asking for (dis)proof of the Church-Turing hypothesis. A more interesting question is: what are problems that humans solve with high probability in seconds and whose solutions machines can efficiently verify, but machines take a long time to solve themselves? Then, you should probably explain why existing Captcha systems are not an answer. $\endgroup$
    – Raphael
    Mar 23, 2014 at 13:06
  • $\begingroup$ Hmm...maybe I should clarify--I thought that "what are problems that humans can solve with high probability in seconds and whose solution machines can explicitly verify, but machines take a long time to solve themselves" is exactly the question I asked. Existing CAPTCHAs require communication between two computers before one can prove to the other that a human is present. What I'm after is an offline way to do this--one computer can prove to the other that it had a human do something, even if the other computer can't communicate back. $\endgroup$
    – Micah
    Mar 23, 2014 at 17:16

1 Answer 1

2
$\begingroup$

Yes. Computer A can generate a CAPTCHA encoding a 24-digit code, and also compute a cryptographic hash of the correct response. Computer A can give the CAPTCHA and the hash to B and C. Now if B claims to have solved the CAPTCHA, computer C can verify the claimed answer using the cryptographic hash. The cryptographic hash doesn't help computer C solve the challenge, because the hash is one-way and cannot be inverted (except by trying all possible codes, but that would take far too long).

In practice, this is not very effective, because no one knows how to build a CAPTCHA that humans can solve but that is expensive for computers to solve. For one thing, there are black-market services that will solve CAPTCHAs for you at the price of about $1-2 per thousand CAPTCHAs solved, i.e., about 0.1-0.2 cents per CAPTCHA. For another, there are algorithms that break most CAPTCHAs with probability higher than we'd like. So ultimately, CAPTCHAs kinda suck. But the reasons they suck have nothing to do with verifiability. If we could make a CAPTCHA that didn't suck, we could probably build one that was verifiable in the sense you mention.

Also, if you were implementing this in real life, you'd make sure to use a slow hash (like PBKDF2, scrypt, or bcrypt) when hashing the code. But again, because CAPTCHAs have so many limitations, I'm not sure you'd want to implement this scheme in real life anyway.

$\endgroup$
3
  • $\begingroup$ To generate two unrelated problems that happen to have the same answer, one of which can be solved by a human and another which can be verified by computer, seems a bit like cheating... $\endgroup$ Mar 23, 2014 at 9:09
  • $\begingroup$ This is fine if we trust computer A and believe that it will use the same value for the hash and the CAPTCHA. But there's no way for computer C to know that the hash it is verifying is the same as the CAPTCHA the human saw. I can't think of a way to verifiably tie them together... $\endgroup$
    – Micah
    Mar 23, 2014 at 14:41
  • $\begingroup$ Karolis - I'm fine with cheating if it achieves the application goals! @Micah - if there is an algorithmic way to generate the CAPTCHA, then in principle we could have computer A provide a zero-knowledge proof to prove that the CAPTCHA was generated in a way that is consistent with the hash. That would address your objection. Of course, this is all theoretical, for all sorts of reasons. $\endgroup$
    – D.W.
    Mar 23, 2014 at 21:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.