Ralph Merkle on Cryptocurrency & Post-Quantum Cryptography

May 2020


By Tim Ventura:

Cryptocurrency is poised to become the future of money, but that ambition is threatened by advances in quantum codebreaking. We’re joined by public key cryptography pioneer Dr. Ralph Merkle to learn how next-generation quantum-resistant cryptographic standards help blockchain encryption stay secure…

Ralph, let’s start with your background: as one of the inventors of public key cryptography and cryptographic hashing, your work is fundamental to the safety & security of the modern internet. Given the global scope & utility of this accomplishment, how does it feel to have created something so important to data authentication & encryption?

Well, obviously it feels great to have a work that’s already being used widely and will be used more extensively as time goes by. As we continue to move into the digital era, things are just going to keep getting better and better for cryptography — both for authentication as well as for privacy.

Now in terms of authentication, there’s just a basic need for it. If I get bits, I would like to know that those bits have not been tampered with, so I’d like them to be authenticated and digitally signed by the appropriate authority. The information in those bits may be completely public, but authentication is still used to make sure that it hasn’t been tampered with.

Encryption is another story: oftentimes if I’m talking with friends about things that I’d rather not be made public, and encryption is good for safeguarding that as well. A number of recent political news headlines come to mind that are reminders of what happens when private information falls into the wrong hands, so it’s comforting to have these types of communications protected by the appropriate encryption technology.

So whether you’re talking authentication or or encryption, its good to see the these tools being widely used. In general, I think that at the very least authentication is appropriate pretty much for all bits. I don’t see a real argument for saying, “unauthenticated bits are useful”, just like I don’t see an argument for picking food up off the ground.

So authentication is universal — but encryption? Well, it depends on the bits. Depending on what kind of information you’re transmitting, some bits may very well deserve heavy-duty encryption, whereas others that contain public information may only need to be authenticated.

Another innovation of yours is the Merkle tree, which is a fundamental part of blockchain technology and has really enabled cryptocurrency. What inspired you initially to develop this and what are your thoughts on how it’s being used in blockchain now?

Well, the inspiration was simple. Some of your readers might remember the trapdoor knapsack that used to be a system that people thought might actually be a reasonable public key cryptosystem.

Back in the day I was having a hard time getting digital signatures from the trapdoor knapsack. So I thought to myself, “geez, if I’m having a hard time with that, maybe I should cook up a digital signature based purely on hash functions”. So in the process of developing that purely hash-based digital signature, I developed Merkle trees as part of that digital signature.

Actually, it turned out that digital signature system has proven quite robust because it relies only on hash functions. In fact, evolved versions of that digital signature are making their way into various standards because it turns out that they are resistant to attack by quantum computers, which is a very useful property.

Merkle Trees are widely used in computing, and part of Bitcoin since it was designed in 2008 (Bitcoinwiki)

What are your thoughts on the future of cryptocurrency? Advocates continue to claim that it will be the future of money. Do you think that will actually happen?

Well, it looks like it’s a good idea, and it appears to solve a lot of problems. Now you’ve got to remember that I haven’t been following the cryptocurrency scene closely, but as a general observation, cryptocurrencies seem to deal effectively with a lot of problems, but they’re definitely still going through the teething process. What I mean is that crypto definitely still has issues that need to be solved, but I’m confident that solutions will be found.

In any case, it’s pretty obvious at this point that cryptocurrencies work, and as we move towards a world where they’re more widely used, we’ll need to deal with a bunch of issues across the larger software ecosystem to help them gain greater commercial traction.

I think it’s also important to look at blockchain as being more than simply Bitcoin. Cryptocurrencies have demonstrated that there’s a technology base capable of providing distributed trust, and a rule-based process that is going make this useful beyond simply cryptocurrencies.

“Generation Crypto” has become a populist movement over the last decade (CoinDesk)

In terms of cryptocurrency, we had the boom, then the bust — and now we’re apparently in the Gartner “Trough of Disillusionment”. On the other side of that, do you think we’ll see something like Facebook’s Libra project finally catch on as a mainstream cryptocurrency?

The overall concept of using an electronic currency which “dots the i’s & crosses the t’s” seems like a good idea — the question is really how long it will take to figure out all the requirements for it, especially when it comes to the things we take for granted.

Keep in mind that all of the uses & benefits of our existing currency aren’t completely obvious, which may lead to some unwelcome surprises if people transition to a completely new currency. It’ll take a while to adapt to it, and we’ll have plenty of those moments were we say, “oh yeah, it did that for us too…”

When you develop a new solution like cryptocurrency, if you haven’t taken into account everything that the existing solution provides, then it means you’ll have to fall flat on your face a couple of times before you finally realize that the old thing solved a problem we didn’t even realize we needed to solve.

The Gartner Hype Cycle for 2019 shows disillusionment with blockchain & crypto (Gartner)

Now, you’ve written that quantum computing will likely compromise all widely used public key crypto systems in the next couple of decades — which has far-reaching security ramifications, especially if cryptocurrency ends up becoming “the future of money”. How big of a threat do you think quantum codebreaking may turn out to be?

Well, it depends on how well-organized people are. If we adopt quantum resistant public key systems before someone builds a quantum computer that can break all of the existing systems, then we’ll be fine. However, if we’re not prepared, then it could be a problem. So, that’s a clear indicator that we need to transition to quantum resistant systems before somebody walks in and says, “Hey guys, we got a quantum computer. You’re now going to play our game or we’re going to make problems for you.”

Now making that kind of a transition is very possible, for blockchain in particular. It’s all based on digital signatures, and we already have a quantum resistant digital signature. If you go and look at what the NIST Post-Quantum Crypto Project is doing, they’ve got some candidate quantum-resistant digital signatures, and I happen to know some of them actually work and are quite reasonable, because they’re based on stuff I did in my PhD back in 1979. So yeah, they’re quite good systems.

In terms of which post-quantum system to use, it largely comes down to performance, and they’re in the process of analyzing that now. That means it will be a little while before we have an improved NIST signature system, but if you want to start switching over to a quantum-resistant system, you can certainly start planning the transition.

In fact, depending on your requirements, you may even be able to make the transition to quantum-resistant algorithms now — but you may want to hold out for a bit and wait for a system that offers better performance.

IBM’s Q System One brings circuit-based quantum computing to the private sector (IBM)

You’ve mentioned quantum-resistant systems on your website — including a favorite called SPHINCS+ which is being considered by the NIST Post-Quantum Crypto Project. So when you talk about switching to one of these systems, are you thinking something like SPHINCS+ would be worth serious consideration?

Yes, and these are the systems that NIST is still reviewing. Some of the algorithms have a little bit of a “gotcha” that will make switching a little bit more difficult. For instance, there’s a state-based signature algorithm that requires you to store the state of the algorithm, but there’s are also more traditional stateless signature systems that are hash-based being considered.

Again, you can start thinking about those transitions now, and it’s probably good to at least be in the planning stages for a transition. The problem isn’t with envisioning how to go quantum-resistant, but comes from the implementation, validation, and testing to ensure that it actually resists quantum attack, which may take years for the standards bodies to agree on.

Now during this process of adoption, if somebody comes up with a quantum computer capable of breaking today’s cryptography, then you’re basically caught with your pants down, right? So it makes sense to start preparing now rather than take risks on security later.

All in all, I think we should be moving at a reasonable pace towards quantum-resistant systems. It’s something we need to do, because otherwise we run a significant risk of vulnerability, but since it’s on such a core level of computing, it really makes everything vulnerable.

The worst case scenario is pretty bad: imagine that someone breaks it, keeps it secret, and then suddenly they have access to everything. That would enable them to put their thumb on the scale in a way which is invisible, which makes me a little nervous. We’d like to make the transition before that happens.

The binary hash tree construction for the SPHINCS+ stateless signature (SPHINCS)

Now let’s turn this around: quantum computing can also be used to generate cryptography, right? Is that a potential solution to this issue?

Well, quantum key distribution is something that could be quite resistant to attack. On the other hand, we do have more conventional methods of public key distribution that work and are resistant to attack by quantum computer, which should be quite satisfactory.

Ultimately you have to weigh the costs against the benefits of a quantum key distribution system. I’m sure there are situations where it would be advantageous, so the question then becomes whether it’s worth the cost of that level of security, especially taking into account the kind of attacks we’re concerned about. Does it actually help us better prevent attacks? That’s a key factor in deciding on this, because it may be quite costly.

China tested what’s being called a “hack-proof” quantum satellite in 2017 (Science)

There are already papers available discussing satellite-based quantum key distribution, some of which are discussing a “quantum internet”, where communications involve entangled photons. What are your thoughts on that?

There are a lot of people making big advances in quantum computing right now. It’s pretty clear we’ll be seeing quantum computers, networks & algorithms playing a much larger role in future computing, and it will open up a lot of new capabilities for information processing & communications.

The big question is how fast are these quantum computers & communication systems going to be developed, and how widely will they be deployed? There’s also still a question as to how many things quantum algorithms actually do. We know they’re good for code breaking, for instance, but what other tasks will they prove useful for? We don’t know yet how well they’ll compete with traditional computers, and we’re still only beginning to explore new areas where specialized quantum systems will excel at.

My feeling right now is that quantum computers are going to be a niche application, and we’ll continue using general purpose computers for most of our computing. I’d expect to see quantum computers as an add-on processor for the handful of applications where they’re really useful, but they won’t be doing sort of the general purpose work that’s the “meat and potatoes” of today’s transistor-based computers. That may change, but that’s my feeling right now.

About Our Guest

Dr. Ralph Merkle has been a Distinguished Professor at Georgia Tech, and is currently a Senior Research Fellow at the Institute for Molecular Manufacturing, in addition to being a Chair Emeritus at Singularity University, a Director at Alcor, and Co-founder of the Nanofactory Collaboration. He has also been honored to be a recipient of the 2010 IEEE Richard W. Hamming Medal for outstanding achievement in information science, in addition to a 2011 Fellow at the Computer Science Museum for his work on public key cryptography.

This article was originally published by: https://medium.com/swlh/ralph-merkle-on-cryptocurrency-post-quantum-cryptography-6bf4cb5a9dea


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s