lukechampine/lthash

A homomorphic hash function

lthash

go get lukechampine.com/lthash

This repo contains an implementation of LtHash, as defined by Bellare and Micciancio and later specified more concretely by researchers at Facebook.

LtHash is a homomorphic hash function based on BLAKE2x. A homomorphic hash function provides a solution to the following problem: Given the hash of an input, along with a small update to the input, how can we compute the hash of the new input with its update applied, without having to recompute the entire hash from scratch?

For example, say you have a database that contains three items: "Apple", "Banana", and "Orange". We compute the LtHash of this set by summing the hashes of the individual elements. Later, we replace "Banana" with "Grape". To compute the new hash, we take our original hash, subtract the hash of "Banana", and add the hash of "Grape". The resulting hash is the same as if the database originally contained "Grape" instead of "Banana".

This repo currently contains an implementation of lthash16. Facebook's paper further specifies lthash20 and lthash32; these may be added in the future.

Be aware that LtHash is vulnerable to multiset input collisions. A multiset is a set containing more than one instance of a particular element. In particular, it is trivial to produce a collision in lthash16 by adding the same input to the hash 2^16 times. One way to prevent this is to concatenate each input with a unique piece of metadata, such as an index.

Usage

h := lthash.New16()

// compute the combined hash of "Apple", "Banana", and "Orange"
h.Add([]byte("Apple"))
h.Add([]byte("Banana"))
h.Add([]byte("Orange"))
oldSum := h.Sum(nil)

// replace "Banana" with "Grape"; the resulting hash is the same
// as the combined hash of "Apple", "Grape", and "Orange".
h.Remove([]byte("Banana"))
h.Add([]byte("Grape"))
newSum := h.Sum(nil)

Benchmarks

Tested on an i5-7600K @ 3.80GHz. Results will likely be slower on non-amd64 architectures.

BenchmarkLtHash/16-4    200000    9651 ns/op    424.38 MB/s    0 allocs/op

lthash's Issues

Absolute nonsense

You're just adding and subtracting a hash function two bytes at a time. This doesn't satisfy a homomorphism.

Is this really what they're doing over at Facebook? This is nonsense.

If you've created a homomorphic hash function then this test should pass:

func TestHomomorphism(t *testing.T) {
	var x, y [2048]byte
	copy(x[:], []byte("Hello"))
	copy(y[:], []byte("World"))
	add16(&x, &y)

	h := New16()
	h.Add(x[:])
	s1 := h.Sum(nil) // H(x + y)

	h2 := New16()
	h2.Add([]byte("Hello"))
	h2.Add([]byte("World"))
	s2 := h2.Sum(nil) // H(x) + H(y)

	// this passes if H(x + y) = H(x) + H(y), otherwise there is no homomorphism
	if !bytes.Equal(s1, s2) {
		t.Error("s1 should equal s2")
	}
}

expected package, found import

can't load package: package .:
test.go:2:1: expected 'package', found 'import'

I tried running the go lthash program, so I created a test file (test.go), then copied and pasted the code provided on readme. But I was getting the above error

output not a regular hash digest

Hello Luke,
I modified the code a bit to enable me print out the values of the hash. I was surprised that the values are in form of list instead of the regular h ash digests.

package main
import "lukechampine.com/lthash"
import (
"fmt"
"reflect"
)

func createNewLtInstance() lthash.Hash {
h := lthash.New16()
fmt.Println(reflect.TypeOf(h))
return h
}

func incrementHash(h lthash.Hash, m string) []byte {
h.Add([]byte(m))
newSum := h.Sum(nil)
fmt.Println(newSum)
return newSum

}

func decrementHash(h lthash.Hash, m string) []byte {
h.Remove([]byte(m))
newSum := h.Sum(nil)
fmt.Println(newSum)
return newSum
}

func main() {
a := createNewLtInstance()
incrementHash(a, "apple")
incrementHash(a, "mango")
incrementHash(a, "tomatoes")
decrementHash(a, "apple")
incrementHash(a, "avocado")
//fmt.Println(a)

}

Does this actuially uses lattices?

Because in https://github.com/lukechampine/lthash/blob/master/lthash.go there is no references of lattices at all while the paper cited do use lattices

Idea: A cryptographic hash function using HAIFA

It would be useful to modift LtHash to use the HAIFA construction for a SHA3-doable hash function.
Adding a counter to each message block would make the compression function work.
See: https://eprint.iacr.org/2007/278.pdf