ARC & IISP Distinguished Lecture by Manuel Blum

The Algorithm & Randomness Center and the

Institute for Information Security & Privacy present

Manuel Blum

1995 Turing Award Winner & Professor, Carnegie Mellon University

Human Computation with an Application to Passwords

Abstract  |  Human computation: This talk presents a simple model of human computation based on well-known features of long- and short-term human memory. The intention of the model is to bring computer science ideas and understanding to bear on the kinds of computations that humans can (and cannot) consciously perform in their heads.

This work has applications to the study of problems that humans might want to solve in their heads, like how to solve crossword puzzles, play speed chess, and various cryptographic problems.

The running example in this talk will be password generation wherein humans - working entirely in their heads - transform website names into random-looking passwords that are provably hard to forge.

Application to passwords: Nowadays, the best password advice suggests, for each website, to either select and memorize four random picturable words (XKCD), or choose a memorable sentence and use the first letter of every word for the password.

One problem with all such proposals is that they don't indicate how to link website names to passwords. In effect, they would have you generate and memorize a special purpose password for every website. Little wonder that few people do this.

We recommend instead to use a humanly computable algorithm (schema) to transform website names into passwords on the fly. Schemas enable a human to have a (completely) different password for every website, to never have to write passwords down, and to be able to test password quality without giving any passwords away. They also enable us to analyze the Quality of Password Schemas mathematically.

Joint work with Santosh Vempala.

About  |  Manuel Blum, the Bruce Nelson University Professor of Computer Science at Carnegie Mellon University, is a pioneer in the field of theoretical computer science and the winner of the 1995 Turing Award in recognition of his contributions to the foundations of computational complexity theory and its applications to cryptography and program checking, a mathematical approach to writing programs that check their work.

The problems he has tackled in his long career include, among others, methods for measuring the intrinsic complexity of problems. Blum’s Speedup theorem is an important proposition about the complexity of computable functions. The Blum axioms give a machine-independent way to understand the complexity of computation, whether that computation is done by human or by computer. Since his early work on the intrinsic limitations of computing devices, Blum’s research has focused on the single unifying theme of finding positive, practical consequences of living in a world where computational resources are bounded. In his work, Blum has shown that secure business transactions, pseudo-random number generation, program checking, and more recently, CAPTCHAs for detecting bot intruders, are possible in part because all computational devices are resource bounded.

Blum’s current research includes the HumanOID (Human Oriented ID) project, a cryptographic project designed to develop a challenge-response authentication protocol that humans can perform entirely in their heads. For this, people must be able to authenticate themselves to a system while a powerful machine-based adversary that knows the protocol listens on the line and records every challenge and response. The system would have to be incapable of learning to impersonate that human.

A member of the National Academy of Sciences and the National Academy of Engineering, he is a fellow of the American Academy of Arts and Sciences, the American Association for the Advancement of Science, and the Institute of Electrical and Electronics Engineers. Dr. Blum has held a Sloan Foundation Fellowship and received a University of California at Berkeley Distinguished Teaching Award, their Faculty Research Award, the Sigma Xi’s Monie A. Ferst Award, the Carnegie Mellon Herbert A, Simons Teaching Award, among other honors. He is the author of more than 50 papers published in leading scientific journals and has supervised the theses of 35 doctoral students who now pepper almost every major computer science department in the country. The many ground-breaking areas of theoretical computer science chartered by his academic descendants are legend.