How a scientist’s lifelong love of puzzles led to cryptography that could help quantum-proof the world

At six years old and growing up in Kyiv, Ukraine, Lyubashevsky saw his grandfather more often than he saw his parents, who both worked. His granddad, a math teacher, had a special love for chess and solving number puzzles. With all their time together, that passion passed on to him.

When he was nine, Lyubashevsky moved with his parents to the US. He’s now a cryptographer at IBM Research and one of the leading minds behind some of the quantum-safe algorithms the US government has selected to replace the current global encryption standards. The inspiration for his career trajectory, he said, came from the math games he used to play with his grandfather. The complex, far-reaching equations that led him to work on cryptography could soon help secure the world’s most sensitive data.

“It’s not that there’s something wrong with the type of cryptography we use today,” said Lyubashevsky, who now lives in Zug, Switzerland, with his children. “It’s just that we will soon have technology that can crack it, which we didn’t have back when RSA-based encryption was developed. That technology is quantum computers.”

RSA is a type of asymmetric encryption, which uses public and private keys to secure our sensitive data. That includes anything from medical records and bank documents to secure website access codes and email passwords. It was first outlined in 1977, when scientists Ron Rivest, Adi Shamir, and Leonard Adleman publicly described their RSA algorithm, which takes its name from the first letters of their surnames.

The RSA standard still underpins many of the popular encryption systems today. But quantum computers have been maturing at breakneck speed over the past decade. These machines rely on the mathematics of the quantum world and Why it’s time to take quantum-safe cryptography seriously. Quantum-safe cryptography is here. Read more about why it’s time for industry to adopt it.researchers estimate they may soon be able to decrypt most of our data that has been secured through RSA encryption and other contemporary techniques. There’s an impending need for a totally new type of encryption.

Lyubashevsky had not yet been born when RSA was unveiled. But even with his love of puzzles and mathematics, he didn’t study RSA. Instead, in the early 2000s as a PhD student at the University of California, San Diego, he dove into lattice-based cryptography, a type of encryption method that was very niche at the time.

The beauty of equations

In the intervening years, many have come to believe that lattice-based cryptography will be the main way we protect sensitive data from future quantum computers.

Cryptography is a science — but Lyubashevsky also sees it as something like art. It’s not something that naturally existed — we created it. “If there were no Mozart, none of the beautiful things that he composed would exist,” Lyubashevsky said. “Whereas if there were no Einstein, relativity would still be here, and we eventually would have discovered it. Cryptography is more like the former — the world would go on well-enough without concepts like public key encryption and zero-knowledge proofs ever existing, but it is much better with them in it.“

People have been encrypting things with increasingly complex ciphers for millennia, from Greek scytales to the Enigma codes cracked by Alan Turing in World War II. In 1973, the US National Bureau of Standards (which later became NIST, the National Institute of Standards and Technology) asked the world’s cryptographers to develop a block cipher to use as a national standard.

At IBM, a dedicated cryptography team led by Horst Feistel designed a cipher called Lucifer, which won the competition and became DES, or Data Encryption Standard. DES was cracked in 1997, mainly due to the small size of the encryption key, and computers of the time being able to find a solution with brute-force computation. This led NIST to look for a new standard, and in 2000, the Rijndael cypher led to AES or the Advanced Encryption Standard, which is what many systems are secured with today.

AES is incredibly secure — many consider it to be quantum-proof. IBM researchers expect that a quantum computer built by 2030 would take a hundred billion years to break the AES-128 version of the standard. But AES serves a different purpose to RSA, and the two are not interchangeable. AES assumes the communicating parties share a secret key.

The goal of RSA, on the other hand, is to allow two parties, who do not initially share any common secret, to create a secret that only they share. This secret key then can be used by AES. The security of RSA hinges on the hardness of factoring large numbers. While it’s easy to factor a small number like 12 (3x4), take a large number and even the most advanced supercomputer will stumble. It would take some 300 trillion years for today’s best classical machines to break an RSA-based 2048-bit encryption key.

But in theory, a quantum computer should be able to factor any large number considerably quicker. The same quantum computer that would struggle with AES should be able to break RSA-2048 in just a few hours. This is where lattice-based cryptography comes in.

From numbers to vectors

Recently, Lyubashevsky’s lattice research has set the security world abuzz, but that wasn’t always that the case. The research community had known since the 1990s that a future quantum computer should be able to break RSA, thanks to Shor’s algorithm. But physical quantum computers at the time were in their infancy. Quantum-safe cryptography, Lyubashevsky said, “was not really on many people’s radar.” He chose to do his PhD in lattice-based cryptography precisely because it wasn’t mainstream, mesmerized by the beauty of cryptographic equations. “I could just sit there by myself and just work on this math for, you know, years.”

Having finished his PhD in 2008, Lyubashevsky was offered a postdoc position at Tel Aviv University. He jumped on the opportunity as Israel is a leader in the study of modern cryptography. Tel Aviv university is also the alma mater of Adi Shamir, one of the original RSA developers. But it was Lyubashevsky’s post-doc advisor, Oded Regev, a theoretical computer scientist now at New York University’s Courant Institute of Mathematical Sciences, who drew him to the university. Regev was instrumental in creating the foundations of lattice cryptography and made the connection between quantum and lattices.

If you picture a two-dimensional lattice and pick a point, it's fairly intuitive for someone to find the closest point to it. But with a lattice with hundreds of dimensions, it’s very difficult, as you would have to try out many combinations to find the next closest point. The security of lattice cryptography is based on the believed hardness, even against attackers possessing a quantum computer, of such problems. Lyubashevsky’s two years in Israel, working closely with so many world-leading cryptographers, led to him thinking more and more about the possible practical applications of lattices, particularly how they could help reduce quantum risk.

The applications became even clearer after he left traditional academia, first heading to Inria (the French national research institute for digital science and technology) in 2010, and then to IBM Research in Zurich five years later. He moved for personal reasons, he said, but also because he had visited IBM a few times before and moving just made sense. At IBM, “it all started to become very practical very fast — in leaps and bounds, where lattice-based cryptography was really increasing in terms of potential utility,” Lyubashevsky said.

NIST and the lattice frenzy

A year after Lyubashevsky joined IBM, there was a global call from NIST to submit proposals for new algorithms that would be safe against future quantum computers. He focused all his attention on the problem. “This was now the real world, I realized that it was time to dot the i’s and cross the t's,” he said. “Otherwise, what was the point of all that theory? I just had to do it.”

The team, based in Zurich, proposed three schemes:

• CRYSTALS-Kyber public-key encryption,
• CRYSTALS-Dilithium digital signature algorithm, and
• FALCON digital signature algorithm.

Cryptographers from all over the world submitted dozens of cryptographic schemes for potential standardization, and in 2020, Read more about how IBM scientists helped develop NIST’s quantum-safe standards.NIST picked the winners. CRYSTALS-Kyber won for general encryption, used in cases like accessing secure websites, for example. This algorithm has small encryption keys and ciphertexts that two communicating parties can exchange easily. For digital signatures, NIST chose CRYSTALS-Dilithium, FALCON and SPHINCS+. Out of those, Lyubashevsky and his IBM colleague, Gregor Seiler, worked on developing the first three, while IBM researcher Ward Beullens contributed to SPHINCS+ before joining IBM.

The four algorithms will likely be published as formal standards this year and are believed to be extremely tough to break — now, or as many believe, pretty much ever. “To break the smallest version of Kyber with a computer today, you’d need the memory the size of a small moon,” said Michael Osborne, CTO of IBM’s quantum-safe security research. “That is just the incomprehensible amount of energy, and of compute resources.”

The news about the success of the IBM algorithms with NIST was encouraging, Lyubashevsky said, but he knew this was just the beginning. Now he and his colleagues had to get companies and organizations to switch to these new algorithms — the sooner the better.

In May 2022, the Biden administration issued a National Security Memorandum, outlining how US agencies will migrate to new, quantum-resistant algorithms. Shortly after, the Quantum Computing Cybersecurity Preparedness Act passed by Congress, mandated federal agencies to prepare an inventory of items for the transition to the new standards. Across the Atlantic, policymakers at the European Commission have been discussing recommendations for quantum-safe migration. A recent paper outlines the need for a new EU coordinated action plan to ensure companies across the continent adopt quantum-secured technologies as soon as possible.

While NIST finalizes the standards, Lyubashevsky continues to work on new algorithms. Although math puzzles are what led him to his professional passion, he’s no longer interested in solving them on paper. “Now, I want to help solve real world problems instead,” he said.