Getting ahead of quantum computing

As with any tool, the next major advance in computing will be used for both good and bad.

Quantum computers promise to speed up research into fundamental physics and chemistry and “needle in a haystack” searches of large databases. But they may also be used to quickly crack the cryptography that protects the world’s information and communications systems, making everything from ID card authentication to legally binding documents and electronic elections vulnerable to being hacked.

Today’s quantum computers are still rudimentary and it is not yet clear when they will become a threat to classical crypto protocols, but researchers are scrambling to identify alternatives that could be impregnable to this new form of computing. To that end, Dominique Unruh, a professor of information security at the University of Tartu, has already developed a proof of concept for software that could verify whether new crypto schemes are breakable by a quantum computer.

There may be no time to lose. “It should be several more years before [quantum computers] can break cryptography,” Unruh says. “But we want to be on the safe side […] even if we had the guarantee that it takes 10 years, we would already have to hurry. The end goal is to develop computer software that researchers can use to check that new crypto schemes can withstand attacks by quantum computers.”

Why are quantum computers upending cryptography? A classical computer encodes information as binary bits, which can be a 1 or 0, meaning it can only perform calculations in sequence. By contrast, a quantum computer can encode information as a 1 and a 0 at the same time, meaning it can perform large numbers of calculations simultaneously. “Quantum computers can solve some problems extremely fast, but for other things they are no faster than classical computers,” notes Unruh. “But some of the problems that quantum computers can solve faster happen to be mathematical problems that you can use for breaking a cryptographic scheme.”

The big burden of proof

Researchers are trying to reinvent cryptography by using quantum mechanics to develop new kinds of mathematical problems that quantum computers won’t be able to solve within a reasonable timeframe. Backed by €1.7 million of funding from the European Research Council, Unruh’s research team is rigorously evaluating cryptographic protocols based on these new problems: the goal is to verify mathematically, to a high level of confidence, that the resulting cryptographic protocols are secure.

Although the developers of such problems generally write a proof to show that the resulting   cryptography will be secure, checking such proofs is very difficult. “It's quite hard to check a proof carefully, because it has so many steps and the maths is so complicated, that you can easily just overlook that someone made a mistake,” Unruh says. “It could even be that for several years some proof stays published and no one ever notices that it's wrong.  One way to counteract this is to verify the security proofs on a computer.”

However, a computer cannot just read the proof written in a scientific paper because it will be much too informal, in the sense that a human being won’t write out every single step. Developing a proof that a computer will actually accept can be a herculean task, says Unruh, explaining that a 10-page proof may have to be extended in length to 500 pages to make it understandable for a computer.  “I'm working on computer software that can check the proofs, and that can help in writing them, where the hope is that at some point the effort needed will become reasonable.”

Although computer verified proofs for cryptography schemes remain few and far between, Unruh says demand is increasing. “A decade ago, the view was computer verification is a nice idea, but we don't really care,” Unruh adds. Now “the attitude is more: okay, if we can have it, we better have it.”

At the same time, Unruh is also working on developing the proofs themselves. “If I wouldn't develop these proofs, I wouldn't get the feedback myself on what the tool should be able to do,” Unruh says. The University of Tartu team has even had to develop theoretical foundations and new kinds of logic for reasoning about quantum programmes.

International standardisation of post quantum cryptography

One of the drivers behind Unruh’s work is to support the standardisation of the next generation of cryptography. The National Institute of Standards and Technology (NIST) in the U.S. is at the forefront of the international efforts to create a consistent global approach to post quantum cryptography. Having called for proposals for international standards, NIST is now in the midst of a lengthy (up to eight year) process to whittle down potential candidates. These candidates will need to be stress-tested and Unruh claims to have already succeeded in formally verifying a construction that is very similar to constructions used by some of the contenders.

Unruh is also hopeful that work on verifying quantum cryptography will also help other researchers verify quantum computer programmes will do exactly what they are supposed to do. The techniques used to formally verify cryptography and its theoretical foundations are similar to those used to formally verify software programmes.

While the ERC funding runs for another four years, the work in this area may need to go on and on. “This is basically open ended,” Unruh says. “This is the kind of work where it's just going to become better and better … so this could go on forever.”

One of the key challenges for Unruh’s research team is to share its knowledge and concepts with other researchers so they can properly make sense of the tools being developed at the University of Tartu. “Ideally there would be a point when I don't have to work on that anymore because other people can continue where I left off,” Unruh says.