Paper 2019/227

Securing Update Propagation with Homomorphic Hashing

Kevin Lewi, Wonho Kim, Ilya Maykov, and Stephen Weis


In database replication, ensuring consistency when propagating updates is a challenging and extensively studied problem. However, the problem of securing update propagation against malicious adversaries has received less attention in the literature. This consideration becomes especially relevant when sending updates across a large network of untrusted peers. In this paper we formalize the problem of secure update propagation and propose a system that allows a centralized distributor to propagate signed updates across a network while adding minimal overhead to each transaction. We show that our system is secure (in the random oracle model) against an attacker who can maliciously modify any update and its signature. Our approach relies on the use of a cryptographic primitive known as homomorphic hashing, introduced by Bellare, Goldreich, and Goldwasser. We make our study of secure update propagation concrete with an instantiation of the lattice-based homomorphic hash LtHash of Bellare and Miccancio. We provide a detailed security analysis of the collision resistance of LtHash, and we implement Lthash using a selection of parameters that gives at least 200 bits of security. Our implementation has been deployed to secure update propagation in production at Facebook, and is included in the Folly open-source library.

Available format(s)
Publication info
Preprint. MINOR revision.
Contact author(s)
klewi @ fb com
wonho @ fb com
ilyam @ fb com
sw @ saweis net
2019-02-28: received
Short URL
Creative Commons Attribution


      author = {Kevin Lewi and Wonho Kim and Ilya Maykov and Stephen Weis},
      title = {Securing Update Propagation with Homomorphic Hashing},
      howpublished = {Cryptology ePrint Archive, Paper 2019/227},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.