If Murphy’s Law holds that everything gets worse, Moore’s Law has long been the opposite, at least when it comes to computing.
Named for Intel co-founder Gordon Moore, it states that the number of transistors that will fit on a chip doubles roughly every 18 months, which explains why our gadgets keep getting better, stronger, faster, smaller.
Unfortunately, in as little as 10 to 15 years, this relentless process will crash into the limits of physical possibility, as transistors shrink to atomic proportions.
Enter quantum computers, which don’t yet exist in practical form, but promise an expanded and vastly more powerful computing environment.
Quantum computers will be able to break many of the cryptographic locks we use to protect data today, but quantum technologies also mean we will be able to build new locks that can’t be picked, not even by a quantum computer.
As concerns mount around online privacy and data security, scientists in Waterloo have been immersed in world-leading cryptographic research to prepare us for the quantum future.
Communitech caught up with Michele Mosca, deputy director of the Institute for Quantum Computing at the University of Waterloo, to talk about quantum cryptography and its implications for online privacy and security.
Mosca, also a founding member of Waterloo’s Perimeter Institute for Theoretical Physics, was a driving force behind IQC’s creation in 2002, along with Research In Motion co-CEO Mike Lazaridis and PI’s then-executive director, Howard Burton.
IQC’s faculty of 17, set to expand to 30 in the coming years, are building on decades of Waterloo expertise and inspiration, including that of late professor Bill Tutte. His code-breaking exploits for Britain, largely unsung, gave the world its first electronic computer and changed the course of the Second World War.
UW is also home to the Centre for Applied Cryptographic Research, where Mosca is an affiliate faculty member.
Mosca, who describes Waterloo’s quantum research as “second to none,” says no one can be sure when a quantum computer will arrive, so it’s critical to prepare now to ensure our secrets will be safe in the future.
Q – What is cryptography?
A – Cryptography refers to the basic mathematical tools we use to try and provide information security.
We often think of it in terms of privacy, but it’s broader than that. We also want data integrity. I might get a message and I might know it’s secret, but how do I know no one has changed it? So I want data integrity, and I also want to know it came from you and not someone else.
Cryptography is the use of mathematical tools to achieve those objectives.
There are also physical tools; you could lock information in a safe and carry that safe around, but cryptography is a way that you can mathematically scramble it, or have a mathematical access structure to it.
Q – So you’re turning it into a code that hopefully can’t be broken?
A – Right.
Q – How does quantum cryptography differ from classical cryptography?
A – There are generally two types of classical cryptography.
There are codes that are computationally secure, where you hope you can’t break the code but you don’t really know for sure; then there are others, which are information-theoretically secure, where we know that there just is not enough information to break the code.
We generally use computationally secure crypto because it’s more efficient and you can do more things with it. The number of things we can do with information-theoretic security is more limited, and usually requires more resources.
So what’s quantum cryptography? It’s a vague term, but the broadest definition is, it’s crypotography in a quantum world. So, you have to take into account the potential existence of quantum computers.
Computational security is based on some mathematical problem being hard, on a computer. But now, we have to reassess what’s hard and what’s easy, taking into account quantum computers.
Almost all of the currently used public-key cryptography relies on either factoring being hard, or this elliptic-curve problem being hard. Quantum computers can break both of those problems, so most of the currently-used public-key cryptography would be broken if and when we have a quantum computer.
So, we need to find and deploy alternatives that are secure against quantum computers.
Q – Is that because a quantum computer could come into existence sooner than we think?
A – We don’t know. If you ask any of the experts in the field who are trying to build one, they’ll say it’s not going to happen any time soon; we just don’t know. That’s the correct answer.
But, as with any fundamentally new or disruptive technology, you’re not going to get a big lead time. They’re going to go from not knowing how, to ‘Oh, here it is.’ Once you have it, you can start making predictions that are pretty reliable, but it’s the breakthrough stuff that no one’s able to predict.
Now, if you go and ask the experts, ‘Are you going to build a quantum computer in the next five to 10 years,’ they’ll say no. But in the big picture, hundreds of the world’s smartest experimentalists and theorists are working on this, and they’re all making progress.
So, I’m optimistic that it’s going to happen, but it’s one of these intrinsically unpredictable things, and there’s no reason to expect to get a long heads-up. There’ll be a pretty fast eureka moment, and we’ll have the first-generation quantum computers shortly thereafter.
Q –So we need to be ready, because when that happens, people will be able to break the security codes that are out there now?
A – A quantum computer won’t break everything that’s out there now, but it’ll break some of the key tools that we’re using today, and these aren’t obscure tools; these are ubiquitously deployed around the world.
But back to your question, what is quantum cryptography? There’s this whole aspect of re-evaluating computationally secure cryptography in the quantum paradigm, where you have quantum computers, and one needs to prepare for this, because we don’t know when we’re going to have one.
The other thing is, quantum information offers a host of new cryptographic tools. It redefines which computational tools are secure or not, but then it gives you a new tool chest as well. It gives a new tool chest both to the cryptanalyst (code breaker) but also to the cryptographer (code maker).
With quantum systems, we have the Heisenberg Uncertainty Principle – if you try to extract information from a quantum system, you have to disturb it. What that means is, you have eavesdropper detectability.
So, I take a quantum system and prepare it in a state I know, and I send it to you, and if an eavesdropper tries to look at it to learn about it, they have to disturb it.
So then you get it, and you do a few measurements and tell me what you’ve got, and I say ‘that’s right,’ and we can determine, with exquisite precision, how much it’s been disturbed.
At a high level, that’s really how quantum key establishment works: We somehow exchange quantum states; we talk about them to see if there’s been any disturbance; if the disturbance is small enough, we distil out the knowledge the eavesdropper could have had, and now we share common, random data.
Now you’ve established a key, and with this key you can meet all sorts of important cryptographic objectives.
Q – Can you describe a real-world situation where that would be really valuable?
A – There are many different layers of IT infrastructure where cryptography is used. Your service provider could be encrypting your data, and it exists at the user level as well.
Currently, there’s a company in Switzerland that sells devices to do this kind of key establishment. These are first-generation products, so they’re big and they cost a few tens of thousands of dollars. It’s not ridiculously expensive, but it’s not something you can put on a BlackBerry today.
The tough thing about crypto is, your customers generally don’t want anyone to know that they’re your customers. So, they have confirmed that they do have banks amongst their customers, and they have government clients to which they sell these quantum devices, and/or they sell devices that do the current classical cryptography protocols, but are quantum-compatible, where at any point in the future they just plug in the quantum-key distribution, or QKD as it is normally called.
One of the current applications is called the link encryptor. You have a link between two branches of a company, or from a company to a backup centre a few kilometres away, and you can encrypt that link with QKD and know that if somebody’s eavesdropping on it, they’re not going to be able to get any information out of it.
That’s one of the niche applications, and it’s niche because of a lack of economies of scale. Once this technology is developed and more mature and cheaper and faster and so on, and smaller, then we can talk about handheld devices.
And people have been looking at the possibility of doing it with handheld devices. In these resource-constrained environments, efficiency of the codes is critical.
Elliptic-curve cryptography (ECC) replaced RSA (the widely-used mode of key encryption) in many of these constrained environments, because it’s efficient, and there are situations where RSA is not practical. That’s why ECC is ubiquitous on the BlackBerry, because it allows for efficiency.
In the short term, QKD is not going to be efficient or practical enough for a lot of these applications, but in future generations it should be, and there’s no reason it can’t be.
Quantum key distribution is short term; we can implement it, essentially, with current technologies. There are others, like quantum money, digital signatures and so on, which will require technologies that we don’t have in the short or medium term, but in the distant future we might have those.
But then, we’re studying what else we can do in the short term.
Quantum random number generation is another great tool. We need random numbers for all sorts of cryptographic and other purposes. The gaming industry, they need good random number generators, and quantum mechanics is potentially the only real source of randomness.
We can build these quantum random number generators, and they are for sale, but we can improve them and make them even more robust. I would call that a quantum-crypto technology, a very basic one.
We study the full host of things, from what we can do today to what we can do someday when we have quantum computers.
The nice thing about QKD is we have the first generation of these products.
Ultimately, the users don’t care if the technology is quantum or classical. What they do care about is whether it is secure against quantum technologies, because they’re coming and we want to be safe in that environment.
Q –Why is the shift to quantum cryptography important right now?
A – If you can, overnight, switch to a quantum-resistant code, and if you don’t have to provide long-term security, then yes, you can wait and see. But in most applications they are not ready for that change; they don’t know what the replacement would be and it takes years and years, even decades, to deploy them.
So, if it’s going to take you decades to deploy a quantum-resistant alternative, then you’d better hope you don’t have quantum computers within that time.
But it’s not just that. For some people, their security guarantee is just a few seconds. Like, if somebody is just authenticating your identity to me, they just do it now and once it’s done, it’s over; you’re not concerned about somebody breaking that code in the future, because who cares? It’s done.
But, in other cases, you need that information to be secure for a year, 10 years, and in some cases 100 years. For example, with health information, people really do want their information to be private as long as they live, if not longer.
If you need to provide decades of security, you’re already being reckless if you’re not switching over to quantum-resistant tools.
There’s no way you’re guaranteeing that we’re not going to have quantum computers for decades. How many years will it take you to switch to something that’s secure? Changing the infrastructure takes years. So that’s why we can’t wait.
Q – What are the main threats to the predominant cryptography systems in use today?
A –I like to partition information security into three pillars. One is trust; you have to trust your IT administrator, you have to trust your certificate authority; your browser has all these certificates on them.
When you open an e-mail from somebody, assuming it was from them, you trust them enough to open up that e-mail, because if you open it and run their software you might install some kind of worm or virus on your system.
You can encrypt your private data with an unbreakable code and send it to somebody and it goes to that right person, but if they’re not trustworthy, then your privacy’s gone.
Second, there’s physical security. I can have an unbreakable code, I can have it in the house of somebody I trust, but then if people can just look in the window and look at my screen – I mean, you always have to have some physical space that you’re assuming is not being accessed by adversaries.
The third pillar is cryptographic systems. These are mathematical tools that allow you to scramble information, and once it’s scrambled, you can take it out of this physical safe haven, put it out into the cloud where you assume anybody can look at it, and yet it’s still protected. That’s an amazing thing.
And you can have access structures, where only people who can prove their credentials can access the information; only the doctors in hospitals or whoever can access that information.
I could keep it locked in my basement, but then nobody can access it, so you want to make it accessible to only the right people. And that’s where cryptography becomes critical.
These three things, together, can achieve something that the other two can’t do on their own.
I would say the predominant threats today, in practice, would be bad trust assumptions and user errors.
Probably the next predominant threat is bad implementation. We might have an unbreakable protocol or a good system in theory, and then you go implement it and you might take some shortcuts, or you just might make a mistake, or your physical security is just not up to snuff.
Any new system will have something that somebody overlooked, so it takes a few years of people attacking the physical device and realizing, ‘Oh, look, there’s a side channel,’ or that your screens radiate information and you have to lower the intensity of the radiation so you’re not giving away secrets unintentionally.
Then there are bad protocols. And it’s hard; you start getting these really complicated multi-party protocols, and how do you prove they’re secure? You prove they’re secure in some abstract, idealized model, but does it capture the essence of the real protocol? Sometimes yes, sometimes no.
In recent weeks there’s been another break through SSL (Secure Sockets Layer) and so on, where there was a protocol flaw. You can look back and say ‘it shouldn’t have been there,’ but it was.
Sort of at the bottom of the list now is bad cryptography, or breaking an actual cryptographic primitive. A primitive is a very fundamental tool, like an encryption function, or an authentication code. It’s a way of taking a message, plus your identity, and putting a small signature which people use to verify that that message was really sent by you. These types of primitives are then used in a more complicated system or protocol.
When you authenticate yourself to Amazon, you’re gluing together all sorts of little cryptographic primitives.
Occasionally, people break the actual primitive, but today, the real practical problems that security experts will tell you about are these higher-level things that don’t have to do with cryptography.
So, that’s one of the reasons they don’t pay a lot of attention to the cryptography layer that we’ve been talking about. It’s because today, it’s sort of the least of their worries.
We’re trying to get on their radar screen and say, ‘Look, the whole infrastructure’s built; cryptography is not just some esoteric part of the infrastructure.'
These cryptographic primitives are the foundation on which you build the protocols, and then you implement them, and then you use them with trusted people.
Today, most systems are broken at the higher layers, but what we’re saying is, with quantum computers, a lot of these primitives are going to be broken. And with quantum communication and other quantum technologies, we can find new, better primitives out of which to build the foundations.
So, it’s a special time in the history of cryptography in that we know we need to fix the foundations, because there are some key pieces that are broken with quantum computers, and we have these really wonderful new primitives to put into the foundations as well.
Q – Where does Waterloo sit in the world of quantum cryptography research, and how is its work regarded?
A – Waterloo has a long-standing reputation in classical cryptography going back to the early 1980s, when the data-encryption group was founded at the University of Waterloo, out of which Certicom was founded. Certicom is the primary developer of elliptic-curve cryptography, which is now used in standards around the world and in BlackBerry.
We didn’t know it, but it actually dated back even further, with Bill Tutte. He was a crypto who figured out how to break these high-level Fish codes that the Nazis were using for high-level strategic communications, and they built Colossus (the world’s first electronic computer) to implement his cryptanalytic attack on these Fish codes.
It was amazing that he found out the structure of the codes, and then he found out how to break them, but it was computationally intensive so they built Colossus, and it was one of the greatest intellectual feats of the war, and of the 20th century. But it was classified, so he never talked about it.
He came to Toronto actually, but he was doing mathematics, which maybe wasn’t so fashionable, so we headhunted him to Waterloo. We largely built the mathematics faculty around him and others, but he was certainly one of the major pioneering figures in the math faculty at the university.
And many of the people he supervised and mentored, and the people they supervised and mentored, were the founders of the cryptography group.
The data encryption group started the Centre for Applied Cryptographic Research, which recruited me to start a quantum computing group because they realized that you can’t do 21st-century cryptography without knowing about quantum computing and quantum cryptography.
This is because quantum computing defines what’s hard and easy, so it defines which computational-secure protocols are really secure, and it also gives us new quantum protocols.
So I was hired, and then I said ‘you can’t have a quantum computing group without some physics’, so we started expanding into physics, and then Perimeter Institute and Mike Lazaridis came along and said, ‘Well why don’t you take this up a few notches’ and started an institute for quantum computing.
We now have 17 faculty and we’re going to grow to 30.
Since the late 90s we started making our name in quantum computing and quantum cryptography, and now I would say we’re regarded as one of the world leaders in quantum cryptography.
We have many of the top people developing new cryptographic primitives and new applications, and blind quantum computing and quantum fingerprinting and so on.
We have Norbert Lütkenhaus, who is a world authority on the security of practical QKD systems. Norbert is second to none in the world in this field.
We have guys like Thomas Jennewein, who is an expert in freespace quantum communication. He’s leading a project to do quantum communication with satellites, which will help us achieve long distance. One of the short-term challenges of quantum key distribution is, you can only do it over a few tens or a couple of hundred kilometres. One solution is to use satellites to achieve global distances, so Thomas is a world leader in that.
We have world experts in quantum algorithms for those interested in quantum cryptography, but also for people who want to do computationally secure classical cryptography that is secure against quantum computers.
I think we sit very well – second to none – in terms of quantum cryptography research in the broad sense, and also in the narrow sense with quantum key distribution.
Q – How is quantum cryptography already contributing to protecting people’s privacy, whether online or on mobile devices?
A – I would say the deployment of quantum cryptography is still very limited right now, so it’s not currently being used on a large scale. But there are banks using it, and governments and so on currently, in these niche applications, link encryptors and so on.
In the broader sense, there’s a question of people having confidence in the systems we use today. Do you trust that your health information is really going to remain private, and so on.
I think people probably are a bit nervous or skeptical about long-term security right now, for many reasons, including the prospect that quantum computers will break some of the existing codes.
There have been several demos of small networks around the world; there’s QKD network demos in Tokyo, there was one in South Africa at the World Cup, there’s one in Europe, one in China.
Q – What about this notion of authorities, such as the government or law enforcement, always wanting to maintain some kind of back door into our information? Does that pose a threat to full-scale development of the most secure cryptographic solutions?
A – I don’t think so, not in any fundamental way, because there are unbreakable codes already. So, if the bad guys are organized, there already are unbreakable codes they could be using, so really, why don’t we let the good guys have a robust infrastructure?
If you talk to a privacy expert and you suggest the notion that only bad guys want to keep their information secret and have something to hide, they’ll rip you to shreds and give you 20 reasons why this is a fallacy.
Privacy is fundamental to our freedom in many ways, our autonomy and so on.
Also, one of the ways we catch criminals is by people volunteering information, and these people want their privacy to be preserved, for very good reasons. They’re the good guys and they’re willing to stick their necks out to help law enforcement authorities track down criminal behaviour, and they want assurances that they’re not going to be revealed.
So I think on the whole you want a robust, reliable information security infrastructure. You can still have lawful access and all these things; there’s nothing fundamentally stopping it; it would work just the way it works today.
Q –What commercial opportunities will quantum cryptography create for Canadian tech entrepreneurs looking to do business in the online security market?
A – I think there are two big opportunities here.
The first one is delivering the next-generation cryptographic infrastructure. As we’ve discussed, the current one is broken, and it’s broken in many different ways. It’s broken from the trust and implementations, but also at the very foundation, so people are going to have to fix all these layers, but the foundation will be used everywhere.
If something’s working, and you say ‘I could do it better,’ then you’re probably going to get ignored, unless it’s really a lot better. But because it’s not working, we basically have to open up the black box at the bottom and fix it, and there’s also the chance to put in new stuff into that black box.
So, there are some serious problems to be fixed at the foundation of cryptography, so if you can be part of the solution, that could have a huge impact and you’d have a very broad market.
This includes being ready and able to deliver standardized and certified quantum-resistant tools, both quantum and classical tools, especially in resource-constrained environments. And the further down the chain you can go, the broader the market.
Security underlies the entire ICT infrastructure, so there’s huge opportunities. The trick is, this is what people would call a disruptive technology, and conventional business analysis and reasoning don’t usually apply to disruptive technologies.
There’s a market to be invented, to a large extent. There is an existing market, but to a large extent it’s uncharted territory. So that’s opportunity number one: Developing, delivering, deploying the next-generation cryptographic infrastructure, because it has to be done.
What it will look like and how it’ll work, we don’t know yet. That’s sort of the exciting part of it.
And the other great opportunity, perhaps the greater one, is to be a pioneer in ‘Quantum Valley.’ Have you heard that term yet? (Former UW president) David Johnston coined it.
As you go and develop and deploy these quantum tools, you’re going to be developing all this expertise in quantum technologies. You’re going to have to figure out how to certify them and standardize them and mass produce them and so on.
These quantum technologies, these basic building blocks you’ll need to build QKD systems, for example, will have other applications. So as you build this one component for this one application, there’s a world of opportunity for all these other applications.
I already mentioned quantum random-number generators. Another host of shorter-term applications of quantum technologies is to do more-precise measurements, whether it’s for medical purposes or for oil exploration or for sensing other very, very weak signals. Sensing is sort of the nearest-term wave of technologies where quantum information can be applied.
The thing is, we’re not talking about harnessing something obscure and esoteric. We’re harnessing something really fundamental, one of the most fundamental aspects of nature. So the potential of figuring out how to harness it is enormous, and surely beyond our current imagination.
We just have to have this intuition to say, are we harnessing something fringe and esoteric, or is it really fundamental? Well, really it’s fundamental; it underlies the fabric of reality and physics.
So those are the two big opportunities.
Fourth in an ongoing series.
Part 1: Q + A with Mark McArdle
Part 2: Q + A with Jennifer Stoddart, Canada's Privacy Commissioner
Part 3: Q + A with RIM's Scott Totzke
