24
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ 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)$ $\endgroup$
    – poncho
    Commented Feb 27, 2013 at 22:20
  • $\begingroup$ @sashank, Your question is very broad. It would help if you gave more specific requirements specific to your particular problem, about exactly what algebraic structure you have on $A$ and $B$ in your particular application. Also, on this site we expect you to do some background research of your own to learn what is already known. $\endgroup$
    – D.W.
    Commented Feb 27, 2013 at 22:20
  • $\begingroup$ Appears these system frequently depend upon the hardness of discrete log. I'd be interested in seeing a post-quantum homomorphic hash. $\endgroup$ Commented Mar 24, 2016 at 14:17

3 Answers 3

8
$\begingroup$

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!

$\endgroup$
0
3
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ If this is a homomorphic hash, what are the operators $*$ and $\star$ that it is homomorphic over? $\endgroup$
    – poncho
    Commented Jun 18, 2017 at 17:28
  • $\begingroup$ 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. $\endgroup$ Commented Jun 19, 2017 at 20:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.