Hide the presence of a key in a key-value storage Problem: I want to build a key-value storage in such a way that it would be impossible to detect a presence of a key in the storage by inspecting it. In other words, any read operation with any valid key always returns a valid-looking value, and without additional knowledge about value it is impossible to say if this key was ever written to the storage, or is it a plain garbage.
Such kind of storage is possible. For example, a simple (but space consuming) approach would be to create a storage and pre-fill all possible valid keys with random values. Write operation replaces the existing value with the new one, delete operation replaces the existing value with a random one. Then just by looking at the storage it is impossible to tell which keys actually contain written values, and which just store a random garbage.
But this of course is impractical for large enough key space.
I suspect that there could be a more practical solution.
Suppose you have a set of key-value pairs $(k_1, v_1), (k_2,v_2), \ldots$. You can store the coefficients of a polynomial $P$ that satisfies $P(k_i)=v_i$. The polynomial can be evaluated at any point to give a plausible output.
The degree of the polynomial leaks the number of key-value pairs, but if the $v_i$'s are uniform then the polynomial leaks nothing about the $k_i$'s. This is because for every way of fixing distinct $k_i$'s, the polynomial's coefficients are an invertible linear function of the $v_i$'s, so the coefficients are uniform if the $v_i$'s are uniform.
The only real downside is that polynomial evaluation is a bit slow: if there are $n$ key-value pairs then probing this data structure costs $\Theta(n)$.
However, there are alternatives to polynomials that have the security properties you need, with cheaper $O(\kappa)$ access time (for security parameter $\kappa$).
They have slightly higher storage overhead, whereas polynomials are optimal in size (exactly $n$ space to store $n$ key-value pairs).
The best reference for these data structures is actually an upcoming paper of mine, which will be on eprint in the next few weeks. I can post an update here when it's available.
In the meantime, the &quot;best&quot; publicly available oblivious key-value store is the probe-and-XOR-of-strings data structure that we propose in ia.cr/2020/193.
It has $O(\kappa)$ access time and $\sim 2.5n$ size to store $n$ key-value pairs.