{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreihtfdadjn2xu66hagxztvxmmvegzxxikkt2abalurwemt3w3dx64y",
    "uri": "at://did:plc:vrrdgcidwpvn4omvn7uuufoo/app.bsky.feed.post/3lrsmu7g4es2g"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreih3jbkd2s4b6utbecqneerucfgdvncbrecyr3idu3qs63xj3knsvm"
    },
    "mimeType": "image/png",
    "size": 39004
  },
  "description": "Homomorphic encryption allows a computer to run programs on encrypted data. Learn how homomorphic encryption works through interactive examples, build a homomorphically encrypted CRDT and see whether it has promise for local-first software.",
  "path": "/words/homomorphically-encrypted-crdts/",
  "publishedAt": "2025-06-17T00:00:00Z",
  "site": "at://did:plc:vrrdgcidwpvn4omvn7uuufoo/site.standard.publication/3mmyfl3pxzi2a",
  "tags": [
    "crdts",
    "localfirst"
  ],
  "textContent": "Here's a problem with local-first software.\n\nYou want to work on a document together with a friend who lives far away from you.\nThat 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.\n\nBut there's a catch: the contents of that document are secret.\nSo secret, in fact, that you don't even want the app developer to know what they are.\n\nOne way to solve this is end-to-end encryption.\nYou and your friend agree on a secret key, known only to each other.\nYou 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.\nBecause the document is a CRDT, you can each still get the latest document without the sync server merging the updates.\n\nThat 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 is only about 750 words — including code samples!\n\nUnfortunately, we've introduced a new problem.\n\nYou and your friend live far away from each other, so you tend to work while they're sleeping and vice versa.\nThat was fine when the sync server could merge your changes and send you the latest document when you opened it.\n\nNow, however, the server can no longer understand the changes you send.\nWe're faced with a tradeoff:\n\nRequire both you and your friend to be online at the same time.\n\nHave the sync server merely relay updates between you and your friend without merging.\nAlthough this allows you to work asynchronously, it prevents the server from compressing any of the updates.\nIf you or your friend are offline for an extended period of time, you might need to download a ton of uncompressed data when you return.\n\nEnter homomorphic encryption: a special form of encryption that allows a computer to run programs on encrypted data without decrypting it.\nUsing 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.\n\nIn this article, we'll explore how homomorphic encryption works and build a homomorphically encrypted last write wins register CRDT.\nWe'll also learn about some fundamental limitations of homomorphic encryption, and how they affect local-first software specifically.\n\nI try to assume as little knowledge as possible about both encryption and CRDTs.\nIf you want to brush up before continuing on, my Interactive Intro to CRDTs and Jeremy Kun's A High-Level Technical Overview of Fully Homomorphic Encryption are good places to start.\n\n(Obligatory disclaimer: I am not a cryptographer!\nWhile I'm reasonably confident that my code and advice here is generally sound, cryptography is a field in which subtle bugs and exploits can look fine to the untrained eye.\nBefore using anything here in an environment you'd describe with the word \"production\", consult someone who works on this professionally.)\n\nHomomorphic Hello World\n\nFirst, let's look at a small code sample that uses homomorphic encryption.\n\nWriting the encryption code itself from scratch would take much more code than can fit in this article.\nInstead, we'll use THFE-rs, a homomorphic encryption library written in Rust.\n\nThe flow goes something like this:\n\nA client generates a key pair consisting of a client key and a server key.\n\nThe client encrypts their data using the client key and sends both the encrypted data and server key to the server.\n\nThe server uses the server key to perform some computation on the encrypted data and sends the result back to the client.\n\nThe client decrypts the result with the client key.\n\nHere's what this looks like in code.\nWe'll take two numbers — clear_a and clear_b — and add them together.\nRather than actually sending anything over a network, we'll just use a function called server_compute to play the part of the server.\n\nGet the keys, encrypt two numbers, add their ciphertexts together, decrypt the result.\nNot too bad, right?\n\nThe simplicity is deceptive!\nRust supports operator overloading, so when we run cipher_a + cipher_b and both of the operands are FheUint32, what's really happening is that TFHE-rs runs a bunch of cryptography code.\n\nBefore we build our homomorphically encrypted CRDT, let's peek at what TFHE-rs is doing under the hood.\n\nUnder the Hood\n\nTo start, what does it even mean to \"run programs on encrypted data\"?\n\nIn short, it means you can use encrypted data in certain math operations, and when you decrypt the data you get the result you would have gotten if you had performed the same operations with the plaintext data.\nThat requires an encryption scheme in which at least one of the following is true (I'll use the notation E(a) to indicate the encrypted version of the plaintext a):\n\nE(a) + E(b) = E(a + b): adding the encrypted values of the plaintext numbers a and b results in the encrypted sum of the plaintext sum a + b.\n\nE(a) × E(b) = E(a × b): multiplying the encrypted values of the plaintext numbers a and b results in the encrypted product of the plaintext product a × b.\n\nWhat this means is that if you add or multiply two homomorphically encrypted values, then decrypt them, you get the respective sum or product of the original plaintext values.\n\nHere's an extremely simple example that you should absolutely never use anywhere.\nFirst, let's pick a number as a key.\nWe \"encrypt\" numbers by multiplying them by the key, and \"decrypt\" numbers by dividing them.\n\nLet's say our key is 7 and our \"plaintext\" numbers are 5 and 6.\nWe can multiply each number by our key 6 to get \"encrypted\" numbers of 35 and 42.\nEven if someone has access to our encrypted numbers, they can't figure out what our original plaintext numbers were without the key.\n\nWhat they can do is add the encrypted numbers together.\nIf they give us back the sum, 77, we can divide it by our key 7 to get 11 — the same result we'd get by directly adding our original numbers.\nTry it out by changing the numbers in the playground below:\n\nBecause it satisfies the first criterion — E(a) + E(b) = E(a + b) — we can say that our toy encryption scheme is homomorphic over addition.\nEncryption that supports only one operation is called partially homomorphic encryption.\nAll in all, there are four different levels:\n\nPartially homomorphic encryption allows only one of the two operations: either addition or multiplication, but not both.\n\nSomewhat homomorphic encryption and leveled homomorphic encryption allow both operations, but limit the amount of times they can be used.\n\nFully homomorphic encryption allows an unlimited amount of both operations.\n\nPartially homomorphic encryption is relatively easy to implement, but has limited uses.\nThe word \"relatively\" is doing some heavy lifting here — you or I probably couldn't come up with a partially homomorphic encryption scheme — but it's simple enough that there are algorithms such as RSA that are accidentally homomorphic over one operation.\n\nSupporting more than one operation is significantly more useful, but each calculation adds \"noise\" to the result.\nToo much noise makes it impossible to decrypt.\nThere are two broad strategies for reducing noise: limiting the number or \"depth\" of operations (somewhat and leveled homomorphic encryption), and \"bootstrapping\", which reduces the level of noise mid-computation (fully homomorphic encryption).\n\nWhy does it matter whether we can perform both addition and multiplication?\n\nWhen we talk about doing math on encrypted data, we're really talking about the underlying bits: the 1s and 0s that make it up.\nTo add and multiply the bits, we use the logical operations \"exclusive or\" (XOR) and \"binary and\" (AND), respectively.\n\nClick on the switches in the playground below to toggle between 1 and 0.\nYou can see that the AND output is the product of its two inputs, and the XOR output is roughly the sum of its two inputs.\n\nThis is called a Boolean circuit — essentially, a function that takes 1s and 0s as input and returns 1s and 0s as output.\nIn this context, the logical operations are called logic gates.\n\nWe can create new logic gates by combining ones we have.\nHere's how to create \"inclusive or\" (OR) and inverter (NOT) operations using only XOR and AND.\n\nOnce we've built a gate, we can then use it to build yet other gates.\nHere's how to make an \"exclusive nor\" (XNOR) using XOR and our newly-constructed NOT gate:\n\nIt turns out that combining just XOR and AND like this is enough to perform any computation!\nAll other logical operations can be created by combining only XOR and AND, which means that adding and multiplying the encrypted data is sufficient to simulate arbitrary Boolean logic.\n\nHere's a circuit that implements the \"greater than\" operator on two-bit numbers (between 0 and 3).\nUsing only AND, XOR and the other gates we've built with them, it returns 1 if the first number is greater than the second, and 0 otherwise.\n\nType in the square boxes at the top to enter the input numbers.\nThe two rounded boxes below each square input box are the binary representation of that number.\n\nDon't forget this circuit — it'll come in handy later!\n\nIn these examples, we've been looking at circuits that use plaintext 1s and 0s as their inputs and outputs.\nWith homomorphic encryption, the circuits operate on encrypted data.\nPerforming an AND on two encrypted bits returns another encrypted bit — and we can't find out what it is unless we have the key.\n\nSo that's how homomorphic encryption works in a nutshell.\nYou express your program as a Boolean circuit, and then simulate the circuit using the encrypted data as input.\nThe output of the circuit will be the encrypted result, which the client can then decrypt.\n\nCrucially, none of this reveals any sort of relationship between the plaintext values.\nFor example, even if E(a) + E(b) were positive, E(a + b) might be negative.\nAdding and multiplying ciphertext corresponds to the same operations on the underlying plaintext, but there's no correlation between any of the ciphertext results and the underlying plaintext results — you need to decrypt the result to figure out what happened.\n\nA Fully Homomorphic CRDT\n\nNow that we have a high level understanding of homomorphic encryption, let's build a homomorphically-encrypted last write wins register.\n\nA last write wins register holds a single value and two additional bits of metadata: a \"clock\" that gets incremented by one whenever the value is set, and an ID indicating the peer who last wrote to it.\nLike all CRDTs, it also has a merge function that describes how it should be combined with another of the same type.\n\nThe last write wins register merge algorithm works like this:\n\nIf the received clock is less than the local clock, the register doesn't change its state.\n\nIf the received clock is greater than the local clock, the register overwrites its local value with the received value. It also stores the received clock and peer ID.\n\nTies are broken by comparing the local peer ID to the peer ID in the received state.\n\nHere's a playground in which you can see how this algorithm works:\n\nTry playing around with the latency and the network toggle.\nSee how updates are accepted only if the sending peer's clock is higher than the receiving peer's clock. If the clocks are tied, the update from the right peer will win out, since the peer ID bob is lexicographically greater than alice.\n\nOkay, let's look at some code.\nFirst, here's what an unencrypted last write wins register might look like in Rust:\n\nIt has a peer ID, a clock and a value.\nTo merge with another register, it just takes the peer ID, clock and value from the register with the higher clock.\nIn case of a tie, it uses the peer ID as a tiebreaker.\n\nBecause Rust is a low-level language, we need separate functions to convert types such as strings into the raw bytes to store as the value.\nWe also store the value in an array with a statically-known size — although as we'll see, that's less of a Rust limitation than it is a fundamental constraint of homomorphic encryption.\n\nHere's the skeleton of an EncryptedRegister struct:\n\nPretty similar to the unencrypted Register struct!\nFheUint64 has replaced u64, and value is now an array of FheUint8 rather than u8.\nThese are TFHE-rs types that encrypt the corresponding Rust types.\nBut other than that, the struct is the same.\n\nThe implementation has two new methods:\n\nencrypt, which takes a normal Register and a client key, encrypts all the fields and returns an EncryptedRegister.\n\ndecrypt, which takes a client key, decrypts all the fields and returns a normal Register.\n\nWe've also omitted the set and set_string methods.\nSince EncryptedRegister runs on the server, the value will never be set manually.\nThe only thing it needs to do is merge an incoming register with the register it has in memory.\n\nOkay, so what does the merge method look like?\n\nAs we saw before, TFHE-rs overloads operators like + to make working with encrypted values more convenient.\nFor operators that don't support overloading such as <, TFHE-rs has methods like gt.\n\nGiven that, you might think we could write the merge method like this:\n\nThis will definitely not work!\n\nRemember that we can't retrieve any information by operating on the encrypted data — including information about the results of intermediate steps.\n\nTo more clearly show the problem with this strategy, we can add some logging:\n\nAlthough we still couldn't decrypt the encrypted data, this (fake) implementation would reveal the result of the merge!\nWe'd know which branches our code took, and therefore learn which decrypted clock was higher and which encrypted data was written to the register.\n\nInstead, our merge function must eagerly evaluate all branches in our code.\nIt also means that all loops must run for a statically-known number of iterations.\nMore generally, our code must always execute as though operating on the worst case input, because altering behavior based on the input would leak information about it.\n\nHere's the real code for our merge function:\n\nSuperficially, it looks fairly similar, but there are a couple of important differences.\nLet's take it line by line.\n\nFirst, we determine whether the local clock is higher than the other clock:\n\nIf we think back to the logic gates, we can imagine what's going on under the hood here, right?\nWe built this exact circuit!\nOurs only operated on two-bit numbers, but the idea was the same: accept two numbers and return a 0 or 1 indicating whether the first number is higher than the second.\n\n(In our circuit, the result was a plaintext 0 or 1 — but remember, homomorphic encryption operates with encrypted values!\nThe gt method actually returns an FheBool: an encrypted bool which indicates whether the local clock is higher than the other one.)\n\nIf we had the client key, we could decrypt that variable and find out its true value.\nWe can't do that, but we can still combine it with other encrypted values to write our merge algorithm.\n\nHere are the conditions to break a tie between the clocks:\n\nTwo more FheBools indicating whether the clocks are equal and if the local peer ID is higher.\n\nNext, we combine them:\n\nThis combines all those FheBools to determine whether to keep the local data or overwrite it with the merged data.\n\nThose | and & operators are bitwise AND and bitwise OR, which work exactly like the AND and OR logic gates we made earlier.\nThey're similar to the logical AND and OR we're used to — && and ||, but with one big difference: bitwise operators are eager.\nWhereas logical AND and OR might skip the second expression depending on the first, bitwise operators will always evaluate both sides.\n\nNow that we've determined the register values to keep — even if we can't tell which ones — we need to write the data to the register.\nHere's the secret sauce:\n\nRather than if or match expressions, we use FheBool's select method.\nIt returns the first argument if the underlying FheBool value is true, or the second argument if the underlying value is false.\n\nThis is important: the return value is different from both arguments.\nWhile decrypting the return value would reveal the same plaintext as one of the arguments, in ciphertext all three are distinct.\nThis means that we can't tell which values we've set on the register by the end of the merge.\n\nWhen the merge is done, every piece of ciphertext has changed — the peer ID, the clock and the register value.\nThe plaintext values might have updated (or might not have!) but there's no way to tell by looking at the ciphertext.\n\nProblem solved, right?\nWe can now have the server merge our CRDT without knowing what it contains?\nWeeeellllllll…\n\nFundamental Limitations\n\nHomomorphic encryption has constraints that sharply limit its effectiveness with regard to local-first software.\n\nFor starters: encryption keys.\nIn both the simple adding example and the last-write wins register, we generated a key that would be passed to the server.\nThat only needs to happen once, but the difference between the size of our key and the size of our data can be surprising.\n\nOur register took up only 32 bytes of data — 8 bytes each for the peer and clock, and 16 bytes for the value.\nMeanwhile, TFHE-rs generated a 123 megabyte server key.\nWe can compress the key down to about 27 megabytes, but still: that's almost 850,000 times more key than data!\n\nThe payload here is particularly small, but a disparity of that size isn't unheard of.\nIn his overview of fully homomorphic encryption, Jeremy Kun cites examples in which ciphertexts of dozens or hundreds of kilobytes require keys on the order of gigabytes.\n\nRuntime performance is also — to put it lightly — lacking.\nI benchmarked the unencrypted and encrypted versions of the last write wins register on an M4 MacBook Pro.\nThe unencrypted one averaged a merge time of 0.52 nanoseconds.\n\nThe encrypted one?\n1.06 seconds.\nThat's not a typo: the homomorphically encrypted merge is two billion times slower.\n\nNot great!\n\nThat's not all.\nWe said before that our code must execute as though operating on the worst case input.\nEven if the performance issues improve by many orders of magnitude, the \"worst case\" requirement will still impose constraints on the CRDT algorithm itself.\n\nConsider a fully homomorphically encrypted last-write wins map CRDT.\nMost maps store keys sparsely, so the map only grows in size as keys are added.\n\nHere's a playground that simulates encrypting a sparse map.\nWhen you modify the plaintext map on the left, the encrypted map on the right updates.\nCan you see a security issue?\n\nImagine you only had access to the map on the right.\nYou could still see data being added and removed!\nFurthermore, this map lazily encrypts only the data that changes, which would allow you to see exactly which key changed (if any).\n\nA homomorphically encrypted map CRDT couldn't do that.\nSince it must assume a worst-case input, it must store the keys densely: limiting the size to a fixed number of keys and reserving all the space up front.\nMerging two identical maps would be exactly as computationally intensive as merging two maps in which every key was updated.\n\nThe playground below simulates a homomorphically encrypted map.\nWhile you can add and remove keys to the plaintext map on the left, the encrypted map on the right behaves as though every key is filled.\nAnd no matter how you modify the plaintext map, everything in the encrypted map changes:\n\nFrom the outside, there's no way to tell what changed in the map: we see the exact same number of keys, and every value has changed.\nTo calculate the new map, the server must go through and merge every single key.\nAfter that, it needs to transfer the full map to each peer — because remember, as far as it knows, the entire map is different.\n\nThese are fundamental limitations of homomorphic encryption!\nThe requirement that homomorphically encrypted code performs as though operating on the worst-case input dramatically increases both the space and time required to update.\n\nParting Thoughts\n\nI started this article thinking that local-first software and homomorphic encryption would be natural bedfellows.\n\nBut honestly, I came away… a little less enamored.\nThe fundamental limitations of homomorphic encryption mean that it will always operate under a set of worst-case assumptions.\nHomomorphically encrypted CRDTs aren't intractable, but they are severely limited by these intrinsic constraints.\n\nSo the question remains: how can we secure local-first apps without severely degrading usability?\n\nLuckily, I'm not the only one thinking about this problem!\n\nThere are a bunch of research papers on secure CRDTs.\n\nMartin Kleppman has written spoken about combining secure group messaging protocols with CRDTs.\n\nLast (but certainly not least), local-first pioneers Ink & Switch have been working on a project called Keyhive that explores how to add access control to local-first data.\n\nProbably many other projects I've missed!\n\nCRDTs are a relatively young technology — the paper formalizing them was published in 2011 — so there's still a lot of unexplored solution space.\nWe may not have solved this problem yet, but I'm confident that we're closing in on it!",
  "title": "Homomorphically Encrypting CRDTs"
}