* terms and conditions may apply. This post is an extension of a recent social-media-thread.
Fully Homomorphic Encryption (FHE) is really cool! LaurieWired’s recent thread on the topic has great pointers, check-it-out!
However, FHE isn’t the only answer to “encryption-in-use”. Other solutions exist that are efficient, employ well-established cryptography, and are deployable today!
There is just one small catch:
Why not FHE?#
FHE’s draw comes from its universality, it’s called fully homomorphic encryption for a reason. But performance concerns in practical use are real.
Laurie references the recent speedups; unfortunately most of the breakthroughs fail to address the complexity inherent to FHE, instead optimizing constant factors.
For example, Zama’s recent blog post1 cites impressive speed ups to 64-bit encrypted addition and multiplication, clocking in at 8.7 milliseconds and 32 milliseconds per operation, respectively.
That’s a real performance improvement and awesome to see! I recommend you check out the full post for all the juicy details.
But Zama’s experiments were on an AWS hpc7a.96xlarge instance, with 192 cores
and 768 GiB of memory,2 so let’s compare it with unencrypted add and mul
on Apple’s 2020 M1 chip.
An M1 addition is ~1 cycle, and multiplication is ~3 cycles.3 On a 3.2Ghz chip, a.k.a. 3.2 billion cycles per second, that’s 0.3125 nanoseconds or 0.0003125 microseconds or 0.0000003125 milliseconds per add. And 0.9375 nanoseconds or 0.0009375 nanoseconds or 0.0000009375 milliseconds per mul. This doesn’t take into account the M1’s multiple cores or the CPU’s internal parallelism.4
That’s a 27,840,000-34,133,133X gap between FHE and unencrypted computation, and the gap only grows more plain as the computation grows in complexity.5
However, many people much smarter than I are all in on FHE, and I’m still bullish on it long term.
If not FHE, then what?#
So what can we do, in practice, today?
The term fully homomorphic encryption begs the question, is there such a thing as partially or somewhat homomorphic encryption? Yes!
System design is all about compromise. By softening some of FHE’s guarantees (universal applicability, specific security properties) other approaches gain performance. While these schemes aren’t universal, they address a large percentage of the everyday computation many businesses are doing. And many only have a performance overhead of 5-30%!
Searchable Encryption#
An underrated approach is Searchable Encryption (SE). With SE, you can search, filter, and perform analytics on structured data. SE isn’t applicable to every possible computation over encrypted data, but some of the most common (sum, avg, count, min, max) have realistic solutions.6
From startups like Blind Insight7 to big companies like MongoDB’s Queryable Encryption,8 searchable encryption is about to hit production-ready.
Oblivious RAM#
“Oblivious” computation comes from relaxing the strict security guarantees of encryption.
While encryption guarantees complete secrecy, oblivious schemes only guarantee indistinguishability from “similar” computation patterns. Your data and operations aren’t completely private, but you still get a haze of deniability in return for performance gains.9 10 Oblivious RAM (ORAM) is an oblivious scheme built for general computation.11
There’s even brand new research that combines SE and ORAM techniques to enable semantic text search over encrypted data via a privacy-preserving Retrieval Augmented Generation (RAG) system.12 RAGs are a hot topic today due to their relevance in vector databases and LLMs. End-to-end encrypted vector database soon? 👀
Somewhat Homormorphic Encryption#
It turns out, Somewhat Homomorphic Encryption (SHE) is a real, formally defined, thing! Instead of restricting the type of encryption, SHE sets a maximum on the complexity of the possible computations over encrypted data.
By setting a upper bound at initialization, cryptographic system designers can make assumptions that allow for optimizations to the total system’s performance complexity.
SHE is still an emerging area of research, gaining popularity in recent years, with regular exciting theoretical breakthroughs.13
Conclusion#
I didn’t even scratch the surface on the nifty tricks and applications of these schemes. And there are other, adjacent, techniques I didn’t have time to mention.14 If you’re interested in any of the research I’ve mentioned here and would like pointers to additional papers or projects, send me an email.
https://www.zama.ai/post/bootstrapping-tfhe-ciphertexts-in-less-than-one-millisecond ↩︎
Modern CPU’s can actually progress on more than one instruction per cycle. If you, like me until an embarrassing age, didn’t know that, check out the performance-aware programming series for more. ↩︎
In particular, the decision to invest heavily in custom hardware is a fun one to overanalyze. Although insanely cool, creating your own silicon is not cheap. To me, the armchair cryptographer, it reads as a lack of confidence that the theoretical complexity of FHE will meaningly improve in the near future. So money is hedging its bets by investing R&D elsewhere. ↩︎
I recommend reading this excellent recent survey and following the citations and follow-up work of whatever interests you. ↩︎
https://www.mongodb.com/docs/manual/core/queryable-encryption/ ↩︎
Multi-party computation, linearly homomorphic encryption, homomorphic secret sharing and private information retrieval first come to mind as techniques with dense histories, that have potential applications to encryption-in-use schemes. ↩︎
