Lecture: Toward a Theory of Humanly Computable Protocols

Manuel Blum

Abstract:

ALGORITHMS are instructions for single agents. PROTOCOLS are instructions for multiple agents. Agents may be specified to be humans or computers.

Our GOAL is to know which cryptographic problems can be solved by protocols that specify certain agents to be human. We are especially interested in the case in which each human does all computations entirely in his/her head (in all dealings with the other agents).

QUESTION: Can a human compute something/anything PRIVATELY -- entirely in his head --
that NO ADVERSARY -- BE IT HUMAN, COMPUTER, OR COMBINATION OF THE TWO -- can reasonably get hold of? In particular, can a human compute a private hash function h(x1), h(x2),...
• with just a few (3?) hours of preprocessing to learn h, and just 1 minute of processing per input xi to compute h(xi), so that
• a human/computer combo that observes a small number of pairs (x1, h(x1)), (x2, h(x2)), … but does not otherwise know h (because it is private and hard to infer) cannot compute h(x) on a new x.

EXAMPLE 1: PRIVATE KEY ENCRYPTION with n randomly chosen n-bit strings (ONE-TIME PADS) for small n.

EXAMPLE 2: PASSWORDS.
Definition: A PASSWORD SCHEME is an algorithm for producing passwords in response to given challenges (typically domain names).

THEOREM: there exists a PASSWORD SCHEME that is
1. WELL DEFINED (a mathematical concept),
2. HUMANLY USABLE by a normal dedicated human being, namely me (an experimentally demonstrable concept),
3. MACHINE UNCRACKABLE to a small well-defined extent (as determined by the password game).

---