Abstract
Does there exists a family H of hash functions h with the property that
1. Any h in H is humanly computable: a human can select a random h∈H, then
- (preprocessing time) learn to compute h in at most a few (≤ 3?) hours, and thereafter
- (processing time) take at most 1 minute per input x_i to compute h(x_i),
but
2. NO ADVERSARY -- BE IT HUMAN, COMPUTER, OR COMBINATION OF THE TWO -- that
- knows the family H but not which particular h was chosen, and
- observes (just) enough pairs (x1, h(x1)), (x2, h(x2)), (x3, h(x3)), ... (for randomly chosen x1, x2, x3, ...) to completely specify h, can (with nontrivial probability) compute h(x) on a new randomly chosen x.
This talk will deal with this question for humans that compute h in their heads matched against a powerful human + supercomputer (10¹⁸ instructions per second) adversary. The adversary wins in the first round, Q, at which it correctly guesses h(x) for a new randomly chosen x.
Human computability has numerous applications including CAPTCHAS and humanly computable passwords.