Who understands homomorphic encryption?

by philg

One of my favorite talks at an MIT computer science event last month was by Raluca Ada Popa, a proponent of keeping everything encrypted on servers even during computation. Then it doesn’t matter if the bad people (formerly “bad guys”) break in. How is that possible? Homomorphic encryption, developed about 15 years ago by Craig Gentry, plus hardware support from Intel.

According to Ada Popa, the performance hit from doing everything encrypted is only about 20 percent.

It is tough to know if this can truly protect garden-variety web services, in which the server holds most of the keys, e.g., the database password. I asked Professor ChatGPT:

Homomorphic encryption is a type of encryption that allows computations to be performed on encrypted data without decrypting it. This means that an HTTP server can process encrypted data without ever needing to know what the data actually is. However, there’s a bit of confusion in your question as you suggest the HTTP server has the decryption key.

The real power of homomorphic encryption lies in the fact that the server (like an HTTP server in your question) doesn’t need to have the decryption key at all. It’s the client who holds the key, encrypts the data, sends the encrypted data to the server, and the server performs the computations on the encrypted data. After performing operations, the server sends the encrypted result back to the client, who can then decrypt it using the decryption key.

This offers an unprecedented level of data security because even if the server was compromised, the data would remain safe since the attacker wouldn’t have access to the decryption key. It’s particularly useful in cloud computing, where sensitive data needs to be processed by third-party servers.

The decryption key should be kept safe and private, usually on the client side. If the HTTP server does hold the decryption key, it weakens the system’s security as it creates a single point of failure where both encrypted data and the decryption key can be potentially accessed by an attacker.

Could this prevent all of the credit card and mailing address breaches that we hear about? The credit card number is stored for one-click ordering, but can be decrypted only when the user is logged into an ecommerce site and is ready to enter his/her/zir/their password, which will serve as the key? Ditto for shipping address, but then that has to be transmitted to UPS or some other company, no?

Could it work for Google Drive? The big selling feature is that you can collaborate with 5 other authors if desired. How can that work if the document is encrypted with just one user’s key?

Who has thought about this and figured out whether homomorphic encryption is the silver bullet for defending practical applications?

Also from the event, the Followers of (Computer) Science stay safe in a crowded room for hours at a time by wearing masks:

27 thoughts on “Who understands homomorphic encryption?”

  1. It’s always been the silver bullet, except for the performance penalty. If that is truly down to 20%, it’s fantastic news!

  2. I haven’t thought about this, but it seems to me that philg’s objections are legitimate. Here is a paper that details how difficult it is to compare two integers:

    https://www.h2020prometheus.eu/sites/default/files/2019-11/Improved%20Secure%20Integer%20Comparison%20via%20Homomorphic%20Encryption.pdf

    Obviously, if a less-than operation on two encrypted integers returned a clear text result, one could decrypt an integer quickly using a binary search.

    So the paper claims that the result is encrypted and only accessible to the private key holder, i.e., not the server.

    It seems to me that the server can do fairly little if all the promises are kept.

    • The most obvious situation in which it works is if you want to use a server in the cloud with the same security that you’d enjoy using a desktop PC behind a firewall in your house. You ssh into that server and only then can computation be done (using the credentials you supplied when logging in). But this is not how consumers use Web sites.

    • Not sure. Could it be encryption based on some reversible mathematical construct that produces homomorphic image of client code and data on server? Doubt it. Probably Intel processor has set of all possible keys and can deduct what key is used by client, maybe by combination of client processor id and some encrypted code analysis and internally decrypts and re-encrypts data.
      Maybe combination of both. Doubt that it is completely hack-proof

  3. Password managers did that but it’s hard to do much besides a database. The lion kingdom still hasn’t migrated to an online password manager so its passwords can be monetized.

  4. It’s mostly seen as a way to do ad-tech targeting while provably protecting privacy. Meta hired a bunch of homomorphic encryption experts 3 years ago and Google open-sourced a FHE transpiler.

    In your example of the credit card, what matters is that the credit card holder authenticate the transaction. That happens when you use smartcard Chip-and-PIN, the PIN allows the chip to authenticate the transaction. Unfortunately US card issuers opted for the utterly unsafe Chip-and-Signature because PINs are associated with debit cards and they didn’t want lucrative credit-card interchange fees of 2-3% to be brought down to the same 0.5% level as debit cards. What’s worse is that there is still no widespread mechanism to authenticate credit card transactions over the Internet nor widespread support for smart card readers in computers. Apple Pay is not the answer, it merely generates a one-time virtual card number, there is no digital signature. Thus we are still in a situation where knowing card number, expiration, CVC and zip code suffices to perform a transaction. There is no need whatsoever to store the card on the server in the first place, other than recurring transactions and subscriptions, but if the server can do that without intervention from the user, the user is by definition not protected.

  5. Your photos show that few of the attendants wore masks. Has your opposition to mask mandates metastasized into an intolerant hatred of anyone who individually chooses to wear a mask while accepting and mixing with those who choose not to?

    Chill out. You’re on the verge of becoming that old spittle-flecked guy who shakes his fist yelling “THE SCIENCE, THE SCIENCE!!”

    • Thanks for the comment, I usually enjoy PhiGs quips but this seems to hit a wrong note. Most people still wearing masks have good reasons to do so, be they medical or psychological, or they’re doing so to support others that do.
      Or, just look at them as fashion accessories now. Do you make fun of everyone wearing a hat indoors because SCIENCE?

    • Sorry, I meant to give an example for the “good reasons”: I suffer from hay fever/pollen allergies and have worn a mask on a walk outside, and I like that this is now socially acceptable.

    • Unlike you, whose post is rather brutal, Phil brings up the mask topic in a light-hearted manner.

      He also does not try to micromanage other people’s speech …

    • Not everyone appreciates the Covidians of Maskachusetts/Academia-in-general as much as I do. I appreciate those who dedicate themselves to avoiding SARS-CoV-2 and yet voluntarily enter jammed rooms for hours at a time while relying on a basic mask for protection.

      But I appreciate the unmasked Covidians even more! These folks said that transmission had to be minimized by any means available, even after vaccinations became available, because any infection carried the risk of mutation. Acceptable means for minimizing transmission, for these Covidians, included at least the following: keeping K-12 schools closed, continuing to outlaw in-person work, interning the unvaccinated or at least confining them to their homes, forcing 2-year-olds to wear masks, forcing 5-year-olds to get injected with a non-FDA-approved medicine before appearing in public (City of Boston, for example), etc.

      SARS-CoV-2 is still with us and still has the potential to mutate into a more deadly form. Yet what do we see the majority of Covidians doing in 2023? Gathering en masse without even the masks that they continue to claim were effective and necessary for 2-year-olds to wear. It might make sense if they said “We were mistaken back in 2020 about masks and school closures and in 2021 about continued school closures and forced vaccination,” but I have never heard one of them say that.

    • I agree with most of your analysis, it’s just the repeated showing of individuals with masks that irks me. We don’t know why these people wear masks or what they’ve been through, maybe they lost parents or close ones and would like to think that a mask would have saved them. Not worse than any other religion in my opinion.
      But then again, I don’t live in Maskachusetts, and it’s quite possible that I would find the whole situation more amusing/annoying if I did!

    • CG: if their friends and relatives all died from Covid, what are they doing participating in an indoor mass gathering that is a proven way to spread Covid? (And, of course, I saw some of the masked Believers later in the day without masks in the same venue among the same crowd, e.g., drinking and eating.)

    • I agree with you on the matter. I also do not understand their behavior and I’m fine with you pointing that out. I just don’t see the point in more or less publicly posting pictures of people who would probably object to that in this context.
      But on the other hand that’s why I enjoy reading your blog, no point in only hearing arguments from people I always agree with!

    • I know people with severe auto-immune diseases and they do wear masks (N95), but they were afraid of the flu before as much as they are of COVID now, and they did avoid any gatherings in the flue season, and avoid any large gatherings now. I agree that wearing mask being socially acceptable is good for them now, sometimes I am sorry that some of us (me?), look at them as new Taliban, which they do not deserve.
      You can see some old frail people with mask and fear in their eyes, and I feel sorry for them, but these are not people we are talking about here.
      I also agree that it is “Not worse than any other religion ”, but there are many different religions, and I am afraid that many of the people who are made fun of here (mostly in very chilled out manner 🙂 do it more in Afghan Taliban or Saudi Wahhabi style, at least many of them had shown it during shutdowns, and I am afraid that they would do it again.

    • The reason why I follow and comment on this blog is that Philip does a great job at filtering out all the nonsense noise on complex issues. And he does it in a clear, elegant, and entertaining way without taking sides.

      If the media and the woke are 1/10 as upfront as Philip is, the country would not be as divided as it is. The USA and the world have far more dangerous issues to deal with than COVID or climate change or LGBTQ’ing.

      Twenty to 30 years from now, which of those 2 would you rather face, a) a generation immersed in masks, in LGBTQ teaching that cannot do basic math and logic, or b) a generation immersed in STEM and logical thinking? Which of those 2 generations will save the planet from melting or the real next supervirus that we might confront?

    • The Mask Believers’ behavior would have been less interesting if they’d kept their masks on when indoors and among the crowd. For example, if they’d walked a few steps with their food and drink and waited until they were outside before removing their masks. (It was very nice weather outside for both temp and lack of precipitation).

    • Judging from your comments I’ve just been lucky to live in a region with less aggressive mask zealots. I guess I shouldn’t judge you for being less tolerant than I am since I lack first hand experience with these people. Maybe they totally deserve being called out for their weird mask cultism.

    • Masks are partly just the visible symbol of the whole package (vax mandates, shutdowns). There were quarantines in the history, but people had been mostly forbidden to travel, I am not aware that people had been forbidden to leave their homes (house arrest) for months (during several years). There had been vax mandates in the history, especially for people who traveled, but not for whole population, for disease with relatively low mortality, and with completely new and experimental vaccine technology.

      Masks are relatively harmless for people who are not forced to wear it whole day. Forcing children to wear mask whole day is not only not harmless, but outright evil. There are still employees forced to wear mask whole day.

    • The Swedish MD/PhDs predicted that masks would be harmful by giving people a false sense of security, encouraging those who should stay home to leave their safe bunkers, for example, and causing humans to ignore physical distancing. I observed this behavior in Cambridge, MA and noted it in my blog back in the late spring of 2020.

      For the folks in the images above, if they do get Covid it will have been caused by their masks. Absent the masks, they would have cowered safely at home and watched on video.

  6. ChatGPT: “However, there’s a bit of confusion in your question as you suggest the HTTP server has the decryption key.”

    I see that the graphics cards get a little impatient and start lecturing. Does the above sentence cause “harm” in the reader, who might be discouraged from CS forever? What if a minority member reads this sentence? I think this is grounds for a lawsuit! Speech is violence!

  7. Looking at the dataflow picture on the right in the Intel link:

    “Secure data moved to cloud for compute, results sent to Enterprise for decryption.”

    So data is collected from the peasants, “securely” processed in “the cloud” and sent straight to Enterprise for decryption and data mining.

    It sounds like a great scheme to convince politicians to finally free health data (because secure enterprise encryption!) and then mine the data elsewhere, in other words, perform data laundering.

  8. Re: homomorphic encryption.

    Just a reminder: if you do HE, you cannot do conditional jumps this means you end up with a huge class of efficient algorithms (which rely on terminating computation early when the result is found) being excluded.

    Simple example: binary search is a sorted array. The only thing you can do with HE is to always read and do computation on the whole array (otherwise the process leaks information).

    For this reason HE will ALWAYS be niche tech. It’s orders of magnitude perfomance difference in real-life apps, don’t buy the 20% BS.

  9. What the f–k is homophobic encryption? Sounds like a non-starter in this day and age. (This also sounds difficult to debug)

Comments are closed.