Homomorphically Encrypting CRDTs

Summary

Here’s a problem with local-first software. You want to work on a document together with a friend who lives far away from you. That sounds like local-first’s bread and butter: store the document as a CRDT, then use some sort of sync server to merge updates and relay them between you and your friend. But there’s a catch: the contents of that document are secret. So secret, in fact, that you don’t even want the app developer to know what they are. One way to solve this is end-to-end encryption. You and your friend agree on a secret key, known only to each other. You each use that key to encrypt your changes before sending them, decrypt them upon receipt, and no one in the middle is able to listen in. Because the document is a CRDT, you can each still get the latest document without the sync server merging the updates. That is indeed a solution, and modern browser APIs make it fairly simple to implement a basic version of it. Excalidraw’s writeup of their implementation Excalidraw Blog | End-to-End Encryption in the Browser Excalidraw introduces browser-based end-to-end encryption using Web Cryptography APIs for secure, private drawing storage. plus.excalidraw.com/blog/end-to-end-encryption is only about 750 words — including code samples!1 Unfortunately, we’ve introduced a new problem. You and your friend live far away from each other, so you tend to work while they’re sleeping and vice versa. That was fine when the sync server could merge your changes and send you the latest document when you opened it. 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. Enter homomorphic encryption: a special form of encryption that allows a computer to run programs on encrypted data without decrypting it. Using a homomorphically encrypted CRDT, a sync server could merge your friend’s and your changes into one document without ever knowing what the document contains.2...