Posted in: Awards and Prizes, Cryptography, IBM 5 in 5, Security

Elegant, Disgusting Cryptography

“The prettiest thing I had ever seen” is not how IBM researcher Shai Halevi describes the beaches in Israel where he grew up. Or the sunset after a long day of hiking in Mitzpe Ramon desert. Rather, he saves these words to describe the first time he saw a cryptographic equation as an undergrad student.

“It was elegant math with real world applications, but it was also hairy and disgusting – I was instantly attracted,” said Halevi.

Growing up in an Israeli community known as a kibbutz, Halevi’s first job was in the banana fields of the kibbutz, but his life changed once he got his hands on a Commodore 128 computer.

“I thought I was the coolest kid in all of Israel.”

Halevi started programming on his Commodore and quickly realized that he wanted to become a computer scientist, applying complex math to address real problems. He then pursued an undergraduate degree in computer science in the Technion – Israel Institute of Technology, where he was introduced to the field of cryptography.

In the 1993 Halevi left Israel for MIT, which at the time he describes as “the mecca for modern cryptography,” eventually joining IBM Research in 1997 in Yorktown Heights, New York.

Finding Opportunity in FHE

While the first half of his crypto career was very “opportunistic,” jumping around from project to project, Halevi has spent the past decade on a technology known as fully homomorphic encryption (FHE), which doesn’t require a math degree to understand, despite the name.

Halevi explains, “Files are often encrypted in transit and at rest, but decrypted while in use. This regimen provides hackers repeated opportunities to steal unencrypted files. But FHE plugs those holes by keeping the data encrypted, while still allowing it to be manipulated even in its encrypted form, without ever having it exist in its vulnerable state.”

It’s sort of like the old days of developing photos, where the photographer would remove the film within a black bag to make sure it doesn’t get exposed. Similarly with FHE, you can manipulate the data that’s hidden inside of a ciphertext, even without having direct access to it.

FHE has been around for nearly a decade. In fact, back in 2015 and reported in Nature, scientists used homomorphic encryption to process DNA sequence data in the cloud, while keeping it encrypted. The point being, if such a data set were to get into the wild it could potentially be used for identity theft or worse.

“This is why I live to be a cryptographer. The concept is so elegant, yet it’s being applied to such a complex practical application,” smiles Halevi.

Until recently FHE was considered to be too slow for everyday usage due to the enormous computing power that it required, but thankfully, researchers like Halevi and fellow IBM scientist Craig Gentry, who was the first to show that FHE is possible, are overcoming these shortcomings through algorithmic advancements and hardware accelerations.

For one example, Halevi and Victor Shoup, at New York University, just wrote a paper that shows how to speed up certain common transformations on encrypted data. In their work, they demonstrated that linear transformations can be made to run 30-75 times faster than what we could do before.

“Computing on encrypted data is probably still 10,000 times slower than standard computation today where the data is in the clear, but this is already acceptable for some niche applications, and we are making steady progress on speeding it up,” says Halevi.

Guided by Coincidence

This past November, Halevi was awarded the SIGSAC Outstanding Innovation Award for outstanding and innovative technical contributions to the field of computer and communication security that have had lasting impact in furthering or understanding the theory or development of secure systems.

When looking back at his 20+ year career, he is thankful for his unique upbringing in a kibbutz and the many coincidences which steered him to the point he is at today, but he struggles to offer much help in terms of advice for young students.

“As an ice breaker at parties and events I often introduce myself by saying that the first couple of times I was on an airplane I never actually landed and people immediately think the worse.”

“Of course, the truth is less tragic — I was parachutist in the military. But I take the same approach to my career. Just jump and believe that something will intervene is the best advice I can give.”

For more on FHE and cryptography, check out IBM Research’s “5 in 5” predictions.

IBM Research editorial staff

with Shai Halevi, Cryptographer, IBM Research