Cryptology ePrint Archive: Report 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.

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:

[ Cryptology ePrint archive ]