Paper 2018/1158

Adversarially Robust Property Preserving Hash Functions

Elette Boyle, Rio LaVigne, and Vinod Vaikuntanathan

Abstract

Property-preserving hashing is a method of compressing a large input x into a short hash h(x) in such a way that given h(x) and h(y), one can compute a property P(x, y) of the original inputs. The idea of property-preserving hash functions underlies sketching, compressed sensing and locality-sensitive hashing. Property-preserving hash functions are usually probabilistic: they use the random choice of a hash function from a family to achieve compression, and as a consequence, err on some inputs. Traditionally, the notion of correctness for these hash functions requires that for every two inputs x and y, the probability that h(x) and h(y) mislead us into a wrong prediction of P(x, y) is negligible. As observed in many recent works (incl. Mironov, Naor and Segev, STOC 2008; Hardt and Woodruff, STOC 2013; Naor and Yogev, CRYPTO 2015), such a correctness guarantee assumes that the adversary (who produces the offending inputs) has no information about the hash function, and is too weak in many scenarios. We initiate the study of adversarial robustness for property-preserving hash functions, provide definitions, derive broad lower bounds due to a simple connection with communication complexity, and show the necessity of computational assumptions to construct such functions. Our main positive results are two candidate constructions of property-preserving hash functions (achieving different parameters) for the (promise) gap-Hamming property which checks if x and y are “too far” or “too close”. Our first construction relies on generic collision-resistant hash functions, and our second on a variant of the syndrome decoding assumption on low-density parity check codes.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. MINOR revision.ITCS
Keywords
Hash functioncompressionproperty-preservingone-way communication
Contact author(s)
rio @ mit edu
History
2019-02-20: revised
2018-12-03: received
See all versions
Short URL
https://ia.cr/2018/1158
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/1158,
      author = {Elette Boyle and Rio LaVigne and Vinod Vaikuntanathan},
      title = {Adversarially Robust Property Preserving Hash Functions},
      howpublished = {Cryptology ePrint Archive, Paper 2018/1158},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/1158}},
      url = {https://eprint.iacr.org/2018/1158}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.