Inside the Competition That Will Save Bitcoin From Quantum Computers

Andersen Cheng's wife wanted him to take it easy after he sold his cyber-security companies for ~$200 million in 2006 at the age of 43. But he returned to the fray for one last mission—to save the world from quantum computers, whose immense power he believes threatens total social and economic collapse.  

“They can hack into any cell phone, laptops—anything,” he told Decrypt in a recent interview. Even Bitcoin wallets.

For the past 14 years, Cheng, now 57, has run Post-Quantum, a British company building an encryption algorithm resistant to quantum computers. Quantum computers, still prototypes, are thousands of times faster than supercomputers and could crack all modern encryption within seconds. 

It'll be about a decade until Google’s quantum computer hits the shelves (Google is believed to be a frontrunner in the race to build a quantum machine.) Yet Cheng said he was tipped off by anonymous friends from the British intelligence world, to whom he has sold cybersecurity software since the 80s, that quantum computers produced in secrecy by governments could crack encryption within three years.

While the timeline might be debatable, the end result is not: Unless we get in front of the problem, a quantum computer, once operational, could reveal every government’s secrets, drain any bank account and overpower nuclear power stations, said Cheng. The machines could also destroy Bitcoin—a hacker could use a quantum computer to reverse-engineer your public keys to work out your private ones, then drain your Bitcoin wallet.

It’s like walking into a bank vault without drawing a gun: “It’s totally wide open,” he said. 

Cheng claims that unless we act soon the computerized world could devolve into “complete and utter financial collapse.” And that’s precisely what his company wants to avert. 

Post-Quantum believes it has created a quantum-resistant encryption protocol that banks and governments could use to re-encrypt their files, and that blockchains could use to prevent people from hacking the network.

According to CJ Tjhai, one of the co-founders of Post-Quantum and an architect of the protocol, here’s how it works. Post-Quantum’s algorithm encrypts a message by padding it out with redundant data and deliberately corrupting it with random errors. The ciphertext recipient with the correct private key knows which fluff to cut and how to correct any errors.

“You add some extra data to the file—some garbage that’s only meaningful to the private key holder. And you then also corrupt the file: you add errors to it—flip the bits,” he said. It’s a little like how archivists use artificial intelligence to restore grainy videos of WW2 dogfights.

Tjhai said that this algorithm is far more secure than today’s common encryption algorithm, RSA, whose private keys are forged from the factorization of two numbers. It would take thousands of years for even the most powerful supercomputer to guess the numbers, though a quantum computer would have no problem. 

Of Post-Quantum’s encryption method, Tjhai said, “People can try to break this thing using quantum computers, but from what we understand now, they can do it, but it will take an extremely long time.” That’s because quantum computers aren’t designed to be efficient at cracking these kinds of codes.

Post-Quantum’s algorithm is based on an algorithm created in 1978 by Caltech professor Robert McEliece. It doesn’t require a powerful computer and is pretty fast. But it’s only feasible today because hard drives are larger and internet speeds are faster. RSA-2048 has a public key size of 256 bytes, while a code-based algorithm like Post Quantum's can be a minimum of 255 kilobytes.

Tjhai said the algorithm could also project Bitcoin. It would be trivial for someone using a quantum computer to work out the private keys to your wallet, so long as they knew the public key. “With quantum computers, we will be able to reverse that [public key] into the private key,” he said. 

In July 2020, the National Institute of Standards and Technology—the US agency that sets global standards for encryption protocols—announced that Post-Quantum’s encryption algorithm had beaten 82 others to become one of 15 finalists of a four-year-long competition to build a quantum-resistant algorithm.

Post-Quantum’s algorithm is up against three finalists from another class of cryptography: lattice-based schemes, whose algorithms crack codes by finding lines in a grid. It’s expected that NIST will choose a finalist from each scheme for standardization by early 2022.

To reach the final round, Post-Quantum in February merged its submission into one created by one of the world’s foremost cryptographers, Daniel Bernstein. 

Post-Quantum is the smaller fish—though Cheng said that it is by no means less able. Bernstein’s work has thousands of citations and he’s a professor at two leading universities; Cheng’s 14-person-strong company (plus ten contractors) receives no government funding (in 2016 it raised $10.3 million in a Series A), and until the pandemic, operated from an office above a busy McDonald’s abridged to a central London train station.

Andreas Hülsing, a cryptographer from the Eindhoven University of Technology and a finalist on a digital signature submission to the NIST competition called SPHINCS+ and a public-key encryption algorithm called NTRU, told Decrypt that the NIST competition feels more cooperative than a fight to the death; Hülsing, for instance, has worked with many of his competitors and once studied under Bernstein. 

“The schemes which made it to the end are actually the schemes which were around already for the last maybe 10 years, and were essentially tweaked,” he said. Post-Quantum’s submission is a tweak of a scheme created back in the 70s. 

“There were a bunch of proposals which really tried to do a lot [of new things], and sadly, most of them actually failed,” said Hülsing. The finalists, such as Post-Quantum’s proposal, are “well-studied”—they just weren’t suitable for the last generation of computers.

“You don't have many different options. They’re all old schemes, which people try to optimize in a certain way," he said.

Post-Quantum’s ambitions extend beyond the NIST competition. The protocol powers a forthcoming VPN and was the backbone of its short-lived quantum-secure chat app; the company removed it from the Google Play store after ISIS started using it to coordinate attacks. “Too much hassle,” said Cheng. 

“Don’t get me wrong—we still want to make some money out of it,” said Cheng, who headed JPMorgan’s credit risk department in Europe back in the late 90s, saving the world from Y2K—a computer bug many feared would crash the programs holding society together on January 1, 2000, because programmers in the 60s hadn’t the foresight to believe that people would still use them in the new millennium.

It sure beats retirement. "There's only so much golf you can play," he said.