Hash Fitting Problem

Posted on 02 Nov 2021

I have an open problem, don’t know about any concrete applications.

Problem #

We are given a finite set \(S \subset \{0, 1\}^*\) which contains \(n\) strings. The problem is to generate a cryptographically secure hash function   \(f: \{0, 1\}^* \longrightarrow \mathbb{Z}_{\lceil log_2(n) \rceil}\) in polynomial time, such that for any two unique strings \(x, y \in S\),   \(f(x) \neq f(y)\). We will call this problem Hash-Fitting Problem.

When? #

I was thinking about the a famous MPC problem - Private Information Retrieval. In this, one party owns an array \(A\) and the other party owns an index \(i\). The objective is to let the second party know \(A[i]\) only, without the first party knowing learning anything about \(i\). This is a generalization of Oblivious Transfer where \(A\) contains only two elements.

PIR is useful for realizing private static websites, where \(A\) is analogous to the array of static pages and \(i\) is the path that you type in the address bar. Though this would require a specialized web browser to implement, but even if such browser exists, the static website owner would have to have a public function to convert string paths like “/”, “/home” to numbers. They could have a lookup table for this function, but they would then have to expose all the paths. This might not be something that the server owner wants. Hence we need to solve this problem.

Interested? #

Hit me up and we can discuss :)