Welcome to the resource topic for 2016/617
Title:
On the Impossibility of Merkle Merge Homomorphism
Authors: 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.
ePrint: https://eprint.iacr.org/2016/617
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .