# Commercializing Cryptography: Infrastructure, Standards, and Future-Proofing

**Podcast:** web3 with a16z crypto
**Published:** 2026-07-24

## Transcript

People started to realize that standards were essential, that cryptography was about communication.
Communication required standards.
RSA was the natural candidate for standard.
But RSA had the defect, in some eyes, that it could also be used for encryption.
The idea that was proposed was the DSA standard, which could only be used for signatures.
But to me, signatures were probably of more interest.
One of the big contributions of the Diffie-Hellman paper was the idea that you could...
sign things.
You can authenticate messages as well.
Suppose we wait a thousand years.
Are we going to have a quantum computer that can break RSA or do you think it's just not possible, period?
People think that quantum computing is going to replace your laptop and do everything faster and so on too, and it's not.
There's the question whether P equals NP.
Within a hundred years, we should know the answer to that question, I would hope.
The cryptographer's nightmare is waking up some morning and finding out that...
Hi, everyone.
and welcome to First Principles, a series by the team at A16Z Crypto.
I'm Tim Roughgarden.
I'm the head of research at A16Z Crypto.
And today we're exploring the mechanics of establishing trust between strangers on the internet.
Public key cryptography is what makes this possible, using math to let strangers communicate securely and verify messages without ever sharing a secret in advance.
Our guest today is Ron Rivest, a Turing Award-winning cryptographer and institute professor at MIT, probably best known as the R in RSA, the public key cryptosystem he co-invented that underpins secure communication across the internet.
Decades later, the core idea still forms the foundation for everything from internet security to blockchains.
Joining us is Dan Bonet.
Professor of Computer Science at Stanford, also Senior Research Advisor at A16Z Crypto, whose pioneering work on pairing-based cryptography earned him the Gödel Prize and the ACM Prize in Computing and opened up entirely new categories of cryptographic primitives.
Together, we talk with Dr.
Rivest about the invention of RSA, about the evolution of cryptography, and about how these ideas continue to shape the future, touching on everything from cryptographic hash functions to post-quantum security.
Here's our conversation.
So, Dan, it's very exciting.
We're about to talk to Ron Rivest.
And so in blockchain protocols, cryptography is used in many ways.
But in my mind, there's sort of two cryptographic primitives without which it doesn't even make sense to talk about blockchain protocols.
You just literally couldn't do them.
One of them being digital signatures, the other being cryptographic hash functions.
And Ron Rivest has been a very key figure in the development of both of those primitives.
So I was hoping you could just...
Talk a little bit about what role do those primitives play in sort of modern blockchain protocols, and then a little bit about Ron's role in their evolution.
Absolutely, yeah.
It's so cool that we get to interview Ron Rivest.
He's one of the gods of cryptography.
So yeah, so Tim, like you said, digital signatures and cryptographic hash functions, they're kind of core to blockchains.
Digital signatures, of course, are used for signing transactions.
When I want to pay you, I have to sign a transaction that's done using a digital signature.
They also play an important role in consensus.
Once enough validators sign on the block, the block is finalized.
So many consensus protocols use digital signatures.
They're also used quite heavily in decision-making, governance, in DAOs and such, right?
All those depend on digital signatures.
And guess what?
The first digital signature that was ever created is actually the RSA digital signature scheme invented by Rivest, Shamir, and Edelman, RSA.
And we're going to be speaking with Ron Rivest, who is actually the R in RSA.
Of course, there are many other signature schemes that have been invented since, most famously maybe in the blockchain space.
ECDSA is a signature scheme that's used widely that uses slightly different technology than what RSA is using.
And then Schnorr is another signature scheme that uses, that's maybe more similar to ECDSA.
And I guess we also have the BLS family of digital signatures.
So those kind of, all together, all of those play a pretty critical role in the world of blockchains.
And because he's too modest to say it, let me just say, Mike, co-host is the B in BLS interest.
Well, thank you, Tim.
But again, you have to remember the original signature scheme, digital signature scheme, is actually RSA.
Maybe it's worthwhile saying that kind of RSA, there's some moving parts to the scheme itself, but fundamentally the security is based on the fact that if I give you an integer number, factoring that integer number into its prime factors is difficult.
Again, the RSA signature scheme depends on a slightly more intricate complexity assumption.
But by and large, you can think that security is derived from the fact that factoring is difficult.
And I'm sure we'll get into that with Ron Rivest when we discuss with him.
The other important primitive in the world of blockchains, of course, is hash functions.
So hash functions are what we call collision-resistant hash functions.
So it's hard to find two different messages that happen to hash to the same output.
So, of course, they play an important role in the world of digital signatures because before we sign a message, we hash it, and then we sign the short hash that comes out of the hash function.
But hash functions also play a critical role in the world of blockchains.
For example, the...
make up Merkle trees.
So Merkle trees, it's a way to commit to a large amount of data and later prove that the cells in the data are what's committed to.
And collision-resistant hash functions play an important role in Merkle trees.
If you take this one step further, Merkle trees play an important role in what are called hash-based snarks.
And so hash functions even play an important role in the world of zero-knowledge proofs and SNARCs.
And again, Ron played a critical role in designing collision-resistant hash functions.
It's kind of interesting.
After they invented RSA, Ron and his colleagues launched this company called RSA Data Security.
And in that company, they commercialized RSA for encryption and for signatures.
So to do that, they needed a collision-resistant hash function.
And so Ron was tasked with, can you build a collision-resistant hash function?
And so he came up with a whole bunch of collision-resistant hash functions called MD2, MD4, MD5, MD6.
We can ask Ron what was MD3 because that seems to be missing from the...
I was wondering when you gave me that overview.
We skipped over MD3.
But these are all very famous hash function.
MD4, MD5 were very widely used.
MD5 is still used in some places.
Now they've been replaced by the NIST standard.
These are called the secure hash algorithms.
SHA, SHA2, SHA3.
But the original...
Collision-resistant hash functions were designed by Ron for the purpose of making RSA digital signatures work.
So it's really going to be incredible to hear Ron reflect on his experience in designing these primitives.
And on the point of cryptographic hash functions, I have to say, every time I teach them, my mind gets blown all over again, right?
It's kind of arbitrary compression in practice without any collision.
So you can take the entire Bitcoin blockchain, the entire Ethereum blockchain, the entire Solana blockchain.
hash it down to 256 bits.
The pigeonhole principle tells you there's zillions of other things that would hash down to that exact same set of 256 bits.
You will never find, nor will anyone else ever find any of them, ever, like for the life of the universe.
It's just, it's shocking to me that these things could exist.
Yeah, it's really quite amazing to a mathematician.
A collision-resistant hash function makes no sense.
Because, of course, there are lots of collisions.
You take a huge domain and you map it into a small domain by the pigeonhole principle, there will be lots of collisions.
So even though we know that there are gazillions of collisions out there, a collision-resistant hash function makes it so that you can't point to any one explicit collision.
It's really quite a difficult thing to try and design.
So when you build a hash function like SHA-256, to break it...
All you have to do is find two different messages that output the same 256-bit output.
And not only that, it's like this very short program.
It's like a couple dozen lines of code taunting you to try to find those two different pre-images.
That's right.
So it's really quite courageous to try to build such a thing.
And yeah, it's quite amazing that Ron put out the first such constructions.
All right.
Well, let's talk to him all about it.
Ron, thanks so much for joining us.
Really excited that you're here.
Really excited about the conversation we're about to have.
I thought we'd start at the, if not the beginning, close to the beginning.
I was wondering if you could just sort of paint a picture of what things were like back in the early mid-70s when, you know, after working in other parts of computer science during that time, you turned your attention to cryptography leading up, of course, to the famous invention of RSA.
What was, you know, did cryptography exist at that point?
What did it look like?
And what drew you in, given that you had a lot of other interests at that time as well?
Cryptography had been an interest of mine, I guess, for a while.
The time period we're talking about is mid-70s, late 70s, something like that.
I joined MIT in 74, and there are some works, such as Khan's classic textbook on the code breakers, which talks about the history of cryptography and the...
Many, many centuries of work had been done on that before.
But modern cryptography was new.
The computer revolution was just starting at the time.
When I got to Stanford as a graduate student, people were playing with the internet.
The ARPANET had boxes scattered around.
I programmed in paper tape and then punch cards for a while.
And then eventually I got a time-shared computer.
So it was...
Early days of the internet.
What would you say about the status of cryptography?
I guess at the time, the data encryption standard, DES, had already come out.
So there were some block ciphers.
Yeah, data encryption standard had just come out.
There was a team at Stanford looking at some of that.
I saw some of their papers evaluating DES.
Sorry, maybe just for context, I'll say that DES is a block cipher.
It's a way to encrypt messages if two sides have a shared key.
I guess the modern version of it is called AES, which people are familiar with.
But back in 1972 or so, that's kind of where DES was invented.
And would you say that was kind of the cutting edge in cryptography?
Yeah, I think so.
I think people started to realize that standards were essential, that cryptography was about communication.
Communication required standards.
And so we need to have standards for cryptography.
And the organization within the government that took the responsibility for establishing such standards was NIST.
was trying to formalize the data encryption standard.
They had two calls.
The first call didn't yield anything useful at all.
The second call, they said, come on, guys, you can do better than that.
So they got a standard involved.
So eventually, the encryption standard was adopted, but not without controversy because the key size was short.
It seemed to be a good, solid cipher otherwise.
So most of the work was classified.
This was the first...
inkling that maybe there was a commercial side of things.
IBM played a key role in developing the data encryption standard.
It was based on statistics and stuff that I don't have a security clearance.
I never did.
And there was no theory.
There was no theory of cryptography.
We didn't know what we were doing.
People were trying this and that.
I think the data encryption standard was sort of a good exemplar of that.
It was not.
provably secure in any sense of the word.
There was no definitions of what security meant.
There was no proof, of course, that went with those definitions.
But you must have felt that block ciphers were not the end of the story.
I guess everybody was focused on just symmetric encryption at that time, but you must have felt that this is missing the point, that there's more to the story than just symmetric encryption.
Well, so my own interest at the time was complexity theory and so on, too.
I was interested in Boolean circuit complexity and stuff like that.
And symmetric ciphers were indeed the story at the time for cryptography.
It wasn't until Diffie and Hellman published their paper in 1976 where they said, you know, hey guys, there's another way to think about these things.
You can have a private key and a public key and one undoes what the other does.
And their paper, New Directions in Cryptography, is a groundbreaker.
It's a fundamental contribution to the field to introduce the idea of public key cryptography.
It's astonishing to me that you could publish a paper like that because they mostly said, here's an open problem.
How do you build a public key crypto system?
So they left that as a juicy thing for somebody else to gather.
And so we got to work on it.
And that's how you got into it, basically.
You kind of got drawn into this open problem.
Well, I was working on DES at the time, but I got drawn into that problem, certainly.
Adi and Len and I were members of the Laboratory for Computer Science at the time, the precursor to CSAIL.
The Lab for Computer Science was interdepartmental.
Adi and Len were both members of the Mathematics Department.
I was a member of the CS department, but we had offices right near each other.
And so I engaged them in the search.
I said, hey guys, here's an interesting open problem.
Let's work on it together.
And so we did.
Adi was more of a...
cryptographer with me trying to design ciphers, and Len was more of the cryptanalyst trying to break them.
He was very good at breaking them.
So Adi and I had lots of stuff we crumpled up and threw in the waste bin because of Len.
The RSA scheme is the one that we didn't know how to attack, and so we ended up pushing that one.
You know, it's very rare.
Very few people get to make a discovery of the magnitude of RSA.
So maybe you could just tell us a little bit about how that process worked.
Like, how did you guys...
work on it throughout ideas and maybe even take us through the, there's got to be like an aha moment, like a day of discovery.
Maybe you can tell us about that day.
Yeah, yeah.
Well, there was in some sense.
I mean, the idea of RSA itself came to me after a context of working with Adi and Len a lot after a dinner, April 2nd, I can remember the day, you know, 1977.
And this is not long after Diffie Hellman published the paper in November of 76.
We had been working all the time on ideas for this and that.
Adi Shamir has this wonderful story where he says, you know, I was skiing with you guys at Killington.
And, you know, we were working on this problem simultaneously.
We were talking about it all the time.
And at the top of the hill, I had this idea, which would have...
given us public key and at the bottom of the hill I'd forgotten totally about it.
I didn't remember what it was.
So we don't know what that was.
There were many, many ideas floating around.
That's a very Fermat's Last Theorem type story.
Yeah, really, yeah.
So we worked hard on the problem and we thought at times that maybe it was impossible.
Niffie and Hellman had a set of conditions that they'd like to meet, that the public key and the private key were separate.
You couldn't tell one from the other.
And that one undid what the other did, but it was infeasible seeing only the public key to come up with the private key.
So that was the basic idea of public key cryptography at the time.
We said, maybe these conditions are just too stringent.
Maybe it's not possible to satisfy all of them together.
We spent a bit of time trying to prove that it was impossible and failed at that.
Came up with RSA instead.
So we had a dinner one night at Ani Bruce's house, as I said.
After the dinner, there was a bit of wine.
And so I was sitting at home afterwards looking at a copy of Dixon's book on number theory.
All of a sudden I said, maybe we should do it this way.
So that was the idea.
That was the aha moment that you're asking.
But I didn't know at the time that that would work.
The next day, I explained it to Adi and Len.
They started thinking about it.
Len couldn't break it.
Adi and I said, yeah, let's go maybe tweak it this way, tweak it that way or whatever.
But it looks good.
But it wasn't an aha for us in the sense that with any kind of research, researching cryptography in particular, you know that's not the end of the story.
Maybe you have a proof that comes later.
At the time, we didn't even have good definitions to prove things about.
You want to try to get it out there, define it carefully, but let others poke at it.
and see if see if it holds water it's always kind of funny that to me that the first example you guys came up with that lane edelman couldn't break nobody else could break either Yeah.
Which was pretty interesting.
We were lucky.
Well, Len was very good.
Yes, yes, yes.
I have to tell you, Ron, every time I've ever had an idea that I thought was a good idea at night after a glass of wine, it never survived the harsh light of the dawn.
So I'm kind of blown away by this story.
I lost those two, so I've experienced, yeah.
So one of the kind of underlying principles behind RSA, I guess, is the fact that you can easily multiply two numbers, or two prime numbers, but it's difficult to factor them.
So I guess this is something that you were already thinking of exploiting for this kind of system?
Yes, yes.
We looked at lots of different schemes, and multiplication and the difficulty of factoring was one of those.
As it stands, computational complexity was new.
We didn't know how hard various problems were.
The field was still evolving.
We're really on quicksand.
We're really on soft ground.
We didn't know.
What we were talking about mostly.
Factoring was a problem like that.
Nowadays, lots of people have looked at factoring and said, oh, that's hard.
But at the time, it was very sparsely studied.
There were a few decent algorithms.
A lot of them had been analyzed carefully, except trial division.
So the aha moment that we talked about was an aha that was very cautious because we didn't know how hard factoring was.
And if you could factor numbers quickly, you could break the system.
And so that was the story there.
So, Ron, one thing I'm really curious about is sort of the closely intertwined stories of public encryption and also digital signatures.
I was curious, both sort of leading into the work and then also sort of afterwards, were you motivated more by one of those problems than the other?
And at the time that it came out, did one of those solutions resonate more with the community than the other one?
Great question.
The Diffie-Hellman paper, which was our starting point, as I said, was such that they talked both about digital signatures and encryption symmetrically.
I mean, they encrypt with the public key and then decrypt with the private key, or vice versa if you want to turn it around for signatures.
So they were entirely symmetric.
There was no randomization.
So randomization comes later in the story.
These are deterministic algorithms.
So to me, signatures were probably of more interest.
because they were new.
And I thought that was one of the big contributions of the Diffie-Hellman paper was the idea that you can sign things, you can authenticate messages as well nicely this way.
Whereas encryption is maybe of more interest to the military community, the intelligence community, their interest in stealing information and listening in on conversations.
But they were somewhat the same in terms of mathematically, in terms of what you did.
I guess it was first published in Scientific American, right?
I mean, Martin Gardner wrote this column.
And there he seemed to focus mostly on encryption, right?
Not so much on signatures?
I don't remember what he focused on there.
But I went down and met him in New York.
He was a great guy.
But the reason for my going was in part maybe to prep for this column, but also to find out what he knew about factoring.
Because factoring was a...
black art at the time.
And he's exactly the kind of person that you want to ask about.
How hard is factoring?
What do you know about factoring?
And so he wasn't able to make a dent either.
And he said, let me write a column about this.
Maybe my readers will do something.
So we helped him write the column.
We put a challenge in there and made up a challenge cipher.
I think we offered $100 for anybody who could break the...
And we put a book, a bad...
estimate of the time it would take to factor the number.
We said it would take 140 quadrillion years to factor this 129-digit number.
And that was way off because it was factored in 94 by a bunch of guys, Leinster and so on.
And these days you can probably do it on your iWatch.
I haven't tried that yet, but I've got an iWatch.
Yeah.
But actually, I want to go back to Tim's question.
In terms of your sense of the interest in the community between signatures and encryption, do you have a sense of what were people more excited about?
Well, we're getting to the stage where NIST is starting to develop standards and the NSA representing the intelligence agencies, also the FBI, but mostly the NSA at that time.
was concerned about their ability to eavesdrop on conversations with foreign adversaries and so on, too.
So they were concerned that academic research in cryptography would hurt their business if encryption became super strong.
So we got some pushback from them about the encryption side of things.
And that's a continuing story, and I can recommend Stephen Levy's book, Crypto.
to talk about that story.
Yeah, I guess doing cryptography back then is very different from doing cryptography now, right?
Now it's a scientific field, it's open, the whole world of cryptographers kind of collaborate with one another.
Well, I think you've got the blinders on a bit, Dan.
I think that there's still portions within this intelligence community that would like to see academic research and cryptography squelched.
And I see some of that, I guess.
Mostly that's within the FBI and the intelligence agencies sort of assume that what's good for the country is good for the world.
Yeah, that's fair.
But it was much more so back then, right?
When you guys got started, it was much harder to publish papers and cryptography.
That's right.
That's right.
And Len Edelman had an offer from the NSA to give him money for a research grant under the condition that he subject all of his papers to their review and stuff like that.
So he declined that.
You're right, though.
I mean, it was very different.
So there were many consequences of that.
I mean, one of which was the founding of the RSA Conference Series in 91.
That was set up in part to give people a forum to talk about the tension between academic freedom and the right to publish and the need for cryptography commercially versus the intelligence needs of the country.
So I'm also curious, so we've talked about sort of interest from the intelligence community and so on.
What about actually within just, say, the ivory tower, like computer science academia?
Was it kind of too new?
Did it take some number of years before cryptography was sort of really respected?
I think that's right.
I think that's fair.
There was no immediate groundswell of enthusiasm for this.
It was, you know, another application of complexity theory, perhaps, or something like that.
We're still feeling our way.
People weren't encrypting messages routinely.
There was no internet.
The examples in the Effie Hellman paper were things like talking to your stockbroker and stuff like that, which were really hypothetical.
Yeah, it's a little hard to imagine, hard to believe life like that without the internet, without computers, without the phones, without everything being encrypted.
It's really a different world.
But I'm also curious, like Tim was saying, so the result came out, RSA was published.
And then the most...
I mean, there was quite a lot of interest in understanding the security of the scheme.
Were there kind of interesting attempts to break the scheme?
Were there interesting attempts at trying to prove that the scheme is secure?
Yeah, sure.
So RSA was a stake in the ground and said, you know, this scheme might be usable, but it's got to be shown to be secure.
And we didn't know what secure meant at the time, even.
I think the Goldwasser-McCaulay work around the early 80s.
really started off the ball with formal definitions and inclusion of randomness in the encryption operation.
Those were two key contributions they made.
So I think people tried to tune up their analysis of factoring algorithms.
Even the existing factoring algorithms were not well analyzed.
There was improvements over time to factoring algorithms.
We got better and better at factoring numbers.
The nice thing about RSA is the key size is totally variable.
We proposed at first a short key, and then it got longer, and it's getting quite long now, 2048 bits or something like that.
Just a recommended length for an RSA modulus.
Computers can handle that easily these days.
But RSA is expandable, and so even the factoring got a bit better was the kind of thing you could manage and deal with.
I still get people writing me every week saying, Professor of S, I've got a new factoring algorithm.
Oh, yeah.
Please consider that.
What about this?
Can you factor 77?
I mean, this was sort of the greatest gift ever to the endeavor of coming up with better algorithms for factoring and number theory more generally.
I wonder when you first heard this, Ron, but many times I've heard people say, you know, this ironic quote of George Hardy, right, the famous, the pure mathematician about his love of number theory.
by virtue of it having no applications.
No applications, yeah, yeah.
And then you kind of completely blew up that vision.
Yeah, definitely.
Yeah, yeah.
Most of mathematics turns out to be useful somewhere.
And cryptography is a great consumer of mathematics.
Yeah, to me, it's actually amazing that the things that people pursue for intellectual curiosity, mostly, you know, Gauss and Euler and all these guys, and Hardy developed all this mathematics because they were curious.
And it always, always, always turns out to be practical in one way or another.
It's really kind of amazing that things that you think have no application eventually turn out to have an application.
And we just see this over and over again.
So actually, speaking of the security, I know that people were still kind of interested in how to set the security, the size of the modulus, as you said, like how secure the scheme really is.
So you guys came up with this really interesting idea to set up a challenge to break up RSA, to break RSA.
There was not only the publication in the Gardner column about a particular challenge, but there was this ladder that we constructed.
And it was precisely that.
Each number had a series of numbers.
Each one was a product of two primes.
And it went from...
four digits, I forget what the shortest one was, four digits, maybe up to thousands of bits long, so 2048 bits or something like that.
And the goal was to give people a challenge to find it, because in practice, security is a practical matter.
You can do all the theoretical analysis you want, but if you can't build a quantum computer or can't implement your factoring algorithm, you know, whatever.
It's hard to tell.
So the RSA challenge is basically a sequence of numbers that you need to factor.
I think the largest one is like 2048 bits.
Yeah, yeah.
I think the largest one that's been factored is like 768 bits or maybe slightly bigger.
That's around there.
Do you know the factorization of these numbers?
I don't know the factorization numbers.
It keeps my laptop from being hacked.
I think that factoring is a nice problem in the sense that if you're given a solution, if you say these are the factors of that number, you can just multiply them together and see if you get the target number.
So at this point, you're saying nobody knows the solution to the RSA-challenged problems?
Well, the short ones, they do.
But the longer ones, they don't.
The longer ones, yeah.
So if anybody comes up with a factorization, then they did something that we think is difficult.
Yeah?
Well, I did give a talk.
My wife does substitute teaching at a fourth-grade class nearby.
One of the girls in the fourth grade class afterwards, she said, Professor Avest, I discovered the factorization of this number.
I said, my God, what's going on here?
In fourth grade, you must be a genius.
She said, oh, it's blah, blah, blah, blah, blah, blah, blah, blah, and a half times two.
Ooh.
Amazing, yeah.
It's true.
Sorry, I said, that's good, but that's not what I meant.
Yes, right.
Factorization into integers.
Into integers, yeah.
Into integers, yes.
But again, our audience should know this.
There are these numbers out there.
Like I said, the largest one is called RSA 2048.
Ron is on the record.
Nobody knows the factorization of these numbers.
Nobody knows the factorization, yeah.
So you have a challenge.
If you can factor any of these numbers, I don't know that the prize is still available.
The prize is not available, but people still use the numbers.
There are headlines every time a new one of these gets solved, for sure.
You'll make the news.
If you factor any of these numbers, you'll make the news.
It's a very kind of nerdy slice of the news, but the news nonetheless.
I'll hear about it for sure.
Ron, you mentioned...
earlier sort of the importance of standards in cryptography.
And so I was wondering if we could spend a little bit of time circling back to signatures.
And in the 1980s, when the NIST made an effort to standardize a signature scheme, right?
DSA and Dan, I'd love for you to fill in more context too as well.
But there are a number of contenders here and there was a winner.
And just we'd love to hear any stories you have to share about sort of how that process.
Yeah, that process is part of the bigger picture of NIST working as a handmaiden to NSA, trying to suppress encryption and adopt signature-only standards.
RSA was the natural candidate for a standard, but RSA had the defect, in some eyes, that it could also be used for encryption.
The idea that was proposed was a DSA standard, which could only be used for signatures.
So DSA stands for digital signature algorithm.
And the goal was to standardize an algorithm that everybody in the U.S.
would use and say the government would accept signatures that were issued by DSA.
Yes, yes.
And so that was complicated, not only for the politics involved and the pushing and shoving that went on about encryption, but also because of the need to deal with patent coverage.
The RSA algorithm itself was patented in...
I think when we first invented it, so MIT decided to put a patent on some of those things.
There was a corresponding Stanford patent for Diffie and Hellman.
There was a back and forth about that.
So that got delayed by six years, which was a great six years to have a patent coverage of 2003 or whatever.
So there's a whole lot of issues having to come into play for the adoption of a standard there.
So DSA...
became later on ECDSA, which is very widely used these days.
But it's not just about the signature algorithm itself.
It's also about the hash function that goes into the signature algorithm.
So signatures, often they'd rely on collision-resistant hashing.
And that also had to be standardized.
Yeah?
And so maybe just to set the context, I know you designed a whole bunch of collision-resistant hash functions, MD2, MD4, MD5, MD6, the whole family.
I'm not sure what happened to MD3.
MD3 was canned because it wasn't secure.
Okay, I see.
There wasn't MD3.
I won't even talk about it now.
Yeah, and then NIST had their own standards, the SHA, the secure hash algorithm, SHA-1.
Those came later, but the design of MD2, MD4, and so on too, was because, exactly as you say, there was a need for hash functions to go with digital signature standards.
And, you know, we needed good hash functions.
And so that was my attempt to try to come up with a decent hash function.
We published it, tried to let other people evaluate it.
MD2 turned into MD4 because it wasn't long enough rounds and so on too.
MD5 was a later addition.
MD6 was even later.
So these things evolved over time as people started poking at it.
But the need was entirely practical.
It wasn't theoretical.
There were no definitions.
There were no security proofs or any sort.
It was just basically, can you invert this hash function?
So, Ron, given a just sort of blank page, how do you even start thinking about that problem?
Because the point of a cryptographic hash function is to sort of be inscrutable, to have no structure, yet be an efficiently computable program.
How do you even start thinking about that?
That's a great question.
I don't know.
To start taking a piece of paper and writing a code, I don't know.
I mean, it's two things.
Got to start somewhere.
The question is, what should the state be, as usual?
You're describing it more as kind of a bit of an ad hoc process?
Very, very, very, very ad hoc.
It was not theoretically motivated at all.
If it had been, it would have been some factoring-based thing or whatever.
It would have been terribly slow.
This is intended to be a fast algorithm.
Yeah, I guess that's one of the things that's changed quite a lot.
I guess there's a little bit more guidance from the theory.
today, which actually is kind of an interesting question.
Did any of your work on public key cryptography inform your constructions for these hash functions?
Or are these completely unrelated?
These are unrelated.
One was a motivation for the other.
The public key work was a motivation for the hash function design.
But the hash functions by themselves were independent, could have been done, I suppose, independently without this context.
Yeah, I see.
And then eventually, NIST decided on its own hash functions to standardize.
Which I think was a good choice.
I mean, they had a community involved.
And there's a lot of similarities between SHA-2 and SHA-256 or whatever, and MD2, MD4, whatever.
So they took the best of what they could find and made it a hash function.
So SHA-256, I'm perfectly happy with.
That's actually good to hear, because that's actually used quite a bit these days.
That's important to say.
So actually, I want to change gears just a little bit and talk a little bit more about a theoretical concept.
So if we go back to look at the Schnorr signature scheme, if you look at how it was constructed, it was derived from an interactive protocol.
And then you derive the signature scheme by applying this transformation.
It's a very famous transformation these days.
It's called the Fiat-Chamere transformation that takes an interactive protocol and turns it into a non-interactive protocol.
And in that process, we end up with a signature scheme.
So that's kind of how Schnorr signatures were derived.
So I think that this dates back to the late 1980s or so.
This is kind of where the idea of random oracles come from and so on.
So today, the Fiat-Miri transformation is very, very important in applied cryptography.
It's used a lot to build practical protocols.
Random Oracle analysis is actually used quite a lot in analyzing real-world systems and so on.
So maybe you can just take us back to those times and when random oracles came out, when this idea of Fiat-Germier came out, what do you think of it?
What did the world think of it?
At the time, I thought they were great.
The theory community was starving for tools and looking for ways to prove things that they couldn't prove.
And so you make assumptions, and the assumptions that random oracles exist.
is a reasonable assumption.
You know, there's no reason that one shouldn't think of SHA-256 as a random oracle, at the time anyway.
So you're saying at the time it seemed reasonable to model things as a random oracle and then instantiate them with SHA-256?
Yes.
And assume the resulting scheme is secure.
Yeah, that seemed very reasonable.
It still does.
I mean, people are getting better at analyzing random oracle protocols and finding places where they don't work.
But, you know, by and large, I think the random oracle methodology is a great one to use and nice to rely on as a theoretician.
Yeah, that's actually okay.
It's good to hear given how much of the deployed systems in the world actually depend on that methodology.
It's also a reasonable assumption, though, in my opinion.
I mean, it's not just a crutch.
People take a hash function and instantiate a random oracle with that and modulo.
saying that in the paper somewhere, they can count on it being secure.
And in practice, it will be.
Yeah, it's interesting to hear you say this, because there was a period in time when this was a very controversial issue.
Like, cryptographers could spend entire dinners arguing about whether this makes sense.
What does it even mean to instantiate a random oracle?
I think that debate has kind of settled mostly by now.
It would be nice if we knew the truths of complexity theory.
You know, how to prove that P equals different than NP and things like that.
But we don't.
We still don't.
After decades, we still don't.
And so we do the best we can.
And the random oracle hypothesis is one of those assumptions we make, yeah.
Jumping off on that, I wonder if you could talk maybe more broadly about the interaction between the more theoretical and the more applied sides of cryptography.
Because, you know, you meet many, many different kinds of computer scientists, right?
Some, you know.
It has to just be based on the existence of one-way functions and anything else is cheating.
And then there's others that are like, you know, does it work or does it not work?
You know, implement it and let's, you know.
Yeah, yeah.
I think the theoreticians learn from the practice.
It's a great question.
Theory and practice at MIT are both emphasized.
And cryptography is one of the places where theoreticians learn from the practical cryptographers a lot.
You'd learn things like timing attacks, which are part of what you see in practice, but you don't see that in theory.
The theoreticians.
tend just to shoo that under the rug and don't model it at all.
But they should.
They should say timing attacks are important in practice.
And other aspects of practice, being able to get in the middle of a conversation and so on, the understanding of which protocols are used in practice matters.
So I think that practice informs theory, and theory also informs practice.
I mean, you have systems which are provably secure in theory, and they get used.
in practice now.
Machines are fast enough.
You can find prime numbers.
You can do other things with them.
You can do exponentiation.
I had my five-year-old grandson ask me, which is your favorite operation?
He's just learning mathematics.
He loves mathematics, by the way.
So he asked, addition, subtraction, multiplication, or division.
I said, exponentiation.
Think of cryptography.
We can do that.
We can do exponentiation quickly.
Modular exponential.
You heard it here first, Dan.
There's someone to look out for when PhD admissions come around in about 17 years.
There you go.
Exactly.
He's good at math, so send him our way.
Yeah, okay.
17 years.
Yeah.
Actually, cryptography is one of the amazing areas where there's a very strong interplay between theory and practice.
So I was really happy to hear what you just said.
But actually, it's also an interesting area where there's also interaction between kind of the corporate side, more of the business side of the world and the academic side of the world.
So you kind of lived in both, right?
You set up a company.
It's called RSA Data Security.
Yeah, we set up a company in 82, 83, something like that, early 80s.
We recall that the web did not exist at the time.
So Tim Berners-Lee invented the World Wide Web in early 90s something.
And so RSA as a company did not take off until the web happened really.
So it was too early, basically.
It was created too early.
It was too early, yeah.
The company was living on fumes for a while.
Jim Bizos joined in 86 and kept the company going with some – contracts that he had arranged to get signed by Microsoft and others, IBM.
But it was very sparse goings.
We had offices in Redwood City, and people would come by and say, oh, this is your satellite office.
And it turns out that was the main office.
But then the web came along, and everything took off, right?
Everything took off, yeah.
Then payment systems happened.
People started paying, doing transactions online.
stuff like that, all the visions that Diffie and Elman had were realized through the web.
And I'm curious, was that sort of a no-brainer decision in your mind to form that company?
I mean, you were still a relatively junior professor at MIT.
I mean, maybe it's post-tenure.
The folks at MIT said, well, there's a commercial application.
We said, okay, we'll try.
I don't know if it was a no-brainer.
We certainly didn't know.
It wasn't like doing an AI company these days where people throw money at you.
So MIT encouraged you to do it?
MIT encouraged us to do it, and it was an interesting venture.
So would you like to see, you know, of the current generation of computer scientists in academia, would you like to see more of them try to commercialize their ideas?
Or do you think the current system is sort of a perfect balance?
Or what are your thoughts there?
It's hard to tell.
I mean, MIT has some tradition of entrepreneurship.
Maybe a third of the faculty are involved in startups of various sorts.
Stanford is, you know, heavily entrepreneurial.
And I don't know what the numbers are like where you are, Tim, but...
Less than Stanford or MIT at Columbia.
Some, some.
Though it's, you know, for the Ivy League, it's very good, I'd say, actually.
Yeah, yeah.
I think people need to understand, you know, what the possibilities are.
And, you know, perhaps, you know, if they lean in a practical direction to set up a startup.
Maybe another way to ask this question is, do you think setting up the company made you a better professor?
That is, did you take things back from the company back into your research world?
Yes and no.
I think it made me a better professor in the sense that one of the things I had to learn to do was to separate the commercial side of me from the academic side of me.
So the academic side of me changed fields.
I got tenure, in part because of the RSA and things like that.
But I got tenure and I switched fields.
to machine learning.
So it's time to do something that's a bit more risky.
So I graduated my first PhDs in machine learning from Shapiri.
I got a doctoral dissertation award, things like that, if things were happening.
So the commercial side of me was pushing the academic side of me to change fields.
And I did that.
So I guess without the commercial side, who knows what would have happened on the academic side.
Eventually, I switched back into doing more cryptography and the academic side of me, particularly with the voting work.
Voting work has a lot of cryptography in it.
And for the younger listeners, this era, doing machine learning was a highly contrarian thing to do.
This was not.
So, you know, back in the 1980s was one of the more winter types eras in AI and machine learning.
It was the practice that made it happen.
Ron, I think we have like multiple examples where you are like ahead of the, way ahead of the curve.
So you have to tell us what you're interested in now so we'll know where the world will be in 10 years.
I guess the thing I'm thinking about now mostly is AI and AI safety.
Nobody knows how these large AI systems work.
And people talk about safety and having no idea what it means.
So I'm thinking about some of those issues.
But I also spend time on climate change.
Both of my sons are involved in climate change.
That's a problem we all have to face.
So we briefly alluded to...
the potential of quantum computers and post-quantum cryptography earlier.
And it's sort of the elephant in the room, right?
The impact that practical quantum computing would have on public-key cryptography.
So what are your thoughts?
How much should we be worried about quantum computers?
And I guess the much broader version of that question is, where do you think cryptography is going to be 20 years from now, 30 years from now, 50 years from now?
Yeah, great questions.
Quantum computing.
is a hot area for research.
Dan knows this, and you know this, Jim.
It's just lots of work happening, but I tend to be very biased about this, and I wish the engineers the worst of luck in actually building these things.
People think that quantum computing is going to replace your laptop and do everything faster and so on, too, and it's not.
We don't know good algorithms for much except breaking RSA.
It's like the universe is messing with us.
Instead of making quantum computers cure cancer, it makes quantum computers break cryptography.
Yeah, yeah.
So there's that.
We don't know.
That may change.
I think cryptography will be resilient and do that.
I love the work that's being done by NIST to be ready for quantum computers should they happen.
But as I said, I wish them the worst of luck.
Maybe the intelligence agencies will buy some, but maybe they won't even.
I don't know.
People are slowly switching to quantum-resistant cryptography.
Do you have an opinion on whether this is like, even in the limits, is this possible?
Like, suppose we wait a thousand years.
Are we going to have a quantum computer that can break RSA?
Or do you think it's just not possible, period?
Well, there's this question whether P equals NP and stuff like that, too, which will be resolved within a thousand years.
So we'll know.
One hopes.
One hopes, yes.
I hope so, yeah.
Me too, yeah.
Within 100 years, we should know the answer to that question, I would hope.
I think the cryptographer's nightmare is waking up some morning and finding out that P equals NP.
All of your cryptography, all of your algorithms run faster, but the cryptography is down the toilet.
People can find out what the secret key is.
They can split.
But that question is likely to be resolved in proving that P is not equal to NP, right?
So I'm not so worried that cryptography is going to break because P is equal to NP.
Who knows?
I think you've got to be ready for it.
I'm a worst case kind of guy.
You have to be ready for the worst case scenarios.
So what do you do if P equals NP?
How do we change over?
Because as cryptographers, we've got some responsibility to the world to try to shine a flashlight in the path that's forward and say, what do we do here?
Maybe it's worthwhile saying for the audience that if it does turn out that P is equal to NP and the algorithms are fairly practical, then cryptography is impossible.
Or at least public key cryptography is impossible.
Any kind of cryptography, except the one-time pad.
Except for information theoretic methods, like the one-time pad.
Yeah, yeah, yeah.
But somehow, I don't think we're going to be losing too much sleep over P equals NP, given that there's kind of a fairly wide consensus that they're probably not equal to one another.
And that's how things would likely be resolved.
Whereas with quantum- And also the if.
They have to not only be equal, but equal with a practical algorithm.
Especially that version of it.
I don't.
I think there are people who believe that just because of a mathematical curiosity, maybe mathematically those classes are equal, basically because P is too generous a notion of efficient computation.
I don't know.
I knew very few people who are betting on actually practically efficient algorithms for MP hard problems, for example.
It could happen overnight.
Some Spark graduates.
It could.
Until it's proved the other way, we don't know.
We don't know.
And the consensus has been wrong before.
I mean, people used to believe in the ether.
That's true.
It's a good reminder.
But somehow the quantum threat seems a little bit more realistic to worry about in that if you believe in the postulates of quantum mechanics, then Shor's algorithm should, in principle, work.
And it's just an engineering problem.
It quotes, yeah.
Big quotes.
Big quotes.
Yeah, yeah, yeah.
Just an engineering problem.
The question is whether they'll ever build a machine, a quantum machine, that's big enough to factor RSA 2048.
Yeah.
Or maybe we'll learn new science.
Maybe it turns out the world is more complicated than just quantum mechanics, and there's some quadratic terms in Schrodinger's equation that prevents it from working.
But it's very interesting to hear.
Your hope is that that endeavor will fail.
It's very interesting to hear that.
Well, it won't help with respect to the standards, because I think the standards have moved on to quantum-resistant stuff anyway, which is a wise move.
But I must confess to having extreme bias in this regard.
These guys are fooling themselves.
I think they could build these things.
But maybe I'm wrong.
But at the same time, the world needs to be prepared in the sense that if it's not true and the machine is built in the next 10, 20 years, then we have to be prepared.
We can't bet the whole safety of the world on our wishes.
It's a good research problem for somebody.
So if you've got a graduate student who's looking for a research topic, Dan.
Fair enough, for sure.
Well, Dan is famous for proposing to his PhD students problems where if they solve it, they are guaranteed a PhD.
I think this one would qualify.
This one would qualify, yeah.
This one meets the bar.
Work well in the past, yes.
All right.
So, Ron, again, a fantastic conversation.
Good to talk with you, folks.
Thanks so much for taking the time to speak to us.
This has been fantastic.
Yeah, yeah, yeah.
Good, good, good.
This has been fantastic, Ron.
Thank you so much.
Wow.
Well, so that was amazing, getting to spend an hour or so with Ron Rivest, legendary cryptographer.
All the stories, all the stuff he's done over the past, you know, half century plus, just amazing to hear about.
So before the interview, we really focused on applications in cryptography, specifically in blockchain technology.
You know, I think it was obvious when, you know, Ron was talking about cryptographic hash functions, signatures, encryption.
They're more general cryptographic primitives.
And he, for example, talked about how, you know, when the web became a thing in the 90s, you know, how signatures had this and encryption was all of a sudden, you know, used in e-commerce.
But they're really much more general technology, right?
These cryptographic primitives.
So could you speak a bit about kind of other applications, less obvious applications where they're playing an important role?
Yeah, I guess we always think about all the applications of cryptography to blockchains, which of course there are plenty.
But cryptography, like you say, is used in lots of other parts of humanity, of human life.
Like, for example, securing the internet is kind of an important application for cryptography.
So they're all internet connections.
Even though the internet is a public network, we can converse privately over the internet, for example, for the purpose of e-commerce.
for the purpose of banking, business-to-business applications, can talk privately over this public network.
And that's all thanks to the cryptography that Ron and many others have built.
But there's other areas where cryptography comes up.
For example, it comes up a lot in digital elections.
So how do we keep our elections safe, secure, sound, and robust?
That is all also based on various aspects of cryptography.
And in fact, Ron worked quite a lot on the security of election systems.
That is a pretty big passion of his.
So yeah, cryptography comes up all over the place.
It's really quite an amazing tool, and it's an amazing science.
Again, it's one of these areas that brings very powerful mathematical tools and very heavy tools from the theory of computer science into practice in areas that touch basically all of our lives day in and day out.
It's an amazing area.
Yeah.
Anytime you're using your smartphone, there's cryptography happening in the background, for example.
Yeah.
Any surprises for you, Dan, in the interview?
Oh, man, yeah.
It was really fun to talk to Ron about his views on quantum computing.
Yeah.
Rooting for it to fail.
Rooting for it to fail, yeah.
I mean, as Ron said, a lot of smart people are working hard on other applications of quantum computing, you know, should it be built.
But as you say, the first killer application, no doubt, breaking public key cryptography.
That's right.
So it was really interesting to hear him say that he's rooting for it to fail.
Same time, hard to blame him.
I sort of, you know, I try to put myself in his shoes.
I can see it, you know.
And I thought his point on, oh, you know, we should be worried about quantum computing, but we should also be worried about what happens if P is equal to NP.
That is a...
Pretty unusual statement to make.
So that was really interesting.
To the point that it makes me wonder if, you know, so Shor's algorithm was 94, I believe, right, which is 17 years after RSA.
So I wonder if in that interim, he was worried about P versus NP already as a possible sort of threat to the RSA cryptosystem, right?
And then Shor's algorithm would just be, you know, yet another kind of, you know, threat to its enduring sort of viability.
But I think you brought it up.
Even if P is equal to NP...
But it turns out that the best factoring algorithm that comes out of P equals NP runs in time into the 500.
Then it's irrelevant.
You can't run the algorithm.
It's polynomial time, but you can't run it.
So it's kind of not really practically relevant.
I do know some of the top computer scientists in the world who are worried about P equals NP for kind of weird mathematical reasons.
It is very rare that I made a...
you know, kind of top computer scientists worried about genuinely practical algorithms for MBHR problems.
And then, you know, of course, the flip side is there's a big optimistic story.
If you're not a cryptographer...
Right.
There's a lot of sort of very positive benefits of having, you know, fast algorithms for all problems in NP.
Somehow the P equals NP question, to me, if P does turn out to be equal to NP, it says something very strange about the amount of order in our universe.
Somehow you can fish out things from a huge fishbowl without looking at lots of fishes.
It says something about tremendous amount of order in the world, which seems a little counterintuitive.
Could be, but...
Perhaps.
The concern, I think, would just be it's such a generous notion of efficient computation.
And perhaps we didn't perfectly mathematically formalize what we meant by efficient computation.
That's the one little loophole that I myself do worry about some time to time.
I would still bet on p-nulled equal to NP.
I would bet on p-nulled equal to NP.
To be clear.
Yeah, yeah.
If it's going to be resolved, it's most likely going to be resolved that p is not equal to NP.
Yeah, yeah.
But by the way, I should say that if disaster strikes and it does turn out that...
I don't know, SAT has a quadratic time algorithm, then we're in trouble.
Then all of a sudden, cryptography, like complexity-based cryptography, is just not possible.
And then it's not really clear what we do.
The only things we can fall back to would be information theoretic methods.
like one-time pad.
And just to clarify that point, so it's not just that the existing systems fail, right?
So what you're saying is fundamentally it cannot exist should P equal NP with a fast algorithm.
Fundamentally, like we do not have good pseudorandom generators.
We cannot have even symmetric encryption that is secure other than things that are information theoretics like the one-time pad.
But there's another alternative, which is, it's kind of interesting that the world of quantum mechanics actually could potentially save us in that scenario too, in that we could actually build key exchange mechanisms based on the laws of quantum mechanics that don't rely on any complexity assumptions.
So we could still build using fiber optic channels.
You and I, Tim, can still exchange a secret key that an eavesdropper can't learn.
And then using that secret key, we can use it to then do a one-time pad to encrypt our conversation.
So in some sense, quantum mechanics could save us in the worst case that in fact SAT has a quadratic time algorithm.
I see.
So quantum giveth and quantum taketh away, I guess.
That's right.
That's right.
Yeah.
Yeah.
So it's a pretty interesting story.
And I guess cryptography will live on, just maybe in a very different shape and form.
It is definitely not a boring area that you work in, Dan, I have to say.
Never a dull day.
Never a dull day.
Well, thanks so much for co-hosting the show.
This was super fun as always.
Yeah.
And I propose we sign off there.
Yeah, this was awesome, Tim.
Thanks for setting this up.