Homomorphic Hashing .. Is It Possible?
Let’s start with a problem. Bob, Alice, Carol and Dave have hashed their passwords with:
H(“Bob123”), H(“Alice111”), H(“Carol999”) and H(“Dave!!!”)
Can we now find a way that we have find the hash of:
H(“Bob123” || “Alice111” || “Carol999” || “Dave!!!”)
and where we do not need to find out what any of the passwords are. And if we could do this, could we also remote a hashed value from it? For this, we could remove Dave’s hash to get:
H(“Bob123” || “Alice111” || “Carol999” )
For this, we need incremental hashing (IH), or more generally, homomorphic hashing (HH).
Incremental hashing
Normally with hashing methods, we need to take all the previous data and new data in order to create a new hash value for our data. In a homomorphic hashing method, we can basically take the previous hash, and then add on any new data values. We can also remove previous data values from our hash, too. This is more efficient in computing, as we do not have to process all of our data into a new hash, and can use simple homomorphic operations for the computation. The method we will use (LtHash) was initially defined by Bellare and Micciancio [1] and defined as an incremental hash:
