I recently attended a great series of talks, the Privacy Enhancing Technologies in Practice (PETiP) series that was put on by the Isaac Newton Institute of the University of Cambridge. I was hoping to learn more about how some of the cutting-edge security technologies work, but I got something better: Instead of covering the technical details of different technologies, the talks were by CEOs of companies that are trying to market those technologies and covered the challenges that they were having with getting their technologies to move past the pilot or proof-of-concept stage. They offered great points of view that I had never encountered before. One of the more interesting talks was about fully homomorphic encryption (FHE).
What I heard about FHE sounded interesting and made me want to learn more about it. The PETiP discussion noted that performance issues are limiting its use and how hard it is to get a new encryption technology approved by government standards organizations. There’s essentially only one standard for encryption that matters, and that’s the US government’s FIPS 140-3, Security Requirements for Cryptographic Modules, and there doesn’t seem to be any chance that any form of FHE will be approved for use under FIPS 140-3 anytime soon.
It’s hard to get the US government to accept new forms of encryption, so I thought that that’s something that I probably couldn't do anything about, whereas understanding the performance imitations of FHE was something that was probably much more realistic. So I decided to not look into what’s required to register as a government lobbyist and started searching for information about FHE instead.
I quickly learned that there’s an effort underway to write a standard that specifies forms of FHE. This is the Homomorphic Encryption Standardization project. This isn’t run through an established standards organization such as the IETF, the IEEE, OASIS, etc. Instead, it’s run by a group of vendors that have an interest in getting their technology accepted. The group is having meetings, running workshops, and creating a draft standard. It’s not clear how useful the standard that they’ll eventually produce is going to be.
What is homomorphic encryption?
Homomorphic encryption lets you do calculations on encrypted data without having to decrypt it first. The common RSA encryption actually lets you do that. With RSA encryption, it’s easy to change an RSA ciphertext C = Encryption(X) into a different C' that will decrypt to 2X, 3X, 100X, or any other multiple of X. Real protocols don’t work like this, but if the encrypted value represented how much money is to be transferred from one bank to another bank, it could be possible to change an order to transfer $1 million into an order to transfer $100 million, for example, by taking advantage of that property.
Cryptographers call this property ciphertext malleability, and it’s generally a bad thing. RSA is homomorphic for multiplication, but not addition. There’s no way to easily change C = Encryption(X) into some C' that will decrypt to X + 10, for example, using RSA encryption.
There’s also a type of encryption that’s homomorphic for addition. That’s Pallier encryption, a technology that is used in some e-voting systems today. It lets you count how many votes were cast for a particular candidate without having to decrypt each individual vote. You can even try a demo of this here.
While RSA encryption is homomorphic for multiplication and Pallier encryption is homomorphic for addition, what we really want is a way to do encryption that’s homomorphic for both operations. Once you have that, you can build any calculation that you need from those operations. And that’s exactly what FHE lets you do.
The leading approaches to FHE don’t let you do this with addition and multiplication. Instead, they let you build operations from logical operations such as AND, OR, XOR, etc. That’s surprisingly complicated for useful operations. If you want to add two 32-bit integers, you can do this with a 32-bit adder circuit, which is fairy complicated. And because we have to implement each of these gates with a complex calculation, that’s not easy to do, and that has severely limited the use of the technology.
Kicking the tires
To get an idea of exactly how severe the performance limitations of FHE are, I downloaded and tested the TFHE library, an open-source implementation of an optimized version of the GSW encryption system. What I learned was a bit surprising.
Encryption and decryption were fairly fast, but implementing operations on encrypted data was slow. Like molasses in January in Vermont slow.
On my laptop, each gate took about 15ms (1,000ms makes 1 second). That may not sound too bad, but when you look at what you’d need to do to do a homomorphic addition of two 32-bit values, it starts looking bad. Even with an infinite number of cores to throw at this problem, the longest path through a 32-bit adder circuit limits how fast it can operate. This is just like the propagation delay that limits how fast electronic circuits can switch. For an n-bit adder, the propagation delay is about 2n. For an n-bit multiplier, the propagation delay is about 6n. So for doing a homomorphic addition of two 32-bit values, I might be able to optimize things down to about 1 second, and for the multiplication of two 32-bit values, I might be able to optimize things down to about 3 seconds. There are only 86,400 seconds in a day, so it doesn’t look like I could do many useful homomorphic operations per day on that laptop.
Putting FHE into practice
So I now understand the frustration of the guys in the PETiP talks who are having trouble getting people to adopt their technology. With current technology, FHE might be suitable for some specialized calculations that can be done quickly and efficiently, but for general-purpose calculations, such as you might want to use in constructing a database query, for example, it doesn’t look like it’s practical yet.
This is still an active area of research, so I wouldn’t be surprised if it eventually becomes practical. But it’s probably too soon to get excited about the marketing messages that FHE vendors are producing these days, unless they give acceptable numbers for the performance of nonspecialized calculations. Once we see that, we’ll know that FHE is truly useful.
No Security is a monthly column.
Keep learning
Get up to speed on unstructured data security with TechBeacon's Guide. Plus: Get the Forrester Wave for Unstructured Data Security Flatforms, Q2 2021.
Join this discussion about how to break the Ground Hog Day repetition with better data management capabilities.
Learn how to accelerate your analytics securely into the cloud in this Webinar.
Find out more about cloud security and privacy, and selecting the right encryption and key management in TechBeacon's Guide.
Learn to appreciate the art of data protection and go behind the privacy shield in this Webinar.
Dive into the new laws with TechBeacon's guide to GDPR and CCPA.
