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)
- 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
-
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}, url = {https://eprint.iacr.org/2016/617} }