Paper 2021/793
PropertyPreserving Hash Functions for Hamming Distance from Standard Assumptions
Abstract
Propertypreserving hash functions allow for compressing long inputs $x_0$ and $x_1$ into short hashes $h(x_0)$ and $h(x_1)$ in a manner that allows for computing a predicate $P(x_0, x_1)$ given only the two hash values without having access to the original data. Such hash functions are said to be adversarially robust if an adversary that gets to pick $x_0$ and $x_1$ after the hash function has been sampled, cannot find inputs for which the predicate evaluated on the hash values outputs the incorrect result. In this work we construct robust propertypreserving hash functions for the hammingdistance predicate which distinguishes inputs with a hamming distance at least some threshold $t$ from those with distance less than $t$. The security of the construction is based on standard lattice hardness assumptions. Our construction has several advantages over the best known previous construction by Fleischhacker and Simkin (Eurocrypt 2021). Our construction relies on a single wellstudied hardness assumption from lattice cryptography whereas the previous work relied on a newly introduced family of computational hardness assumptions. In terms of computational effort, our construction only requires a small number of modular additions per input bit, whereas the work of Fleischhacker and Simkin required several exponentiations per bit as well as the interpolation and evaluation of highdegree polynomials over large fields. An additional benefit of our construction is that the description of the hash function can be compressed to $\lambda$ bits assuming a random oracle. Previous work has descriptions of length $\mathcal{O}(\ell \lambda)$ bits for input bitlength $\ell$. We prove a lower bound on the output size of any propertypreserving hash function for the hamming distance predicate. The bound shows that the size of our hash value is not far from optimal.
Note: Changed title as suggested by Eurocrypt 2022 reviewers.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 A minor revision of an IACR publication in EUROCRYPT 2022
 Keywords
 PropertyPreserving Hash functions Hamming distance PostQuantum
 Contact author(s)

mail @ nilsfleischhacker de
larsen @ cs au dk
mark simkin @ ethereum org  History
 20220608: revised
 20210614: received
 See all versions
 Short URL
 https://ia.cr/2021/793
 License

CC BY
BibTeX
@misc{cryptoeprint:2021/793, author = {Nils Fleischhacker and Kasper Green Larsen and Mark Simkin}, title = {PropertyPreserving Hash Functions for Hamming Distance from Standard Assumptions}, howpublished = {Cryptology {ePrint} Archive, Paper 2021/793}, year = {2021}, url = {https://eprint.iacr.org/2021/793} }