4 ms·
Open-sourcing homomorphic hashing to secure update propagation
- jawns 8y agoThe post offers a brief explanation of homomorphic hashing: > homomorphic hashing answers the question, “Given the hash of an input, along with a small update to that input, how can we compute the hash of the new input (with the update applied) without having to recompute the entire hash from scratch?” We use LtHash, a specific homomorphic hashing algorithm based on lattice cryptography, to create an efficiently updatable checksum of a database. Imagine adding and subtracting hashes! > For any two disjoint sets S and T, LtHash(S) + LtHash(T) = LtHash(S ∪ T). This is cool because now you don't have to recompute from scratch a hash representing a large array; you can just compute the hash of the parts you update and perform addition and subtraction.
- zzzcpan 8y agoYears ago I was trying to use Merkle trees for checksuming and synchronizing database replicas, since everyone was doing it this way. It was immediately obvious how impractical it was. So the first thing that came to mind was to use a fixed sized Merkle tree (half trees or whatever they are called). It was essentially an array of 64k hashes with each element storing a hash for a set of database keys. That, however, required rescanning multiple keys on updates and the number of keys depended on the database size. Of course this wasn't going to work well. Naturally the same idea of adding and subtracting hashes came to mind. Adding a hash of a key on update and subtracting on removal allowed to completely eliminate reads from disk. And rescanning a particular set of keys was only necessary during background synchronization and only when a key was missing on a replica, which was pretty rare. Although I don't use this approach anymore, it did work well and was trivial to implement.
- maximegarcia 8y agoSaving it. This is what I dreamt of for the ETag header of a list of items in a REST API (when caching each of the items separatly).
- dfox 8y agoI somehow fail to see why the example in the article needs the hash to have some special property of homomophicity. When you represent the overall hash of your dataset as a sum of individual item hashes it trivially follows that change of one item means that you substract the hash of original version and add the hash of new version. Or am I missing something? (apart from the somewhat obvious security implications of doing such a thing in the first place)
- mlthoughts2018 8y agoSay you just define your total hash to be the sum of hashes for some constituent data. You change a constituent datum, so you subtract the old hash, add the new hash. What will you get when you decrypt the total hash? Probably some gibberish data. If your hashing had the homomorphic property, then when you do the add/subtract song and dance with some datum’s new hash, the resulting total hash has the property that it decrypts to be the sum of the (updated) data. A practical example might be keeping track of the average salary of a group of people without ever learning the salary of any one of them. As they get raises, you learn only about their new encrypted salaries, but you can update the encryption of the average salary directly, knowing that it will decrypt to the correctly updated new average inclusive of raises you never explicitly saw. (Here I am using the term “hash” loosely to refer to the cipher text of whatever data item is encrypted.)
- ivmaykov 8y agoDisclaimer: I’m one of the authors of the paper/blog post/code. If you want to use signatures over the hash as proof of data set integrity, you need two things. 1) you need to make sure that hash({a}) + hash({b}) == hash({a, b}). 2) ensure that hash() is collision resistant - in other words, it needs to be computationally infeasible to find hash(S) == hash(T), S != T for any sets S and T. We prove that LtHash with our choice of parameters has this property in the paper (which is linked from the blog post).
- dfox 8y agoMy reading of the post is that the Hash({a, b}) is infact computed as Hash'(a) + Hash'(b) given that a and b are "rows". And thus my question is why Hash' has to have any special properties.