SCIS Event

Distinguished Turing Lecture Series

Toward a Theory of Humanly Computable Protocols

Date / Time:

Jan. 08, 2016 @ 02:00 pm


Florida International University
ECS: 241


Professor Manuel Blum
Carnegie Mellon University
Computer Science Department

Professor Manuel Blum


A PASSWORD SCHEMA is a humanly computable algorithm for transforming challenges--such as EBAY, GOOGLE, and AMAZON--into passwords. My question is whether there exists a password schema that enables a (competent) human to compute something of great value, his/her passwords- PRIVATELY (entirely in her/his head)--so that NO ADVERSARY- BE IT HUMAN, COMPUTER, or COMBO--can generate the password response to a new challenge. I will present a PUBLISHABLE HUMANLY USABLE SECURE PASSWORD CREATION SCHEMA (PHUSPCS--rhymes with toothpicks) that is: 1. WELL DEFINED (a program can run it), and PUBLISHABLE (everyone can know it), 2. HUMANLY USABLE by a normal dedicated human being, namely me (an experimentally provable concept), and 3. MACHINE UNCRACKABLE to a TINY but WELL-DEFINED EXTENT (provably so--by a simple information theoretic argument). This theory inevitably builds on ideas from both computer and cognitive science.


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. He did his doctoral work under the supervision of Artificial Intelligence pioneer Marvin Minsky, and earned a Ph.D. from MIT in mathematics in 1964. Blum began his teaching career at MIT as an assistant professor of mathematics and, in 1968, joined the faculty of the University of California at Berkeley as tenured associate professor of Electrical Engineering and Computer Sciences. He was Associate Chair for Computer Science, 1977-1980. He was named Arthur J. Chick Professor of Computer Science in 1995. Blum accepted his present position at Carnegie Mellon in 2001. 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 A ward, 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.