Cryptology ePrint Archive: Report 2016/617
On the Impossibility of Merkle Merge Homomorphism
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 , data maintenance , 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  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.
Category / Keywords: hash functions, digital signature, homomorphism
Date: received 13 Jun 2016, last revised 21 Jun 2016
Contact author: ytang100 at syr edu
Available format(s): PDF | BibTeX Citation
Version: 20160622:041009 (All versions of this report)
Short URL: ia.cr/2016/617
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]