News for hackers. Stuff that matters.
Re:Open-sourcing homomorphic hashing to secure update propag... by dfox on Saturday March 02, 2019 @10:10PM (#19292460)
I 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)

Re:Open-sourcing homomorphic hashing to secure update propag... by ivmaykov on Saturday March 02, 2019 @11:04PM (#19292644)
Disclaimer: 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).

Re:Open-sourcing homomorphic hashing to secure update propag... by dfox on Saturday March 02, 2019 @11:43PM (#19292770)
My 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.
Re:Open-sourcing homomorphic hashing to secure update propag... by ivmaykov on Sunday March 03, 2019 @12:02AM (#19292828)
I can think of hash functions that are homomorphic, but are not secure. A simple example is something like “sha256 each element separately and XOR all the resulting hashes together.” This would not be collusion resistant.

We offer a proof that LtHash with our choice of parameters provides over 200 bits of security. You would have to read the paper for the details.

Re:Open-sourcing homomorphic hashing to secure update propag... by Scaevolus on Sunday March 03, 2019 @01:29AM (#19293074)
I can see how you might lose collision resistance with a normal 256-bit hash function, but it's not clear why a "stretched" hash with 2048 bytes of output wouldn't work.

E: Ah, there it is, in the paper:

> However, Wagner [Wag02] later showed an attack on the generalized birthday problem which could be used to find collisions > for AdHash on an n-bit modulus in time O(2^(2√n)), and that the AdHash modulus needs to be greater > than 1600 bits long to provide 80-bit security. Lyubashevsky [Lyu05] and Shallue [Sha08] showed > how to solve the Random Modular Subset Sum problem (essentially equivalent to finding collisions > in AdHash) in time O(2^(n^ε)) for any ε < 1, which indicates that AdHash requires several more orders > of magnitude larger of a modulus just to provide 80-bit security.

Re:Open-sourcing homomorphic hashing to secure update propag... by jorangreef on Sunday March 03, 2019 @09:08AM (#19294476)
Assuming a trusted system, could you go into more detail on the qualities or guarantees a Merkle tree using XOR would or would not give you and partial mitigations for any of these disadvantages? i.e. How does the entropy of a leaf node's 256-bit signature disperse into the tree up to the root? How does the birthday paradox come into play with regards to collisions at the root of the tree?

For synchronization purposes in a trusted system, a Merkle tree based on XOR seems elegant and efficient, but I can't seem to find accessible papers on this.

Re:Open-sourcing homomorphic hashing to secure update propag... by rstuart4133 on Wednesday March 06, 2019 @01:51AM (#19316833)
Just so I have this clear: is the issue the simple solution above doesn't work (at all) with multisets, and the birthday problem combined with potentially billions of rows means even sha256 will have a significant chance generating a collision?
Re:Open-sourcing homomorphic hashing to secure update propag... by scottlocklin on Sunday March 03, 2019 @09:47AM (#19294655)
Are you guys going to use this in your blockchain?
Re:Open-sourcing homomorphic hashing to secure update propag... by mlthoughts2018 on Saturday March 02, 2019 @10:47PM (#19292590)
Say 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.)