Property-Preserving Hash Functions
Cryptography, Data Compression
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).
Property-Preserving Hash Functions from Standard Assumptions (https://arxiv.org/abs/2106.06453)
- 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)