1

Do you know about a hash function, that approximates (in probability) the following function:

Original function: Two vectors collide if there is a row where their entries are equal. $$ \text{E.g., }\quad \begin{pmatrix} 1\\ 2\\ 3 \end{pmatrix} \text{ and } \begin{pmatrix} 4\\ 2\\ 6 \end{pmatrix} \text{ collide (both=2 on row 2),} \qquad \begin{pmatrix} 2\\ 1\\ 3 \end{pmatrix} \text{ and } \begin{pmatrix} 4\\ 2\\ 6 \end{pmatrix} \text{ do not collide.} $$

Hash Function: Do you know about a hash function where the hashes of two vectors $u,v$ are equal (with high probability) if they they had an equal entry on some row (so, $\exists i\colon u_i=v_i$)?

$$ \text{So,}\quad P(h(v)=h(u)) \quad \text{should be high for vectors that have a same entry on some row} $$

ndrizza
  • 1,348

1 Answers1

0

I don't think such a hash function should exist because the collision rule that you defined is not transitive. For example, $A=(1,2,3)^T$ collides with $B=(1,4,5)^T$ at $1$, and $B$ collides with $C=(7,6,5)^T$ at $5$, but $A$ and $C$ do not collide. But for any hash function $h$, if $h(A)=h(B)$ and also $h(B)=h(C)$, then $h(A)=h(C)$. There are too many such examples, so the chances of errors for an "approximate" hash function should be very high.

Zhuoran He
  • 3,039