Paper 2021/773

HEX-BLOOM: An Efficient Method for Authenticity and Integrity Verification in Privacy-preserving Computing

Ripon Patgiri and Malaya Dutta Borah


Merkle tree is applied in diverse applications, namely, Blockchain, smart grid, IoT, Biomedical, financial transactions, etc., to verify authenticity and integrity. Also, the Merkle tree is used in privacy-preserving computing. However, the Merkle tree is a computationally costly data structure. It uses cryptographic string hash functions to partially verify the data integrity and authenticity of a data block. However, the verification process creates unnecessary network traffic because it requires partial hash values to verify a particular block. Moreover, the performance of the Merkle tree also depends on the network latency. Therefore, it is not feasible for most of the applications. To address the above issue, we proposed an alternative model to replace the Merkle tree, called HEX-BLOOM, and it is implemented using hash, Exclusive-OR and Bloom Filter. Our proposed model does not depends on network latency for verification of data block's authenticity and integrity. HEX-BLOOM uses an approximation model, Bloom Filter. Moreover, it employs a deterministic model for final verification of the correctness. In this article, we show that our proposed model outperforms the state-of-the-art Merkle tree in every aspect.

Note: This work has been submitted to the IEEE for possible publication. Copyright may be transferred without notice, after which this version may no longer be accessible.

Available format(s)
Publication info
Preprint. MINOR revision.
authenticationverificationhashBlockchainprivacyMerkle tree
Contact author(s)
ripon @ cse nits ac in
2021-10-06: last of 7 revisions
2021-06-09: received
See all versions
Short URL
Creative Commons Attribution


      author = {Ripon Patgiri and Malaya Dutta Borah},
      title = {HEX-BLOOM: An Efficient Method for Authenticity and Integrity Verification in Privacy-preserving Computing},
      howpublished = {Cryptology ePrint Archive, Paper 2021/773},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.