This post originally appeared on NYU Abu Dhabi’s Salaam blog.
By Brian Kappler
The “cloud computing” we hear so much about is cheap and efficient, but it’s not completely secure. Encrypted data — payroll information, for example, or hospital records — can easily be stored on servers run by Google, Amazon, Oracle, or another company. But only non-encrypted data can be processed “in the cloud” and that creates an obvious security risk in our era of hacks, exploits, and cybercrime.
Now, however, NYU Abu Dhabi researchers have taken a long step toward solving this problem, in HEROIC fashion. The acronym stands for Homomorphically EncRypted One Instruction Computation. In simpler terms, it’s computer architecture that permits the processing of encrypted data.
Nektarios Tsoutsos, Ph.D. candidate in computer science, has published a paper on HEROIC, along with his advisor Michail Maniatakos, the director of NYUAD’s Modern Microprocessor Architecture Lab and assistant professor of electrical and computer engineering. Their research is connected with TwinLab, a $2.57 million project on trustworthy computer hardware supported by GlobalFoundries and the NYUAD Institute.
More recently Tsoutsos, Maniatakos, and postdoctoral associate Oleg Mazonka have developed a newer version of HEROIC, known (non-acronymically) as Cryptoleq.
Tsoutsos explained the purpose of both systems this way: “Let’s say I have a proprietary algorithm, and I want to apply it to a large database. The job is much too big for my computer, so I’ve got to outsource this to somebody in the cloud, Amazon for example. But I don’t want that company to have access to the data — let’s say it’s a fingerprint or DNA database, or medical records, something that has to be confidential. I’ve got to be able to outsource to the cloud, but not let the cloud service provider figure out what I’m doing.”
Enter homomorphic (“same-shape”) encryption. “If I want to use an application it is possible to first encrypt the data, and then apply an algorithm as a sequence of mathematical operations, and then reverse the encryption process — and I can get the correct result and the remote service can’t read the data,” Tsoutsos explained. None of this is simple – it’s based on algebra involving “nested abstractions”, he said — but it can be done, so that attackers can be thwarted.
One form of this process, partial homomorphic encryption (PHE), has been known for about 35 years, Tsoutsos said, while fully homomorphic encryption (FHE) became possible as recently as 2009. A key difference is that PHE works only for addition or multiplication, while FHE is versatile and “because of computer science tricks we can use sequences of additions and multiplications to execute computer programs,” Tsoutsos added.
But there’s a drawback. FHE remains painfully, impractically slow. It’s a little faster now but when it was first discovered, a simple Google search with FHE would have needed fully one thousand years, Tsoutsos said. “So, we don’t have computers today to take advantage of FHE. Fully homomorphic encryption is the most powerful tool cryptography can give us, it solves all the problems, but it’s too slow.”
Here, HEROIC and Cryptoleq come to the rescue. “We’re trying to simulate FHE, using PHE,” Tsoutsos said. “On its own it cannot do as much as FHE, so we gave HEROIC a little help: additional memory, look-up tables, and in Cryptoleq an ‘obfuscated module’ that users can’t look inside. With these tricks that we play, it’s much faster than FHE, so it is practical.”
Of the two systems, HEROIC is faster, but demands more memory; Cryptoleq is slower but needs less memory. Tsoutsos and Maniatakos have patented HEROIC in the US, with the patent assigned to NYU, and Cryptoleq – computer language, compiler, and execution engine — is available as open source software. Once this work is complete, Tsoutsos added, he will have the “foundation for my Ph.D. thesis.”