Paper 2016/617

On the Impossibility of Merkle Merge Homomorphism

Yuzhe Tang

Abstract

This work considers a theoretic problem of merging the digests of two ordered lists “homomorphically.” This problem has potential applications to efficient and verifiable data outsourcing, which is especially desirable in the public cloud computing where the cloud is not trustworthy. We consider the case of merge-sort as it is fun- damental to many cloud-side operations, such as database join [32], data maintenance [10], among others. Informally, a merge-homomorphic digest enables that the digest of an ordered list, merged from two sublists, is computable from the digests of the two sublists. We present the formal definition of a merge-homomorphic digest (§ 2). We then examine the feasibility of using Merkle hash tree or MHT [17] to construct the merge-homomorphic digest (§ 3). Our theoretic result is that we proved the impossibility of merge- homomorphism for MHT (§ 3.2) by contradiction to the definition of collision-resistant hashes. This negative result is useful to understanding the limitations for designing a merge-homomorphic digest and might shed lights for a correct construction in the future.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
hash functionsdigital signaturehomomorphism
Contact author(s)
ytang100 @ syr edu
History
2016-06-22: last of 2 revisions
2016-06-16: received
See all versions
Short URL
https://ia.cr/2016/617
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/617,
      author = {Yuzhe Tang},
      title = {On the Impossibility of Merkle Merge Homomorphism},
      howpublished = {Cryptology ePrint Archive, Paper 2016/617},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/617}},
      url = {https://eprint.iacr.org/2016/617}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.