Homomophic Hashes — Efficient Trust and Avoiding Complex Hashing Operations

Homomorphic Hashes — Efficient Trust and Avoiding Complex Hashing Operations

We waste so much computing power, and every bit of extra computing costs us a little more energy. So, a good of work is going into making sure we have trusted systems, but also in reducing our computational overhead. Can you thus have trust with efficiency?

Homomorphic Hashes

We are currently seeing the rise of homomorphic encryption, and where we can mathematically process encrypted values. But, how can we create a new hash value, without knowing the previous values added to the hash? Well, we can do this with a homomorphic hash. So, let’s look at one of the implementations of this: LtHash and initially defined by Bellare and Micciancio [1]:

At the time, the homomorphic encryption method was defined as an incremental technique. The method has since been updated by Lewi et al at Facebook [2]:

This paper focuses on a method by which an owner of a database — a distributor — is responsible for propagating updates to subscribers. With this, the distributor is then responsible for updating the subscribers with a signed hash. Overall, it may be possible to recompute the over hash to the data, but it would be more efficient to update the hash based on new data added. The distributer can then just take the previous hash, and then added the new data, and produce the new hash.

With homomorphic hashing, Bob (the distributor) needs to sign for updates to Grace (a subscriber). In a normally hashing method, Bob would take all the previous data and the new data, and compute a new hash (Figure 1). If we have large amounts of data, this may be a computationally intensive task. To overcome this we can use a homomorphic hashing method, where we take a previous hash and then compute the new hash using this and any new data:

Coding

In Golang, we initialize a 2,048-byte hash. In this case, we will use Blake2b, and where XOF is an extendable output function (and which is similar to a normal has, but can be of any size of output):

}          
func New16() Hash {
 xof, _ := blake2b.NewXOF(2048, nil)                               return &hash16{xof: xof}                             
}

This initialises our hash value to a Nil hash value (“0000000000000000000000000000000000000000000000000000000000000000”). To add a hash, we take the current hash (x) and add a new one (y). We then take two bytes (16 bits) at a time from each, and then add them together, and then put it back into the current value of x:

func add16(x, y *[2048]byte) { 
 for i := 0; i < 2048; i += 2 { 
   xi, yi := x[i:i+2], y[i:i+2]                               
   sum := binary.LittleEndian.Uint16(xi) +   
     binary.LittleEndian.Uint16(yi)  
                             
   binary.LittleEndian.PutUint16(xi, sum)                                 }                             
}

To perform a removal of a value (y) from x (the current hash), we just subtract the hash two bytes(16 bits) at a time:

func sub16(x, y *[2048]byte) { 
 for i := 0; i < 2048; i += 2 { 
   xi, yi := x[i:i+2], y[i:i+2]                               
   sum := binary.LittleEndian.Uint16(xi) -  
     binary.LittleEndian.Uint16(yi)  
                             
   binary.LittleEndian.PutUint16(xi, sum)                                 }                             
}

The code is [here]:

In the following, we will add “Edinburgh”, “Glasgow” and “Dundee”, and produce a hash. Then we will remove “Edinburgh” and add “Stirling” and produce a new hash. Finally, we check the hash of “Glasgow”, “Dundee” and “Stirling”, and see if it is the same as the one previously created with the addition and removal of our data objects. A sample run is [here]:

Adding: Edinburgh
Adding: Glasgow
Adding: Dundee
Sum (first 32 bytes): 3a2031807078ccf8c9ae4fd21ce6c4407e558e9671aedd9eff8758766d690944

Removing: Edinburgh
Adding: Stirling
Sum (first 32 bytes): 3c02c125fd9d9d679f5f8a536dbd6498ff55b5d1ec85440b91cd9a6969100cbf

Now checking with: Glasgow, Dundee, Stirling
Sum (first 32 bytes): 3c02c125fd9d9d679f5f8a536dbd6498ff55b5d1ec85440b91cd9a6969100cbf

The length of the hash is: 2048 bytes

Overall, Facebook saw they have implemented with 200-bit security, but rather than our 32-byte hash as we would have with SHA-256, we end up with a 2,048-byte hash.

Conclusions

We are often inefficient with our processing. Every bit of computation consumes a little bit more energy and processing time. The homomorphic encryption method defined by Facebook is a good step along the route of understanding how we can be efficient in providing trust. With this implementation, Facebook thus has to only use the previous hash and new data, in order to compute a new hash. This can then be signed with their private key, and the signature checked by the subscribers. If you want to know more about homomorphic encryption, try here:

https://asecuritysite.com/homomorphic

References

[1] Bellare, M., & Micciancio, D. (1997, May). A new paradigm for collision-free hashing: Incrementality at reduced cost. In International Conference on the Theory and Applications of Cryptographic Techniques (pp. 163–192). Springer, Berlin, Heidelberg.

[2] Lewi, K., Kim, W., Maykov, I., & Weis, S. (2019). Securing Update Propagation with Homomorphic Hashing. Cryptology ePrint Archive.