0
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – poncho
    Commented Feb 8, 2016 at 21:31
  • $\begingroup$ @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. $\endgroup$
    – user153465
    Commented Feb 9, 2016 at 9:39
  • $\begingroup$ @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. $\endgroup$
    – user153465
    Commented Feb 9, 2016 at 10:00

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.