Picture of Anna Baumeister

M.Sc. Anna Baumeister

Technical University of Munich

Associate Professorship of Coding and Cryptography (Prof. Wachter-Zeh)

Postal address

Postal:
Theresienstr. 90
80333 München

Theses

Available Theses

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

Supervisor:

Theses in Progress