# Permuted Hash Table

Suppose we have a hash table, $HT$, consisting of $100$ bins.The hash table uses a hash function $H$ that is public. We all know that given value $a$ we can compute the address in the hash by $H(a)=j$, where $j$ is the $j^{th}$ bin the the table.

• Assume we construct an empty hash table of size $100$, then we permute (using keyed pseudorandom permutation) the bins and give it to an adversary. So it does not know the original index of each bin in the table.

• Then, given value $b$ we compute the original index $i$. Next, we use the key to compute the index $i'$ in the permuted hash table.

• We encrypt value $b$ (using semantically secure encryption) and give the ciphertext and $i'$ to the adversary and ask it to insert the ciphertext in position $i'$ in the hash table.

Assume that the adversary know the universe of $b$ and the universe is not too large.

Question: Can we say that given the ciphertext and $i'$ the adversary learns nothing about the message $b$? If Yes/No why?

• Is the transform from $H(a)$ to the index $i'$ deterministic? If so, then someone who sees two values $a, b$ hashing to the same entry in the table can immediately deduce that $H(a) = H(b)$. This implies that if they know what $a$ is, they reduce the number of possible values of $b$ significantly. – poncho Feb 8 '16 at 21:31
• @poncho mapping from $H(a)$ to $i'$ is deterministic but we can use a pseudorandom permutation (that uses a random key) for the mapping, and the server obviously does not know the key. – user153465 Feb 9 '16 at 9:39
• @poncho Alternatively, we can map the original index, $i$, to a random value $i'$ (using a pseudorandom function), then we give away the encrypted $b$ and $i'$ to an adversary. And ask him to insert encrypted $b$ into $i'$-th bin in the hash table. – user153465 Feb 9 '16 at 10:00