HN Reader

As the article mentions, fully homomorphic encryption is insanely slow and inefficient. But I have to say that it is a relatively new field (the first FHE scheme was discovered in 2009), and that the field has immensely progressed over the last decade and a half.

The first FHE scheme required keys of several TB/PB, bootstrapping (an operation that is pivotal in FHE schemes, when too many multiplications are computed) would take thousands of hours. We are now down to keys of "only" 30 MB, and bootstrapping in less than 0.1 second.

Hopefully progress will continue and FHE will become more practical.

It doesn't actually say it anywhere, so: CRDT = Conflict-free replicated data type.

https://en.wikipedia.org/wiki/Conflict-free_replicated_data_...

FHE is indeed slow, but the progress since 2009 is truly remarkable. Bootstrapping speed alone improved by tens of millions of times, and tfhe-rs already demonstrates homomorphic AES-128. Real-time FHE for AI inference/training feels increasingly plausible.

> https://github.com/sharkbot1/tfhe-aes-128

> Now, however, the server can no longer understand the changes you send. If you want to see your friend’s latest changes, you’ll need to both be online at the same time.

What? No, the server sends you the changes you've not seen yet, you decrypt and merge them, and so you get the latest version of the document. Right?

The homomorphic encryption is a fascinating topic, but it's almost never an answer if you need anything resembling reasonable performance and/or reasonable bandwidth.

I've seen a paper that ingeniuously uses homomorphic encryption to implement arbitrary algorithmic computations, totally secret, by encoding a (custom-crafted) CPU together with RAM and then running "tick a clock" algorithm on them. And it works, so you can borrow some AWS huge instance and run you super-important calculations there — at 1 Hz. I am not kidding, it's literally 1 virtual CPU instruction per second. Well, if you are okay with such speed and costs, you either have very small data — at which point just run your computation locally, or you're really, really rich — at which point just buy your own goddamn hardware and, again, run it locally.

FHE is simply the wrong tool here. FHE is for a central server operating on data held/known by another. They want MPC -multiple parties jointly computing on distributed data- and that’s fairly more efficient.

I'm not sure I get the premise of the article. I know what a CRDT is and how homomorphic encryption works. But why do both parties have to be online at the same time to sync? They could send the updates asynchronously, store-and-forward style, and everything in flight is encrypted. Why does this need server that keeps state (which is kept in encrypted state and modified, as per the proposal)?

I like it! The slowness and inefficiency of homomorphic encryption is nicely complemented by the storage bloat of CRDTs.

Sorry for going off-topic, but kudos for UI/UX on your blog!

To name a few: Nice style (colors, font, style), "footnotes" visible on the margin, always on table of contents, interactivity and link previews on hover.

Nice. What's your tech stack?

> keep_self.select(&self.peer, &other.peer);

> Rather than if or match expressions, we use FheBool’s select method. It returns the first argument if the underlying FheBool value is true, or the second argument if the underlying value is false.

This wasn't super clear to me. I get the computation is performed on encrypted values, but how does ".select" actually work?

Is ".select" just evaluating to "keep_self*self.peer + keep_self*other.peer"?

Following the topic of FHE for quite some time and I am always hoping that we get some breakthroughs regarding speed. Seeing how this can be applied to CRDTs another awesome topic, is really cool, even if it still more theory than practice :-D

This is wild. I’ve seen CRDTs pop up in collaborative editors, but hadn’t considered them alongside FHE before. What kind of performance hit are you seeing in practice?

For the uninitiated:

"In the context of encryption, 'homomorphic' describes methods that enable computations on encrypted data without needing to decrypt it first.

Encrypt the diffs for the server and write the hash to a blockchain to manage the ordering. Boom, problem solved without HME.

Love the presentation.

“We introduced a new abstraction for no reason! Take a look!!”

Theoretically only one operation is sufficient: both NAND and NOR are universal gates, meaning all boolean operations are expressible in terms of only NANDs (or equivalently only NORs). The downside is that the expressions became longer.

Another cool use of FHE, allowing to browse wikipedia privately while still online: https://news.ycombinator.com/item?id=31668814

>Runtime performance is also — to put it lightly — lacking. I benchmarked the unencrypted and encrypted versions of the last write wins register on an M4 MacBook Pro. The unencrypted one averaged a merge time of 0.52 nanoseconds.The encrypted one? 1.06 seconds. That’s not a typo: the homomorphically encrypted merge is two billion times slower.

Ouch!

Don't use THFE-rs because Zama requires a commercial license for anything other than prototyping. Their license sucks.

Instead use openFHE (C++) or lattigo (golang) libraries which are both free to use commercially.