# Are there any practical implementation of a homomorphic hashing or signature scheme?

A homomorphic hash function is a function $H : A \to B$ between two sets with some algebraic structure $(A, *)$ and $(B, \star)$ such that

• $H$ is collision resistant, i.e. it is hard to find $x \neq y$ such that $H(x) = H(y)$ and
• $H$ is a homomorphism, i.e. $H(x * y) = H(x) \star H(y)$.

Are there any practical realizations of such a homomorphic hash function, or even a homomorphic signature scheme (i.e., where we can "add" valid signatures to get a signature of the "sum" of two messages)?

Even better, are there even any libraries implementing this?

• As far as I know, there is yet no practically efficient implementation of fully homomorphic encryption on the horizon. So the answer to your question would evidently be negative, at least for a good hashing scheme, IMHO. – Mok-Kong Shen Feb 27 '13 at 11:00
• FYI, I posted a question on Meta a while back about this type of question and whether we should allow them. Perhaps you would like to weigh in? – mikeazo Feb 27 '13 at 12:31
• sashank, I think you might need to specify more precisely exactly what you mean by homomorphic hashing. – D.W. Feb 27 '13 at 15:45
• @D.W., sashank: I edited the question to contain an explanation of what is searched here. – Paŭlo Ebermann Feb 27 '13 at 20:16
• You might want to add an additional constraint; the Identity function pedantically meets all the requirements listed; it is hard (impossible) to find $x \neq y$ with $I(x) = I(y)$, and for it homomorphic with any operation $\star$, that is, $I(A \star B) = I(A) \star I(B)$ – poncho Feb 27 '13 at 22:20

There's plenty of research in this area. I'll give you just a small sampling:

Like I said, this is only a small subset of the available research in this area. I found most of these through about 5 minutes with Google Scholar. I recommend you start by doing a literature review to familiarize yourself with the research literature on this subject: search to find as many relevant papers as possible; read each such paper; for each paper you find, read the related work section and bibliography to try to identify other relevant papers, and also use Google Scholar or other sites to find other papers that cite that paper that might be relevant; for each additional relevant paper you find, repeat the process.

After you have done this process, you should be in a better position to ask a more narrowly targeted question with a particular set of requirements -- or, if you're lucky, you might have found a solution to your particular problem already described in the literature!

• @sashank: Note though that I had responded to your original (unedited) OP with a comment and given there a negative answer. – Mok-Kong Shen Mar 2 '13 at 14:26

There is at least one secure, homomorphic hash function that I know of. It's found in the paper "On-the-Fly Verification of Rateless Erasure Codes for Content Distribution" located here:

http://pdos.csail.mit.edu/papers/otfvec/paper.pdf

The paper was published in the 2004 IEEE Symposium on Security & Privacy. Section IV describes the scheme and subsections IV.D and IV.E provide efficiency improvements (computational and space, respectively). Its security based on the difficulty of finding discrete logarithms in a large group. Whether or not the scheme is 'practical' is a function of the level of security desired, application domain, and the tolerance of the users.

For this scheme, there is no publicly available library implementation that I'm aware of (none of the authors' webpages have any code for it). It is stated in the paper that the authors themselves used the gmp library to implement it. You might be able to contact them and get a copy of their implementation. But, since the paper was published a decade ago, it's unlikely that they still have the code

Hash function of tree-list (such as bitstring) by list content with log number of multiplies per concat. This gives the same hash for every equal tree-list branch by list content regardless of its internal structure (and computes the exponents cumulatively by 2 multiplies in each next branch), and leafs can be the random primes for bit0/bit1 or any secureHash. I suspect its secure cuz subsetSum is nphard. The simplest case is a list of bits. Given 4 192 bit random primes (bit0 bit1 x y) and a bitstring b to hash,

hash384=pair( (sum<index i in b>((b[i]?bit1:bit0)*x^i))%y, (x^size(b))%y )


See my according github repo: benrayfield/homomorphiclistdedup

• If this is a homomorphic hash, what are the operators $*$ and $\star$ that it is homomorphic over? – poncho Jun 18 '17 at 17:28
• list concat (like add), and if you want to concat n times (like multiply) you can do that in log number of concats like exponent by squaring. – Ben Rayfield Jun 19 '17 at 20:39