## Property-Preserving Hash Functions

**Keywords:**

Cryptography, Data Compression

#### Description

A *hash function* is a deterministic map between an input string and a (usually shorter) output string. While this means that in theory hash functions can be used to compress data, it is not feasible to recover the input to a hash function given only its output. For two input strings that share a certain property (for example they are equal except for one symbol), the outputs are completely unrelated - the hash function behaves similar to a random oracle.

In contrast, *Property-Preserving Hash (PPH) Functions* are used to compress data in such a way that certain properties of the data remain preserved and can be evaluated based only on the hashed value, without knowledge of the original data.

More formally, a PPH function compresses two messages *x* and *y* as *h(x)* and *h(y)* where some predicate P(*x*, *y*) can be computed as Eval(*h(x)*, *h(y)*) such that P(x,y) = Eval(*h(x)*, *h(y)).*

A PPH function is said to be

*adversarially robust*if it is infeasible for an attacker to create some input

*x*,

*y*for which P(x,y) ≠ Eval(

*h(x)*,

*h(y)).*

The student should familiarize themselves with the concept of PPH functions using the main paper listed below, which describes the construction of a property-preserving hash function for the Hamming distance predicate.

The final report should include a description of PPH functions, their construction and some applications (possibly using some of the additional resources listed below).

**Main Paper:**

Property-Preserving Hash Functions from Standard Assumptions (https://arxiv.org/abs/2106.06453)

**Additional Reading:**

- Adversarially Robust Property-Preserving Hash Functions (https://drops.dagstuhl.de/opus/volltexte/2018/10109/pdf/LIPIcs-ITCS-2019-16.pdf)

- Robust Property-Preserving Hash Functions for Hamming Distance and More (https://eprint.iacr.org/2020/1301.pdf). A nice talk given by one of the authors of this paper from EUROCRYPT22 can also be found on the IACR Youtube channel.

- Property-Preserving Hash Functions and Combinatorial Group Testing (https://eprint.iacr.org/2022/478.pdf)

#### Contact

Anna Baumeister

anna.baumeister@tum.de