Manuel Blum University Professor Emeritus Website Office 5013 Gates and Hillman Centers Email mblum@cs.cmu.edu Phone (412) 268-3742 Department Computer Science Department Administrative Support Person Charlotte Yano Research Interests Algorithms and Complexity Cryptography Security and Privacy Research/Teaching Statement My current research projects include: 1.1 The CAPTCHA project. CAPTCHA is an acronym for "Completely Automatic Public Turing Test To Tell Computers Humans Apart." It is a kind of automatic sentry, a test that is made up, administered, and graded by a computer in order to permit humans but not bots to enter the Garden of Eden. One of the paradoxes of this project is to show how a computer can generate and grade a test that it (the computer itself) cannot pass! Current Captchas do this by putting a randomly chosen string of characters on a rubber sheet. They then deform the sheet to the point that OCR (Optical Character Recognition) cannot read the characters. Humans can read the deformed image, just as they can read the writing on a stained and twisted piece of paper. While the Captcha tester itself cannot read the deformed image, it can grade the test. This is because it remembers its initial choice of characters. 1.2 A good sound-based Captcha is needed for blind people (the blind are stopped by visual Captchas). I'm looking for someone interested to try her/his hand at this. 1.3 The Ultimate OCR (Optical Character Recognition) project. The Ultimate OCR is a program that can read anything that humans can read. ***NOTE: I do not propose to create the Ultimate OCR but to get the vision community to create it for us.*** The approach to the Ultimate OCR is to build an Ultimate Captcha that can ONLY be read by a human or by a device that can read everything that humans can read. We have ideas how to build such a device, but need someone to think these ideas through with us, make improvements, and then build the Captcha. This Ultimate Captcha would serve as a challenge to the Vision Community. As with previous challenges we have set, this challenge will almost certainly be taken seriously as it would be a maximally powerful automatic test of ability to read text. A bot that could pass this test would be able to read anything that a human can read. It's code would therefore constitute an Ultimate OCR. This work is joint with Luis von Ahn and anyone whom we accept to work on it with us. 2.1 CONSCSness: CONSCS = CONceptualizing Strategizing Control System. This project is a top-down complexity theoretic approach to understanding consciousness. The intent is to set down a very small number of axioms for CONSCSness and then prove theorems about the concept. Hopefully the theorems will make sense and teach us something about how to build a CONceptualizing Strategizing Control System. This work is joint with Ryan Williams and Brendan Juba. 2.2 Proof triangles. (Definition triangles. Algorithm triangles. etc.) One concrete consequence of our study of CONSCSness is a new view of proof that extends the traditional formal concept of proof to something that we call a "proof triangle." A proof triangle has a formal mathematical proof at the base of the triangle. The apex of the triangle is a bare minimal hint. The next level might be a more extended hint. The next a proof idea. Then a proof outline. Then several levels of informal proof, leading to the final complete formal proof. None of these levels is uniquely specified. There are many different hints possible just as there are many different formal proofs. Most mathematicians consider their theorems proved when they get a relatively high intermediate level of proof. Machines currently work only at the most formal level of proof. Little wonder that while machines can check proofs, they have difficulty constructing proofs. Our goal is to create machines that can prove nontrivial theorems. This work is joint with Matt Humphrey, Brendan Juba, and Ryan Williams. 3. The Human Oriented ID project. This is a cryptographic project to develop a challenge-response authentication protocol that a human can do entirely in his head: The human must be able to authenticate himself to a computer while a powerful adversary (one with a CRAY) -- who knows the protocol, listens on the line, and records every challenge and response -- should be incapable of learning to impersonate the human. This is a very hard problem.
