eprint.iacr.org will be offline for approximately an hour for routine maintenance again at 10pm UTC on Wednesday, April 17.

Paper 2019/227

Securing Update Propagation with Homomorphic Hashing

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

Abstract

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.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Contact author(s)
klewi @ fb com
wonho @ fb com
ilyam @ fb com
sw @ saweis net
History
2019-02-28: received
Short URL
https://ia.cr/2019/227
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/227,
      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{https://eprint.iacr.org/2019/227}},
      url = {https://eprint.iacr.org/2019/227}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.