Talks

Fall 2015

# Human Computation

Monday, September 28th, 2015 9:30 am – 10:15 am

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.