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.