IBM's homomorphic encryption accelerated to run 75 times faster

It lets you work on encrypted data without taking it to plaintext and back again


IBM has rewritten its C++ homomorphic encryption library and claims it now goes up to 75 times faster.

Homomorphic encryption is a technique used to operate on encrypted data without decrypting it. This would make sensitive operations much more secure: for example, companies could encrypt their cloud-hosted databases, and work on them without converting records back to plaintext.

IBM has worked on homomorphic encryption for some time, and released the first version of its HElib C++ library three years ago, but as we reported in 2016, the technology has always suffered huge performance penalties.

IBM's first attempts at homomorphic encryption, under the hand of its inventor Craig Gentry, ran “100 trillion times” slower than plaintext operations. It later accelerated by a factor of two million times, running on a 16-core server.

UIltron

Microsoft researchers smash homomorphic encryption speed barrier

READ MORE

Hence Big Blue's ongoing work on HElib. Released at GitHub, the latest version gets its performance kick from a “re-implementation of homomorphic linear transformations”, making it between 15 and 75 times faster.

In this paper at the International Association for Cryptologic Research, IBM's Shai Halevi and Victor Shoup (the latter also with New York University) explain how they improved speed.

“In the linear transformation algorithms currently implemented in HElib, the bulk of the time is spent moving data among the slots in the encrypted vector,” they wrote.

This is done with “special automorphisms” (a mathematical operation that maps an object to itself), and the computational cost comes from how many times the automorphisms have to loop around.

“The main cost of applying such an automorphism to a ciphertext is actually that of “key switching”: after applying the automorphism to each ring element in the ciphertext (which is actually a very cheap operation), we end up with an encryption relative to the “wrong” secret key; by using data in the public key specific to this particular automorphism — a so-called “key switching matrix” — we can convert the ciphertext back to one that is an encryption relative to the “right” secret key” the paper said.

“So the main goals in improving performance are to reduce the number of automorphisms, and to reduce the cost of each automorphism.”

In more accessible English, the new library implements a new strategy for calculating those automorphisms (achieving between 15 and 20 times speedup); the researchers refactored many of the necessary computations; and some of the calculations are shifted out of the library's main loop (getting a 6-8 times speedup).

The way public keys are constructed for homomorphic encryption is also expensive because of the aforementioned key-switching matrix. Each matrix adds several megabytes to the public key, and in HElib there could be several hundred such matrices in a public key. The researchers say for common operations, they were able to cut the size of the matrix by 33-50 per cent.

HElib is still a research-level project. As stated on the GitHub page: “At its present state, this library is mostly meant for researchers working on HE and its uses. Also currently it is fairly low-level, and is best thought of as 'assembly language for HE'. That is, it provides low-level routines (set, add, multiply, shift, etc.), with as much access to optimisations as we can give. Hopefully in time we will be able to provide higher-level routines.” ®

Similar topics

Broader topics

Narrower topics


Other stories you might like

  • AI tool finds hundreds of genes related to human motor neuron disease

    Breakthrough could lead to development of drugs to target illness

    A machine-learning algorithm has helped scientists find 690 human genes associated with a higher risk of developing motor neuron disease, according to research published in Cell this week.

    Neuronal cells in the central nervous system and brain break down and die in people with motor neuron disease, like amyotrophic lateral sclerosis (ALS) more commonly known as Lou Gehrig's disease, named after the baseball player who developed it. They lose control over their bodies, and as the disease progresses patients become completely paralyzed. There is currently no verified cure for ALS.

    Motor neuron disease typically affects people in old age and its causes are unknown. Johnathan Cooper-Knock, a clinical lecturer at the University of Sheffield in England and leader of Project MinE, an ambitious effort to perform whole genome sequencing of ALS, believes that understanding how genes affect cellular function could help scientists develop new drugs to treat the disease.

    Continue reading
  • Need to prioritize security bug patches? Don't forget to scan Twitter as well as use CVSS scores

    Exploit, vulnerability discussion online can offer useful signals

    Organizations looking to minimize exposure to exploitable software should scan Twitter for mentions of security bugs as well as use the Common Vulnerability Scoring System or CVSS, Kenna Security argues.

    Better still is prioritizing the repair of vulnerabilities for which exploit code is available, if that information is known.

    CVSS is a framework for rating the severity of software vulnerabilities (identified using CVE, or Common Vulnerability Enumeration, numbers), on a scale from 1 (least severe) to 10 (most severe). It's overseen by First.org, a US-based, non-profit computer security organization.

    Continue reading
  • Sniff those Ukrainian emails a little more carefully, advises Uncle Sam in wake of Belarusian digital vandalism

    NotPetya started over there, don't forget

    US companies should be on the lookout for security nasties from Ukrainian partners following the digital graffiti and malware attack launched against Ukraine by Belarus, the CISA has warned.

    In a statement issued on Tuesday, the Cybersecurity and Infrastructure Security Agency said it "strongly urges leaders and network defenders to be on alert for malicious cyber activity," having issued a checklist [PDF] of recommended actions to take.

    "If working with Ukrainian organizations, take extra care to monitor, inspect, and isolate traffic from those organizations; closely review access controls for that traffic," added CISA, which also advised reviewing backups and disaster recovery drills.

    Continue reading

Biting the hand that feeds IT © 1998–2022