The race to build an uncrackable computer network

"I was surprised, of course," says Brassard, now a professor of information science at the University of Montreal, "but I continued to listen politely." According to him, this conversation eventually became the event that changed his life. The stranger was Charles Bennett, a physicist from IBM, who recognized Brassard from a conference they attended. The idea of ​​quantum notes intrigued them both, but they knew it was technically impractical. Even today no one knows how to capture, freeze and store photons inside a piece of paper: light particles tend, as we know, to move fast.

"We're in a better position today, but still nowhere near anything resembling practical quantum notes," says Brassard. "It was a thought experiment that served as a starting point. This is a great example of a completely absurd idea from a practical point of view, but at the same time also crucial, because from it Bennett and I developed the idea that is now known as quantum key distribution.”

Distribution of quantum keys, and in short QKD, is a technique for encoding and transmitting data using photons. Basically, it is uncrackable encryption. After that day on the beach, Bennett and Brassard began a collaboration that lasted five years, bringing to the world the first encryption technique in history that does not rely on mathematical complexity, but on the laws of physics. When Bennett and Brassard published their work in 1984, only a few researchers paid attention to the idea, and many paid no attention to it at all. "It is considered a marginal occupation," says Brassard, "even in the eyes of those who have paid any attention to it." I think we didn't take him too seriously either."

Things have changed since then. Thirty years ago, almost no one - except for government intelligence agencies - used encryption technology. Today it has become essential for daily transactions on the Internet. Whenever someone types a password or credit card number online, sophisticated software built into browsers works behind the scenes to ensure that information is protected from online theft. "This is a technology that everyone needs, but no one is aware of," he says and steam up close, a researcher at the Institute for Quantum Computing at the University of Waterloo in Ontario. "She just works."

But her days may be numbered. Almost every existing encryption method will be rendered useless by the advent of quantum computers: machines capable of cracking the complex codes that protect everything from Amazon shopping to the power grid. While no one has yet built a complete quantum computer, researchers in academic labs, industry, and government all over the world are trying to do so. Among the documents revealed by the leaker Edward Snowden is a description of a secret project of the American National Security Agency (NSA), called "penetrating difficult targets" - an attempt at a cost of 79.7 million dollars to build a quantum computer. "It's hard to say with certainty that there won't be such a computer in ten or fifteen years," says Ray Newell, a physicist at the American Los Alamos National Laboratory.

If, or when, the first quantum computer becomes operational, the best defense against its code-breaking capabilities may be another kind of quantum magic: encrypted network technology based on the theory developed by Bennett and Brassard 32 years ago. It turns out that quantum cryptography—a method of encoding transmissions that exploits the strange properties of single particles of light—is an easier problem to solve than building a quantum computer, and in fact there are already several small active quantum cryptography projects. There is only one problem: replacing the encryption systems all over the world with quantum systems will take more time than the development of quantum computers. "If you think we will have a problem in 10 or 15 years, you should start solving it yesterday," says Newell. "Most likely we are already late."

Very large numbers

Behind the simple clicks and clicks of online trading are complex and elegant mathematical frameworks of two types of encryption: symmetric encryption, where the same key is used to encrypt the data and decrypt it, and asymmetric encryption, where one key encrypts the message and another key decrypts it. Any transfer of secure information on the Internet requires the use of both methods.

A typical communication between the home computer and the servers of an Internet store begins with the creation of a symmetric key, which the customer and the seller share over the network to encrypt credit card numbers and other private information. The key is basically a collection of instructions for encoding the information. For example, a ridiculously simple key could specify that each digit in a credit card number be tripled. Of course, in the real world the keys are much more mathematically complex. Every time someone buys something online, their browser shares a key with the online store's servers. But what secures the key itself at the beginning of the process and maintains its privacy? A second layer of security, this time asymmetric, is what encrypts the symmetric key.

Invented in the 70s simultaneously by the British Secret Service and by academic researchers, asymmetric encryption uses two separate keys: a public key and a private key. Both are essential to any encrypted information transfer. During the online purchase, the seller's servers send their public key to the customer's computer. The client computer uses this public key, which is available and open to all clients, to encrypt the shared symmetric key. When the servers receive the encrypted symmetric key, they decrypt it using the private key, which no one else has. Now the symmetric key is shared and safe to use, and is used to encrypt the rest of the transaction.

The public key and the private key used in asymmetric encryption are derived from the factors of very large numbers: more precisely, prime numbers, which are integers divisible by only 1 and themselves. The public key is the product of two large prime numbers, while the private key is the two multiplied numbers. Even a child can multiply two prime numbers, but the opposite operation, of factoring a large number into two prime factors, is a difficult task for even the most powerful computers.

The numbers used for asymmetric encryption are often hundreds of digits long each. Newell says that finding the prime factors of such numbers is like trying to separate colors mixed in a container: "Anyone can mix colors, but not separate them."

The most common asymmetric encryption method is known as RSA, named after its inventors: Ron Rivest, Adi Shamir [now at the Weizmann Institute] and Leonard Edelman, who developed the idea in the late 70s at the Massachusetts Institute of Technology. Since then, the keys have gotten longer and longer to protect them from hackers equipped with faster computers and improved skills: cracking a longer key requires more computing power. Today the typical asymmetric keys are 1024 bits long, but even if we put aside the question of quantum computers for a moment, that may not be enough to stop future cyber attacks. "The American Standards Institute (NIST) recommends upgrading the RSA key size to 2048 bits," says Richard Hughes, a physicist at Los Alamos. "But increasing the key will have a price in terms of performance. The annoying delay after you click the buy button, when the computer seems to freeze for a moment: this is the encryption of the public key in action. The longer the key, the longer this wait will be." Unfortunately, the processors in our computers are not improving fast enough to keep up with the encryption algorithms needed to deal with longer and longer keys. "This is problematic in many respects," says Hughes. "If you operate a cloud service, with many keys that work at the same time, or manage a system like the electricity grid, you cannot allow such delays."

If quantum computers appear in the field, NIST's recommendations will also be irrelevant. "I think that by 2030, there is a 50% chance that a quantum computer will be able to crack RSA-2048 encryption," says Michel Mosca, one of the founders of the Institute for Quantum Computing. Donna Dodson, senior cybersecurity advisor to NIST, says that "in the last five years we have seen many developments that make us believe that we should be prepared in case quantum computers do appear. Our working assumption is that the chances of this are high."

About codes and qubits

What makes quantum computers so powerful? In a normal computer, each bit of information can be in one of two states: 0 or 1. A quantum computer, on the other hand, takes advantage of the strange properties of the subatomic world, where individual particles can exist in many states at the same time. Like the cat in Erwin Schrödinger's thought experiment, which both lives and dies in a box until someone opens it to check, the quantum bit of information ("Cubit") can be 0 and 1 at the same time (physically, the qubit can be a single electron held in two spin states at the same time). A quantum computer with a thousand qubits would contain two to the power of a thousand different possible quantum states, a number far greater than the number of particles in the universe. This does not mean that it will be able to store an infinite amount of information: any attempt to view the bits will cause them to immediately receive one specific value of a thousand bits. But with the help of smart programming, it is possible to manipulate the countless states of qubits when they are still unknown, and thus perform calculations that cannot be done with ordinary computers.

In 1994, Peter Shore, a mathematician then working at AT&T Bell Laboratories, demonstrated that a quantum computer could find the prime factors of large numbers of the type used in RSA encryption, the asymmetric encryption method that protects the transmission of the symmetric key in network transactions. In fact, Shore wrote the first software for a quantum computer. Unlike normal computers, where the calculations are performed one by one, in the quantum computer all operations are performed at once, and Shore took advantage of this feature. "His algorithm will crush RSA," Mosca says. However, symmetric encryption methods, the most common of which is BEA (acronym for "Advanced Encryption Standard") approved by NIST in 2001, will remain safe from quantum computers. This is because symmetric encryption software such as AES does not use prime numbers to encode information. Instead, the symmetric keys are random strings of 0's and 1's, usually 128 bits long. This means 2128 possible keys, which would require a hacker to go through a billion billion billion billion combinations to crack the code. The world's fastest computer, the Chinese Tianhe-2, which can perform 33.8 quadrillion operations per second, will need more than a trillion years to test all possible keys. Even a quantum computer won't help hackers crack such large numbers. On the other hand, the massive symmetric keys are encrypted during network transactions by asymmetric software such as RSA, which are vulnerable to breaking into factors invented by Shore.

Before Shore's software can break down RSA, a quantum computer powerful enough to run it needs to be found. Moska estimates that already in 2017, several laboratories in the world will have initial systems of several tens of qubits. According to him, "to find the prime factors of an RSA key with 2,048 bits, you probably need at least two thousand qubits." The jump from tens of qubits to thousands may take another decade, but he sees no insurmountable obstacles on the way. "We already meet most of the performance criteria needed to build a large-scale quantum computer," he says, "just not in the same place and at the same time, in a system that can be scaled up."

Quantum network

The good news is that so far progress in quantum encryption technology has been greater than in building a quantum computer. Quantum cryptography began to gain momentum in 1991, whenArthur Eckert, a physicist from the University of Oxford, published an article on quantum cryptography in the prestigious journal Physical Review Letters. Eckert, who at the time was unaware of Bennett and Brassard's work, described an alternative method of using quantum mechanics to encrypt information. In the end, his paper brought back to consciousness Bennett and Brassard's idea, which turned out to be more practical than Eckert's own solution.

However, it was not until the early 1997s that quantum encryption technology began to leave the confines of the laboratory and enter the commercial world, when physicists found ways to cool photon detectors - which are the most essential and expensive components of any quantum encryption device - using electric currents instead of liquid nitrogen. "When I started studying for a doctorate, in XNUMX, we would cool them by immersing them in a thermos of liquid nitrogen, which is fine in the laboratory, but not practical if you want to use them in a data center," says Grégoire Ribordy, CEO of the Swiss company Quantique ID. This company developed one of the first commercial quantum encryption systems in 2007, and the Swiss government bought the system to protect data centers. Since then the company has also sold systems to Swiss banks, and now it works with a company Battelle Memorial Institute in Columbus, Ohio for the establishment of a network that will eventually connect the company's offices in Ohio with a branch in the city of Washington.

Nino Valente, a physicist at Battelle, shows me one of the encryption devices on a cloudy summer day. "Everything we need is on this shelf," he says. "All the quantum optics, everything needed to create keys and distribute them - everything is here." Valente stands next to a six-foot-tall cabinet in the laboratory located in the basement of the company's offices in Columbus. On one of the shelves in the closet is a metal box the size of a large suitcase. Inside it is the physical realization of the quantum encryption method, first proposed by Bennett and Brassard more than thirty years ago.

The hardware includes a small laser diode, similar to those in DVD players and barcode scanners, which directs pulses of light through a filter made of glass. The filter absorbs almost all the photons and allows, on average, only one of them to pass through each pulse. These single photons undergo polarization in one of two directions, each of which represents a bit value: 0 or 1. After filtering and polarization, the photons serve as the basis for a secret key that is transmitted through an optical cable to the recipient. Hardware on the other side deciphers the key by measuring the polarization of the photons.

Unlike a normal secret key, the photonic key is almost unbreakable (more on this "almost" later). Any spy who tries to read the photons will affect them and change their values. The legitimate sender and recipient can compare parts of the key and thereby verify that the arriving photons match the source. If a disturbance is detected that indicates an attempted eavesdropping, you can abandon the key and start over. "Today there are keys that haven't changed in years," Valenta says. "With QKD, you can change the key every second or minute, and that's what makes the process so safe."

Battelle has already begun installing a quantum network to transfer financial reports and other sensitive materials from its headquarters in Columbus to one of its production facilities in Dublin, Ohio, with a fiber loop 110 kilometers long between the two sites. It turns out that this distance is approaching the upper limit of transmitting encrypted messages in quantum encryption. At greater distances, the signal degrades because photons are absorbed in the fiber optic cable.

To circumvent this limitation and expand the network throughout Columbus, and in the near future, to the city of Washington, Battelle researchers are working with ID Quantique on the deployment of "trusted nodes", relay boxes that receive and resend quantum transmitters. The nodes will be installed in isolated and sealed units that will protect the sensitive photon detectors inside cooled to a temperature of -40ºC. If someone tries to break into the node, the device inside will shut down and erase itself. "Key production will stop," says Don Hayford, a physicist who directs quantum cryptography research at Battelle.

According to him, if the network of trusted nodes works properly, it will be possible to deploy the technology on an even larger scale. He hands me a leaflet with a map showing a future quantum network spanning most of the US. "This is our vision for a quantum network that will protect the systems of the federal banking system," he says. "If we reach all the federal banks, it will be a success. To get from one side of the country to the other we will need about 75 intersections. It sounds like a lot, but even in a normal fiber optic network there are relays at similar distances."

The Chinese government is adopting similar technology and has begun building a 2,000-kilometer quantum network between Shanghai and Beijing for use by government and financial institutions. Hayford's and China's projects can protect banks and other organizations with private networks, but they are impractical for Internet use. The trusted nodes connect one computer to another in a chain, not in a branching network where every computer can communicate directly with every other computer. According to Beth Nordholt, a recently retired Los Alamos physicist, point-to-point connections are reminiscent of the anthralls of the early days of the telephone industry in the late 19s, when thick tangles of cables hung over city streets. "In those days," she says, "you needed a separate cable for each person you wanted to talk to. It is difficult to build such systems on a large scale."

Nordholt, her husband Richard Hughes and their colleagues Newell and Glen Patterson of Los Alamos are working on large-scale quantum encryption. To this end, they created a device, roughly the size of a portable memory stick, that would allow multiple networked devices - cell phones, home computers, and even televisions - to exchange quantum keys by connecting to a central secure server. This invention is called in their mouths QKarD, a linguistic play with the English acronym of the term QKD, Quantum Key Distribution.

The way QKarD works is reminiscent of a telephone switchboard. Each computer in the network uploads its own symmetric keys to the central computer, coded as sequences of photons. This quantum encryption replaces RSA encryption, which is commonly used today to protect the transmission of symmetric keys. As soon as the keys are exchanged, the central computer uses them and AES encryption to transmit normal (non-quantum) messages between the various clients in the network, who need to share sensitive information with each other. Nordholt explains that "the expensive parts of quantum encryption are the single photon detectors, as well as the equipment required to cool these detectors and take care of their safety." She and her colleagues placed the expensive and complex components on one computer placed at the center of the network. The 'client' devices, each of which is equipped with QKarD, will connect directly to the central computer - but not to each other - with optical fibers. The QKarD itself is a transmitter, with a small laser that allows it to send photons to the central computer.

Nordholt's team ran a model of QKarD, in this model the entire system is located inside a small laboratory in Los Alamos, but to simulate distances in the real world, the devices are connected by an optical cable 50 kilometers long, rolled up in a bucket under a desk. A license for commercial development of the QKarD technology was sold to the company Whitewood Encryption Systems. According to Hughes, if the product reaches the market, its price will be about $10,000 for a central computer linking 1,000 devices equipped with QKarD. In mass production, the QKarDs themselves will cost about $50 per unit.

"I would like to see QKarD inside smartphones or tablets, so that it is possible to create a secure connection to the server," says Nordholt. "You can also put one inside the base station in the office, and upload keys [to the server] from there. This way we can create networks organically."

Quantum future?

It takes more than ten years to replace the world's encryption infrastructure. "The more widely deployed something is, the harder it is to fix," Mosca says. "Even if we could carry out the repair at the technological level, it would be necessary for everyone to agree on the method of execution, and for all the components to work together within the framework of one global communication system. Today we don't even have a common electrical system and every time we travel to another country we have to equip ourselves with socket adapters."

The difficulty of the challenge adds to its urgency. According to Nordholt, "It's not just about protecting credit card numbers. The business became very serious." She says that a few years ago, the Idaho National Laboratory conducted research that showed hackers could cause generators to explode by feeding incorrect data into the computer networks that control the power grid. "I don't want to make apocalyptic predictions, but this could affect people's daily lives."

However, it is likely that the first target of the quantum computer will not be the power grid. Many researchers in the field of encryption believe that the American National Security Agency (NSA) and other intelligence agencies in the world store huge amounts of encrypted data from the Internet, which cannot be deciphered with existing technology. This data is kept, it is thought, in the hope that the agency will be able to crack its encryption when it obtains a quantum computer. This means that the agency will lay its hands not only on the private transactions of citizens decades from now, but also on our communications today, which we naively assume to be secure.

"It's crazy to think that there is no one recording all the communications and just waiting for the technology to arrive to decipher everything in retrospect," says Brassard. "So even if the quantum computer isn't available yet, and even if they don't develop such a computer in the next twenty years, once it arrives everything that was sent from day one of the classical techniques [for encryption] will be at risk."

Even when quantum encryption is implemented on a large scale, the cat and mouse games of cryptography will continue. Going by the history of conventional cryptography, there is always a gap between theoretical perfection and real-world implementation. Zulfikar Ramzan, head of technology at RSA (the company Rivest, Shamir and Edelman founded to commercialize their invention), says that when RSA encryption first appeared, it was considered completely secure. In 1995, Stanford University student Paul Kucher discovered that he was able to crack RSA encryption simply by measuring the time it took a computer to encrypt a small amount of data.

"It turns out that if the key has more bits with a value of 1 than 0, the computer needs a little more time to calculate the encryption," says Ramzan. "If the measurement is repeated many times, it is actually possible to recover the entire key - simply based on the calculation time." Closing this loophole was quite simple: the engineers disguised the calculation time by adding a bit of randomness to the process. "But again, this was an attack of a type that no one anticipated, and there may be similar attacks in the context of quantum computing."

In fact, the first quantum attack has already happened. Five years ago, a team led by Vadim Makrob, then at the Norwegian University of Science and Technology, connected a suitcase with optical equipment to an optical fiber that served as a communication line in an encryption system built by ID Quantique. The suitcase temporarily blinded the photon detector of the encryption device with laser pulses, and thus the team was able to decipher an apparently safe quantum transmission.

A normal hacker would not be able to carry out such an attack, says Closer. "It is not suitable for teenagers, and access to an optics laboratory is needed. It's a technology that doesn't exist in basements - yet." The ID Quantique company has since improved its device so that it is not vulnerable to this type of attack, but Makarov's hack burst the bubble of perfection that surrounded quantum encryption. "It's always easier to break than to build," says Makarov.

As far as Brassard is concerned, there is no doubt that the far-fetched idea he and Bennett developed many years ago on the beach - even if it is not perfect - will be essential for the future security of many networks in the world. "It will require a lot of willpower and it will be expensive, just like the war against climate change," says Brassard, "but the investment is zero compared to what we will lose if we don't do it... in both cases."