39th Annual Killian Award Lecture—Ronald L. Rivest

PRESENTER: I want to begin by thanking Alan Oppenheim and his committee for their hard work in the selection process and for their good judgment in choosing Professor Ronald L. Rivest as the Killian Award recipient for this year. Many of you know Ronald from his great work in computer science and electrical engineering, and in CSAIL. And so the real main event here is to hear his speech. So I will be very brief and giving you just a small introduction to Ron and to his background.

He was born in Niskayuna, New York-- which is good Indian name for a New York-- the state of New York. Did his undergraduate, graduate degrees at Yale and at Stanford, and joined the MIT faculty here in the Department of Computer Science-- or what became the Department of Computer Science and Electrical Engineering-- in 1974. He is known best as one of the founding fathers of modern cryptography.

And we're going to hear about the growth of cryptography in his lecture here today-- particularly in what's called the public keys activities and component of cryptography. And the shorthand version, as I understand, of the impact of his work is, he allows us to use the internet with some degree of security, and some degree of safety, and maybe some degree of confidence that all of our mistakes-- which some of us, as some people in this audience know better than others, are prone to make in using the internet or using email as we go along.

In particular, he and two of his colleagues-- Professor Shamir and Professor Adleman-- developed something that's appropriately known as the RSA system, after their initials. And this is a particularly appropriate MIT invention, because his colleagues describe it as elegant, simple, abstract, and immensely practical. I can't think of a better way to describe MIT's values in working across that whole spectrum of innovation from discovery to application. And in fact, he's carried this into the commercial world by developing two different organizations-- one, RSA Security Systems, and then a second company called VeriSign Incorporated. So he's not only worked on the discovery and development, but also taking this into the real world of practice and application.

But in addition to his great scholarly work, he's also known as a very accomplished teacher and mentor, together with two colleagues, Thomas Cormen and Charles Leiserson. He is author of a leading textbook on algorithms for his field. And as you know, we have this thing that I've come to know as CSAIL. And maybe we can give a quiz to see if you can figure out what the acronym is.

But it is the largest laboratory here on campus. It's a laboratory that was put together by merging the AI, the Artificial Intelligence Lab, with the Laboratory on Computer Science. And knowing something about some of the personalities who were associated in the earlier years with these two institutions, that is no small achievement.

And so Ron is really the quintessential MIT Professor. He does path-breaking work in his research. He carries it through to have an impact on society.

He maintains his commitment to education here in the Institute and worldwide through his publications and textbooks. And he works to help make this place run effectively, not only in bringing scholars together to work in a common laboratory, but also to build the kind of spirit and the kind of community that lead his peers to recognize his professional achievements in the field, his contributions to MIT, and his contributions as a citizen and a friend in our community. So I'm delighted to congratulate Ronald L Rivest on the Killian Award achievement and welcome him to the podium.

[APPLAUSE]

So the award reads, "The president and faculty of the Massachusetts Institute of Technology have the honor to present the James R Killian Jr Faculty Achievement Award for the academic year 2010 to 2011 to Ronald L Rivest, in recognition of his extraordinary contributions to modern cryptography and to the field of computer science, and for his dedication to MIT as a teacher, mentor, and educator. So, congratulations.

[APPLAUSE]

And now for the main event.

RIVEST: We'll get started. I think we should turn up the microphone. Can you hear me? It sounds like it's on, yes. Start by thanking you, Tom, for the introduction, and thanking MIT and the selection committee for this is wonderful award.

MIT is really an extraordinary place, and to be recognized by one's peers with an award like this is really very special-- particularly 150th birthday of MIT. So I really appreciate it. Thank you to everyone who participated in the process for the presentation. Thank you.

So I'd like to talk about what I've been up to. It was hard to figure out how to prepare for this talk. Basically the question is, what have you been up to for the last few decades, and why are they giving you this award, and so on. So to talk about cryptography, enlarge it a bit, I'll talk about what I've been doing. But I'd like to set it in a larger context-- talk about the growth of cryptography, some of its roots, and where it's going a bit too. So I'll talk, emphasizing what I do and emphasizing the field more to try to set it in context.

So my target audience is really the students here, best, who haven't been paying attention to this field at all and want to learn something about it. So I have slides somewhere. Can we have my slides? Maybe my laptop is dead.

There we go. Ah, password needed.

[AUDIENCE LAUGHS]

That wasn't planned. That was my screen saver. All right.

So let's get started. So I actually have quite a bit to talk about. And we'll just dive right into it. I'd like to give a historical narrative for the field a bit, and then sort of position my work with within that.

So we'll talk a bit about what happened prior to '76, the invention of public key and RSA. Some of the early steps of seeing the technology get out beyond those early inventions, a few slides about the cryptography business, cryptopolicy-- which is still with us, but it seems to have died down pretty much as an issue of debate. Some of the cryptographic attacks of interest, where's the field going, some new directions, what's next, conclusions, acknowledgements-- so that's the menu. Starting off with the earliest days, let's start with the Greeks. Everything starts there.

Euclid had a proof that there are infinitely many primes-- 2, 3, 5, 7-- so they go on forever. That's nice. We can use them, as many as you like. So we have that.

We also have his wonderful algorithm, called Euclid's algorithm, that allows you to find the largest number that divides two given numbers. 12 and 30 have 6 as their greatest common divisor. We knew that as well.

The Greeks practiced cryptography in an elementary way. One of the ways they had was to write a message on a leather scroll, wrap it around a stick of circumference unknown to the enemy, and then pass the leather strip without the rod to the recipient. So the period, the circumference of that rod, was the shared secret. So that shared some of the characteristics of not public, but conventional cryptography, where there's a shared secret between sender and receiver and in the case an unknown period plays a role with RSA as well, as we'll see.

Periodicity plays a role in some number theory that comes into play. Fermat-- best known for his last theorem, which he didn't prove-- is known also for his Little Theorem, which he didn't prove either. But he realized it was true. For any a less than p, if you take a to the p minus first power, you get a number which is a remainder of 1 when divided by p. So 2 to the 6th is 64-- divide that by 7, you get a remainder of 1.

Euler, perhaps the greatest mathematician of his time, proved Fermat's theorem and generalized it, as all good mathematicians do. So he showed that a to the phi of n is congruent to 1 mod n for any n, where phi of n is just the number of numbers less than n that don't share a common divisor with n. We need that theorem for the proof of the correctness of RSA. There's not gonna be a lot of math in this talk, don't worry. But that's an important theorem, 1736.

Perhaps the greatest mathematician ever was Gauss. He lived from 1777 to 1855. He just died before the founding of MIT. So 1861 was our founding, so just before that. At the age of 21, he wrote his famous book, Disquisitions Aritmeticae-- I think I'm mispronouncing that, probably-- and said, "The problem of distinguishing prime numbers from composite numbers and of resolving the latter into their prime factors is known to be one of the most important and useful in arithmetic. The dignity of science itself seems to require a solution of a problem so elegant and so celebrated."

Nice plug for the problem. Actually, he had it wrong. There's two problems there, and he confounded them. Right? There's the problem of telling whether a number is prime or not-- which turns out, actually, to be easy-- and then there's the problem of separating a number that's not prime into its prime factors-- which we think is hard, we hope is hard. But he sort of conflated those two problems together.

This fellow you may not have heard about. He's not well known in the computer science field, actually. He was an economist-- he was worried about Britain running out of coal, he had lots of interesting things to say about energy usage-- and a logician. But the reason I like him is, he gave the world's first factoring challenge.

In 1874 he published a book on the philosophy of science, saying, "What two numbers multiplied together will produce 8626460799?" This is a measly 10-digit number, but at the time it seemed out of reach for factoring. It's about the size of a phone number, right? You can factor this on your smartphone.

In fact, it was factored, but after he died. [INAUDIBLE] factored it in 1903. No cash prize was ever offered for that number.

So cryptography proceeded with fits and starts. There was lots of work in hand cryptography. World War I introduced a qualitative change in patterns of communication.

The radio came on the scene. Marconi invented radio, showed you could transmit long distances from one place to another. That's marvelous for working with your military. You can give them their orders and so on, too, but it also tells your enemy what their orders are.

So it provided a very strong demand for the use of cryptography, the use of cryptography [INAUDIBLE] in World War I. Because of that, cryptography played an essential role in World War I. The decipherment of the Zimmerman telegram, which was intercepted by the British and published, showed that the Germans were planning to sell off parts of the US to Mexico in return for the Mexicans' help. This brought the US into World War I decisively.

Between the two World Wars, Alan Turing did a number of marvelous things. He is well known for his invention of the Turing machine and the foundations of computability, as well as the Turing test for AI and many other interesting things, some biological systems he worked with as well. But the point here is, he worked on the foundations of computability and showed, decisively, that some problems are impossible to compute on a computer. The things you can't solve with any kind of reasonable computer, any kind of imaginable computer-- the holding problem is the best-known one.

So that sort of set the stage for thinking about computers as devices that you could use and what they could do. And as time went on, we get into World War II where such devices start being built and used for the purposes of cryptography. The Germans in particular had the famous enigma machine to encipher their messages.

This is a picture of one that had some rotors that moved. It was a nice little digital device. And you pushed the buttons and get the lights showing what the encipherment is, letter by letter.

So we start getting into a computer age, almost, with the encipherment. And Turing and others who had familiarity with notions of computation-- William Friedman in the US-- broke these ciphers, as is well known now. It wasn't at the time, it wasn't for quite a while after that. It had great impact on the war.

The war was arguably shortened by several years because of these cryptographic breakthroughs. And the first computers were built about that time. The Colossus is arguably one of the world's first programmable computers.

So Claude Shannon-- one of our own, was a faculty member here for many years-- met Turing in the later stages of the war. Became familiar with some of the cryptoanalytic work. Became intrigued by cryptography as a field and wrote a very important paper on cryptography, showing that the one-time pad was, in fact, theoretically unbreakable.

That's his paper there. It wasn't published for while. He's better known, perhaps, for his work on error-correcting codes. But that was done later and published earlier. So there's some more connection with MIT-- I'll emphasize the MIT connections when I can.

The field didn't really blossom in a public way, in the public sector, until David Kahn's book, I would say. 1967, he wrote a 1,000 page book detailing the development of cryptography from the Greeks all the way up to the present time. He did not know about the World War II cryptoanalytic efforts at that time. So they were not in his book. But this book inspired lots of modern day cryptographers, including myself, to become interested in the field with [INAUDIBLE] and others.

NSA, our National Security Agency, tried to suppress publication of this book because it brought attention to the field and had a lot of interesting technical detail, too. But Kahn went ahead and published it anyway. And he's updated it since to include more recent developments. But it's a great book, and I still recommend it.

So marching on, the field of computer science evolved. We started seeing messages, bits, being passed around that ought to be protected. The US government decided there should be some sort of commercial standard. There was internal conflict about what that should be like, how strong should it be. Horst Feistel, who got a BS here at MIT-- in math, I think-- helped provide the architecture of this latter-type architecture on the right there.

NSA had their fingers in the pot, it seems, on this design, arguing that the key size should be kept short. I think they wanted 64 bits. IBM wanted 64 bits. NSA wanted 48, and they compromised at 56. That story is still not entirely told, and there's a talk coming up next week at the RSA conference where Dickie George will present a lot of interesting detail about that interaction. So, looking forward to that next week.

So computers as both a practical tool and a theoretical subject of interest really blossomed starting the '60s with the work of Hartmanis and Stearns, who laid the foundations for computational complexity. Turing showed that some problems were unsolvable on any computer, but then we get down to interesting problems which seem solvable in principle, but they just take a lot of time. So the theory of computational complexity started with them.

Manny Blum, who did his PhD here with Marvin Minsky in the math department, elaborated on that theory. And then the theory of NP-completeness was developed by Cook and Karp. Their notion of polynomial time reduction showing the one problem is easily reduced to another is a key notion there.

So talking about problems that are hard becomes something in the air-- that's important for cryptography. You need to think about making the problem hard. Not impossible, because you can't do that. But you can make it hard for the adversary to solve.

So now we get to the point where public key gets invented. So these guys, Ralph Merkle, Marty Hellman-- who had just finished an assistant professorship at MIT and was at Stanford-- and Whit Diffie-- who had done a degree here at MIT, but was out in California-- Ralph Merkle, independently from Whit and Marty, invented the idea of public key cryptography. A marvelous idea, just a, really, stroke of genius on these arts. And it's a really qualitatively different notion than classical cryptography, because it separates out the public key and the private key.

And Diffie and Hellman wrote up their take on this in the paper "New Directions on Cryptography," which was very inspirational to me and to many other people, where they laid out this vision. And I'll tell you the vision that they laid out. And they said at the beginning, they realized this is potentially very important. They said, "We are at the brink of a revolution in cryptography."

So the idea that they proposed was to do public key cryptography this way. Everybody would have a public key, and you could use that public key to encrypt a message. So if somebody wants to encrypt a message for party A, they would take the messages and somehow apply the public key to that and come up with a cypher tech, C. So the public key would do the encryption and a separate key would do the decryption. So if A receives a message encrypted with the public key, you could use the secret key to decrypt.

And it's easy to compute matching key pairs. So having these two keys be different-- and the key notion, coming back to this notion of computational difficulty, is that publishing one of them shouldn't reveal the other one. It should be computationally hard to figure out the secret key, given the public key.

So somebody could tell you the public key, and you wouldn't be able to figure out the secret key. You could encrypt mail to somebody but not decrypt. So that's public key encryption as they present it. These are deterministic operations mapping the message space to the cyberspace, one to one. It's computationally hard to invert.

Digital signatures was another idea they had which, in my mind, was even more inspirational than the notion of public key cryptography. The idea that you could somehow take a message and add something to the end of it which would authenticate the sender and authenticate the contents of the message in a way that could be verified by anybody was, I think, in some ways more revolutionary an idea than public key cryptography itself, or the related public encryption.

So the idea is, you just turn things around. You sign with a secret key and you let people verify your signature with your public key. So if message M is to be signed, party A, the signer, can apply the secret key, obtaining the signature sigma, and you can verify that signature is correct given the message, and the signature, and the public key of the alleged signer, by verifying this equation and just checking that the mappings go back and forth.

So if a message maps to the signature, then the signature should map to the message with the other key. Marvelous idea. And so we can imagine them sending email around signed and doing all these wonderful things-- having technology for doing digital signatures. These are amazing ideas.

They did not implement them at all. The had the brilliant insight, but they said, this cool stuff. We think you ought to be able to do this. They had some ideas, but they could not implement what they proposed here. And they published a paper saying this. And so this paper was our starting point, thinking about public key.

So the guy in the middle with the hair is me, and Adi Shamir is on the left, and Len Adleman is on the right. Adi and Len were assistant professors in the math department at the time. And I was in the computer science department. And we have this wonderful structure at MIT where people of different departments can work together in the same lab-- and LCS is that-- and provide that kind of synergy between people with different styles.

So we made a proposal, known as the RSA proposal, which solves the problem posed by Diffie and Hellman for implementing public key. And it relies, in part, on this difficulty of factoring. If you multiply two prime numbers together, p and q, to get a product n, you can publish that product without revealing what the primes are. So it's a foundation for building a public key cryptosystem.

That by itself is not enough. You need have some way of transforming messages-- that allows you to build a key, as it turns out-- so with RSA as we proposed it, you have a public key consisting not only of the number n, the product of two primes, but some other number e, which just needs to be relatively prime-- that is, share no divisors with phi of n. Okay? It' just a technical condition.

And the secret key is another number, d, that relates to e in a certain way. And you can compute e from d using the Euclid algorithm that I presented on the very first slide, okay? So that's the structure of the setup for the public keys. And then the RCA equations are well-known at this time, but they give us-- [INAUDIBLE], maybe not. [INAUDIBLE] There we go.

I was told to use this slide for pointing. Sorry. There we go. So we take the message m, and we raise it to the eth power, and take the remainder, mod n. That's a one to one transformation of the residue's mod n to itself, so m to the e, the message raised to the power that remainder mod n gives you the cypher text you want. And the corresponding secret key operation just is the same thing with just a different exponent. So that's our proposal for the RSA scheme. And it works. It still seems to work. We'll talk about the security of RSA. But that was the proposal. It was the first concrete proposal for a public key system as proposed by Diffie and Hellman.

So once we had the idea, we said, well how hard is factoring? Because it really relies on factoring. You need to keep the prime secret to make this secure. And factoring at the time was not that much of an academic research area. It was sort of a backwater area that hobbyists cared about.

So we talked to people who like that kind of thing. Martin Gardner wrote a column in Scientific American which some of you may have read-- wonderful recreational mathematician, inspired lots of computer scientists. You should read his columns if you haven't. He wrote a column on this.

We contacted him about the difficulty of factoring, what he knew about it. He got excited about public key and wrote a column. And he offered a copy of our technical memo that we could mail out. We even got together to put together a challenge cipher and offered $100 for anyone who could figure out a particular secret message that was encrypted with a modulus n that was the product of two primes, modules then having like 129 digits. So, a lot bigger than [? Jeven's ?] 10-digit puzzle, right?

We estimated at the time that it would take 40 quadrillion years to break. That was a bad estimate, in part due to, I think, a numerical error in the calculation, but also because there were no published analyses of factoring algorithms.

Richard [? Shappel ?] had some notes that we consulted. I think we made a mistake in interpreting some of that. But even then, it looked like it should have been secure for a long time. We'll get to that again.

Anyway we published the memo. We didn't actually distribute the copies of the memo to the thousands of people that wrote for it based on Martin Gardner's article because of the questions, whether it was legal to distribute works in cryptography. And MIT was very supportive in resolving that issue, and we eventually mailed out copies of this yellow memo on the left. And our journal article appeared not much later.

One of things that's maybe not well-appreciated either is that that paper, the RSA paper, not only proposed public key cryptography but did something else which is very enduring, which is, invented Alice and Bob. So Alice and Bob made their first appearance in this paper as protagonists, or partners, in this endeavor. I was trying to resist, when describing public key before, using party A-- I always talk about Alice and Bob when I'm doing this. And Alice and Bob, you know, they send public keys back and forth, and encrypted messages back and forth.

What's been surprising is that Alice and Bob now appear in all the crypto papers everywhere. And they've even spread out in other fields. I was very surprised the other day. I was watching television and there was a nice nature show about black holes, and there was Bob slowly watching Alice disappear into a black hole.

[AUDIENCE LAUGHS]

So they've made it around. So they even have a web-page of their own, a Wikipedia page, right? But I think there's a point there, which is, not only are they a cute expository device, but chromatography is about people who care about things.

There's people with motivations. There's a narrative, there's a scenario. They're trying to do things. And so it's not just about devices trying to communicate-- there's a satellite talking to a ground receiver, something like that-- it's about the kind of scenarios you care about, where people have goals or motivations, or trying to evil or good or whatever, cooperate or not cooperate, stuff like this. So having names for the parties is captures the spirit of what you're trying to do in cryptography well.

It was also revealed not too long ago-- well, 1999-- that the invention of public key in RSA and such things apparently also happened in British intelligence circles about the same time, or even a touch earlier by these fellows, James Ellis, Clifford Cocks, and Malcolm Williamson. So they announced that later. But it apparently didn't go anywhere. It's out in a drawer, basically, there.

And they had the idea of public key and some of the map that might go with it. But they didn't have the idea of digital signatures either. So there's some kind of interesting revelation. Maybe you'll learn more about that as time goes on.

The world of what happens in the public sector and what happens behind the walls of classification-- I don't have any security clearance. And I don't know what goes on there, but they're sort of parallel. They can watch what we do. And we don't know what they do. Interesting stories to come out.

Early steps. So another interesting thing that happened, happened here at MIT as well. So after the original invention of RSA, the management of public keys, there was this nice Bachelor's thesis by Loren Kohnfelder-- who did it here at the MIT math department under the supervision of Len Adleman-- which invented the notion of a digital certificate.

Many of you played with your certificates on your browser, the idea that you could have a signed message basically saying, so and so authenticates that this is your public key. Or the certificate from Amazon saying, this is Amazon's public key. So that notion was invented here at MIT as a Bachelor's thesis.

We saw a lot of activity in the academic sphere. And we said, this is about time to get a society together. So this is really the first steps of turning this from a hobby field and some interesting paper sort of on the fringes of computer science into a real professional area.

There was a society founded by David Chaum, myself, and others, called the ICR. It now runs all professional conferences in the area. There's hundreds of papers published every year and dozens of conferences and so on. So it's really grown up in a professional way.

In addition to getting the societies, right, there were also theoretical foundations laid at this time too. I have photos here of Professor Shafi Goldwasser and Professor Silvio Micalli, who joined our faculty about that time and laid some of the early foundations for this. And two particular works, one of which I'm involved in, one of which I'm not-- the first one I'm not was their paper on probabilistic encryption, which, first of all, gave good definitions of what it means to be secure.

Cryptographers have, for a long time, been working in an ad hoc way. And we started to see a field develop in this paper, sort of illustrative of how to start laying good foundations by getting the right definitions and showing how to achieve those definitions. In order to achieve those definitions, they argue that encryption public key encryption needs to be randomized.

The original RSA was not randomized. The notion of Diffie and Hellman was not randomized. Coming up with a scheme where the messages have to be different every time-- where the cypher tics have to be different every time you encrypt the same message was a key insight. And their paper lays the foundations there for good encryption.

The other side of public key was signatures. And I worked with Shafi and Silvio on a paper which did a similar thing for digital signatures, trying to get the definitions right. What does it mean to have a secure digital signature scheme? How can you achieve it?

It uses a particular style definition which has become popular. It was not the first place that was used. But it's, again, laying the theoretical foundations for work and security.

So in addition to having the foundations for public key stuff, as a practical matter, some other things needed to happen. Public key, as it was, was too slow. It was really painful to find big prime numbers and to take modular exponation, particularly with the machines at the time, which were 1,000 times or more slower than they are today.

So the computers were a lot slower. And even so, doing the number theory takes time. So, both for encryption and signatures, you need some way to speed this up. For encryption, having a fast stream cipher works, helps. And RC4 was a scheme that I had proposed that actually has turned out to be widely used, quite fast, and sufficiently secure for lots of applications.

And I've got some details here about how it works, which I'll skip over. But the ideas is just every few lines, do a byte of pseudo-random data. And it's used widely. It's used in PDF files, Skype, Kerberos, et cetera. So it's a very fast stream cipher, generates a pseudo-random stream that you [INAUDIBLE] with the message in the style of a one-time pad that [INAUDIBLE] analyzed.

So there's one practical foundation. On the digital signature side, again, you need some way to sign very large files. How do you sign a large file? You can't run the number theory on a big file. So you can run something called a hash function that takes a large file, compresses it down to a fingerprint. And you sign that instead.

So MD5 was one of my proposals for that. It ran fast on 32-bit machines. It was supposed to be collision resistant. That is, it shouldn't be possible to have two messages, two files, that give you the same fingerprint.

We'll talk about that in just a minute some more. But it turned out to be very widely used. I was surprised at that quick uptake of this proposal before, as it turns out, sufficient analysis was done.

This is some cryptography. MIT had a technology licensing office. A patents was filed, issued in '83. The three of us, Adi and Len and I, founded a company. The activity of that company is well-summarized by this slide for many years.

[AUDIENCE LAUGHS]

There was really no market and nothing happening for a while. Eventually we hired Jim Bidzos, who I'm convinced could sell snow to the city of Boston in the middle of winter-- a very sharp businessman and very sharp technically-- and he was able to have a first license to Lotus, Lotus Notes, and embedded some of the RSA technology and was able to grow the business after that. So he really made this fly.

The RSA conference series got started in '91, in part to bring together people who cared about public key cryptography and also to talk about cryptopolicy, which was starting to boil up at that time. Today Jim runs VeriSign, which is doing a great business on the notion of certificate, which was invented here by Loren Kohnfelder. There's 101.3 billion certificate checks per day done by VeriSign right now, and $65 billion DNS requests per day, which will soon be authenticated with public key crypto with the NSA. So this is all growing up very nicely. It'll build a secure public key infrastructure.

RSA itself, our company got sold to Security Dynamics, which is now part of EMC, a local company. But actually not only Jim made an effort. There's another fellow that had a big contribution on the practical development of cryptography, which was Sir Tim Berners-Lee. He deserves the sir very much.

The invention of the worldwide web, just like Marconi's invention of radio, made cryptography essential for that communication medium. The web itself, as a new communication medium, really drove the demand for cryptography. People are communicating all over the place on the web, doing commerce and so on, too. The demand for cryptography blossomed with the web. So without that, I think we'd still be thinking about potential applications rather than doing real applications.

Policy, as I said, started to become an issue. The birth pangs of cryptography, as it came away from being a purely intelligence agency kind of business to becoming a tool of ordinary commerce, was not easy. And there were many debates, discussions, and policy steps forward, as this happened.

There was an early attempt to chill research by a fellow who worked at NSA, he wrote a letter and said that, you may be violating the International Traffic and Arms Regulations by publishing this kind of stuff. Turns out, there's a nice exemption the ITAR for academic research and so on. But MIT put together a committee. MIT, I found, is very supportive for doing work in these kinds of areas where deep policy decisions need to be talked about.

Francis Low, [? Mike Dratuzos ?], Walter Rosenbleuth, John Deutch, and myself, and others, had a committee where we talked about these kinds of policies and decided that, really, the law was clear. We could go forward with this. And we did.

The government, meanwhile tried to continue to control things, and proposed that everybody should use crypto chips that had keys that they could read and so on-- a big brother inside kind of thing. That didn't fly very well, particularly when it was revealed that they had technical flaws in their proposal.

Today the world is much more harmonious. I think everybody realizes we live in an information-based society where information needs to be authenticated, protected. And good security, good cryptosecurity, is part of the whole cyber-security picture that we need to be working towards to make our information infrastructure work the way we want it to. That's not entirely unanimous, but I think we're pretty much there.

Attacks-- so life is never rosy in the crypto world all the time. That number that we published in Martin Gardner's column back in '77, that's it right there, that 129 digit number eventually was factored, using some new algorithms and a bunch of volunteers all over the internet, to this product of a 64-digit prime and another 65-digit prime. There's about 5,000 mips here-- a mips is a million instructions per second machine, so that's maybe not a lot by today's standards. But it was a distributed effort, very nicely done.

And they got the secret message out too. The magic words are Squeamish Ossifrage. It was the secret message that was published. We never thought anybody would see those words. We just picked them at random out of the dictionary. We thought if they got up, we'd recognize them again.

So there's the folks. There's me on the left with the four guys. They've got their Squeamish Ossifrage t-shirts on. They're holding a long printout of the number they factored.

That's [INAUDIBLE] with the students. And the check that we gave them for $100. That was the cheapest purchase of computation time in history. [INAUDIBLE]

How are we doing on factoring? RSA depends on the security of factoring. So what's happening with the art of factoring?

So this is the chart of the recent benchmarks. So the dot on the left is the factorization of RSA 129, a 129-digit number. The most recent factorization is the dot on the right, which is a factorization of what's known as RSA 768, a 768-bit number. That's 232 digits, decimal digits.

So they've been making progress. Computers have been getting better. Algorithms have gotten better. The line at the top is for a normal high-security RSA key. And it's 248 bits. That's 616 digits.

So are they going to get up to there? I don't know. There's lots of primes. So if we have to raise the barrier again, it's not hard to do. That's one of the nice things about a scheme like this.

But we're working with laws of computation here. We don't know what they are yet. Factoring could be an easy problem. It could be factoring a million-digit number turns out to be easy. Maybe someone here will discover such an algorithm-- in which case, all the factoring-based crypto goes away and we have to think of other things.

In fact, there are other proposals around that could be used as replacements for RSA and things like that, and are being used concurrently with RSA now. So this is the kind of question you yet as a cryptographer-- how good are the attackers going to get? And you don't know, because you can't prove that computation is difficult with the technology we have. It's open questions.

Is p different than np? How hard is factoring? We don't know.

Not only that, but they're changing the rules of the game a bit. Peter Shor, who's here at MIT, has proposed-- he's a faculty member of the math department, I don't know if Peter's here-- proposed a fast factorization algorithm that's based on fundamentally different computational architectures based on the use of cubits of quantum computation. This works, in principle.

If you can build a quantum computer, you should be able to factor in polynomial time, very large numbers. Building a quantum computer seems to be a challenge. I don't expect to see big ones built, actually. But that's just a guess-- or maybe I'm just biased.

So far, they've been able to factor 15 with a small one. And that's an enormous accomplishment. So they may build up to bigger numbers later on. But we'll see.

It's an interesting technical question-- can you build a large quantum computer? Once you do it, you've demonstrated that you can do it, then nobody uses RSA anymore. You've got no market for them there whatsoever, because it's not clear still what you use quantum computers for, except breaking RSA. So, dark clouds on the horizon for RSA, maybe.

So remember we had the public key leg. We also had the other legs of fast encryption with not public key style-- with RC4, digital signatures, where we needed a hash function. So Xiaoyun Wang, a professor at Tsinghua University now, and colleagues worked about 10 years to pick apart the internal details of MD5, that hash function that I proposed. They worked very, very hard at it, and finally figured out that, in fact, it was defective.

In fact, if you're clever enough-- and they were-- you could come up with ways of creating pairs of messages that had the same hash value. So a signature for one message would look like a signature for another message. It's a disaster. So they really broken open.

And they not only broke MD5, they broke lots of other hash functions that had been modeled on MD5. So it was a major breakthrough. It doesn't mean hash functions are impossible in principle. In fact, it seems quite likely that you can build good hash functions.

NIST, who has gotten a little gun-shy about some of this, has started a competition for a new hash function for a national standard. It's called the SHA-3 competition. We had submitted an entry for MIT here as part of that. We're not in the finalist running, but there's a lot of good candidates who are. And it's just an interesting competition.

So hash functions took a beating there, went in a new direction. The field has really blossomed. I mean, there's lots and lots of wonderful stuff happening in cryptography. I don't have time to tell you about everything. If I did, then we'd go into an hour lecture in each of these topics.

There's just lots and lots of interesting applications, theoretical foundations, development of definitions, oblivious transfer key linkage, proxy encryption payment systems, whatever. So there's lots of interesting stuff. A typical crypto conference will have talks on many of these topics.

So the field has blossomed. It's not just the same refinements of the same notions we started with encryption signatures. But there's lots of application-- multiparty computation, what happens when you start losing your keys, and doing other kinds of weird things like oblivious transfer. Can I give you a message, and such. I won't even define it right now. But lots of fun stuff.

So I'm going to talk about four of them-- zero-knowledge proofs, payment systems, voting systems, and homomorphic encryptions. So the first one, I didn't have anything to do with. But it's such beautiful stuff I can't help but mention it. So I'll talk about that. And then payment systems, voting systems, and homomorphic encryptions, which I had some connection with.

Zero-knowledge proofs-- so this is a notion developed by Professors Goldwasser, Micali, and Rackoff, and refined by Goldreich, Micali, and Wigderson. So I sort of wrote a haiku here to describe it. I'll try it out. So the definition is, "I can convince you that I know a solution to a hard problem"-- like factoring, I know the factor of some number, maybe-- "while telling you nothing about the solution itself." So I can tell you that I've got it, and that if I gave it to you, you would know that was it. But I'm not going to give it to you.

You're not going to see it. You're going to be frustrated. But you'll know that I've got it, and I've got it right. Beautiful notion, wonderful notion-- and even if you're very skeptical, I can convince you. We have more dialogue.

So it's a beautiful notion-- has lots and lots of applications within cryptography. Secrets are the essence of cryptography. This shows how to keep a secret while using it to convince somebody that you've got it. So having secrets lost when you're working with them is the bane of cryptographers. And this shows that you can keep a secret and still use it effectively for the purpose of convincing someone that you've got it-- wonderful work.

I didn't have anything to do with this. As I said, this is [INAUDIBLE] and others. Very useful. So that's one thing. I'm just trying to give you a flavor sampling of some of the things that cryptographers have been playing around with. So that's one.

Probabilistic micropayment-- so this is an issue that Silvio and I got involved with around 10 years ago. Paying for music over the web in small payments seemed like it ought to be going somewhere, so we said, what's the best we can do as cryptographers to come up with a payment system that works efficiently and securely? So we took the idea-- which was not new-- of probabilistic payments and made it secure.

So probabilistic payment-- if I want to pay you a dime, I'll pay you a dollar with probability 1 in 10. Expected value is the same. And if you're selling lots of things-- like you might be if you were a music merchant or something like that-- it all works out in the end.

So how do you flip coins fairly in such an application? Well we use pseudo-random digital signatures, some nice cryptography, to make that work. And there's lots more details on how that works, but it was an attempt to take this perceived need of an efficient probabilistic efficient payment system, make it efficient for very small payments where credit card companies were charging lots and lots for each payment, and make it efficient just between the two parties primarily.

So we founded a company-- and there's an MIT patent involved in all that, too. So the short story is, it didn't go very far as a business. Wonderful theory stuff, but as a business, I think we were ahead of our time. That's the official story. [INAUDIBLE]

So voting systems, another-- I've spent a lot of time these days talking about voting. And I think cryptography has a role to play in voting as well. There's a whole spectrum of new cryptographic voting systems-- Chaum, Neff, Benaloh, Ryan, myself, Adida, others, trying to take the classic problem, how do you vote securely? How do you vote verifiably and make it as real and workable as we can using the best technology that we have? So a lot of the proposals that we're looking at have the following character.

You vote, draft's on paper. You take your ballot, you post them on the web in encrypted form so that anybody can see them. You can see that your vote is posted properly in encrypted form. Because it's encrypted, you can't sell your vote-- that's always a problem with voting systems.

And the crypto works out in such a way that anybody can verify that the tally is right. You add up a bunch of cypher text and you can see that the number is right. There's some cube math for that. Not everybody likes cube math voting. There's some issues with persuading people that this stuff really does work and that, you know, you can believe the results without having to do all the math as well.

And in fact, the fact that you can do it with paper ballots that can be recounted by hand or statistically sampled and counted by hand gives comfort to people who aren't mathematically-oriented as well. So voting really has to satisfy everybody. It's a challenge.

So cryptography here though, in some sense, increases the transparency and verifiability. So it may be that large prime numbers will have a role to play in our democracy down the road a bit. This is a very promising area. We're actually seeing at least one jurisdiction, Tacoma Park, Maryland, has used one of these systems in a recent election and may use it again.

Finally, hopefully, homomorphic encryption-- one of the hot buzzwords of the field. Back in 1978, Mike Dertouzos was running a lab for computer science at the time, and Len Adleman and I came up on the question, can you compute upon encrypted data? Can you work with data that's been encrypted piece by piece and combine the pieces while leaving them encrypted so you can end up taking two cypher texts, you combine them, you end up with a new cypher text in such a way that the underlying plain text for that new cypher text is the appropriate operation on the underlying plain text?

So this is what the mathematicians would call a homomorphism. And you want a cryptosystem that's homomorphic. For a sufficiently rich set of operations, you can do arbitrary computations. And we couldn't see how to do this. We asked the question, so we get some credit for asking the question. But we couldn't solve it.

Right, so it was just solved recently by this guy, Craig Gentry. Wonderful solution based on, not number theory really, but lattices and some technology that's been evolving in that direction of hard problems. There's some hard problems involving lattices over the integers.

And it works. You can do arbitrary operations on encrypted data, keeping it encrypted. So if you're a cloud service computing service provider, maybe you can work on your clients' encrypted data, providing the encrypted results they want and not running any risk yourself of disclosing the client's data. That's the dream. It's not very efficient yet. There's lot of work to do to make it efficient.