You are looking at a specific version 20201019:163647 of this paper. See the latest version.

Paper 2020/1301

Robust Property-Preserving Hash Functions for Hamming Distance and More

Nils Fleischhacker and Mark Simkin

Abstract

Robust property-preserving hash (PPH) functions, recently introduced by Boyle, Lavigne, and Vaikuntanathan [ITCS 2019], compress large inputs $x$ and $y$ into short digests $h(x)$ and $h(y)$ in a manner that allows for computing a predicate $P$ on $x$ and $y$ while only having access to the corresponding hash values. In contrast to locality-sensitive hash functions, a robust PPH function guarantees to correctly evaluate a predicate on $h(x)$ and $h(y)$ even if $x$ and $y$ are chosen adversarially after seeing $h$. Our main result is a robust PPH function for the exact hamming distance predicate $$\mathsf{HAM}^t(x, y) = \begin{cases}1 &\text{if } d( x, y) \geq t \\0 & \text{Otherwise}\\\end{cases}$$ where $d(x, y)$ is the hamming-distance between $x$ and $y$. Our PPH function compresses $n$-bit strings into $\mathcal{O}(t \lambda)$-bit digests, where $\lambda$ is the security parameter. The construction is based on the q-strong bilinear discrete logarithm assumption. Along the way, we construct a robust PPH function for the set intersection predicate $$ \mathsf{INT}^t(X, Y) = \begin{cases} 1 &\text{if } \vert X \cap Y\vert > n - t \\ 0 & \text{Otherwise}\\ \end{cases} $$ which compresses sets $X$ and $Y$ of size $n$ with elements from some arbitrary universe $U$ into $\mathcal{O}(t\lambda)$-bit long digests. This PPH function may be of independent interest. We present an almost matching lower bound of $\Omega(t \log t)$ on the digest size of any PPH function for the intersection predicate, which indicates that our compression rate is close to optimal. Finally, we also show how to extend our PPH function for the intersection predicate to more than two inputs.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint.
Keywords
Hash functionsproperty-preservinghamming distance
Contact author(s)
simkin @ cs au dk,nils fleischhacker @ rub de
History
2020-10-19: last of 2 revisions
2020-10-19: received
See all versions
Short URL
https://ia.cr/2020/1301
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.