Cryptographic data structure: sparse array without membership test I would like a data structure supporting two operations: $\mathsf{set}(k,v)$ and $\mathsf{get}(k)$, with the following properties:


$k$ can be any number between $0$ and something impressively large, like $2^{256}-1$.
If there is some $v$ such that $\mathsf{set}(k,v)$ has been called then $\mathsf{get}(k)$ returns the most recent such $v$.
There is no way to learn anything about which $k$ and $v$ are such that $\mathsf{set}(k,v)$ has been called (but it might be possible to determine information that does not have to do with specific $k$ and $v$, e.g., it might be possible to learn how many times set has been called or on how many different $k$ it has been called).
Space and time complexity are bounded by reasonable functions of the total number of calls to set and get (or better yet by a reasonable function of the number of keys set has been called on).


An attacker would learn everything I know, so the solution cannot be based on me retaining any secrets.  But an attacker would not see the sequence of $\mathsf{set}$ and $\mathsf{get}$ operations since that would allow knowing what $\mathsf{set}$ has been called on.  An example of a data structure that would meet all my demands except for the computational complexity ones is to create at time zero an array of size $2^{256}$ populated by random data and then update and query it as a normal array.

I assume a fixed field length for $v$ and also that the data being stored in $v$ is effectively random.  The meaning of the last statement is a bit subtle.  If $v$ is a 256-bit field then storing all zeros in a place in the array will effectively give away that it has been set.  If $v$ is a 1-bit field then storing any particular value in any particular place will not give anything away, but other patterns, like storing more zeros than ones might.  Imagine that the attacker has a correct guess about what the set of set keys is.  Depending on how the array was used, he might be able to become more certain of his guess by querying the array.  I simply want a data structure that doesn't give up any more information than strictly necessary beyond the infeasible full array of length $2^{256}$ initially stocked with random data.

Obviously it will have to give up a little more information because it will get bigger depending on how much data it has in it (compare black holes), but ideally the approximate number of keys set is all the information it will leak.  Actually, it will not have to progressively give up more information if the maximum amount of data the structure can contain is fixed at creation time.  And the partial solutions to the problem that are given below by otus and myself require the size to be fixed in this way anyway.

Is there such a data structure?  Also, what is a good reference for this kind of question?

The attacker only gets to see the final data structure. The concept of history-independent data structures looks really interesting, but I am skeptical that literature will help with my problem. Among other things, the couple of papers I looked at seemed to use a threat model where the attacker has infinite computational resources, but it is impossible to solve the problem under that threat model.
This answer builds on the answer supplied by @otus.  There is also an important worry about whether the main solution works at all as advertised.  I am posting it now to make clearer to @otus a question I asked in a comment.  I will eventually either delete it or substantially revise it.

First off, let me emphasize that if the table is going to be used to store arbitrary data, then an attacker who suspects k is a key may be able to test the suspicion by checking whether get(k) is data-like.  So the natural guarantee in this case is just that an attacker cannot recover any information from the table without possessing the key to that data.  If this guarantee is all we require, the problem can be completely solved using the @otus's idea of hashing the keys and using the hash as a symmetric encryption key.  Let me explain this solution as a preliminary.

Assume, as @otus does, that an initial hash has been performed.  (Questions: do standard cryptographic hash functions actually come with a guarantee that the hashes are indistinguishable from draws from the uniform distribution?  Also, if we are willing to hash to a larger space than the domain, can we be guaranteed that the hash function is injective?)

A simple version of the data structure is as follows.  We maintain a list of data items.  Each item in the list is of the form $E_k(k,v)$ for a $k$ that is unique in the list.  To retrieve the value associated with $k$, we decrypt the list members using $k$ and check for one that returns to $(k,v)$.  To store $(k,v)$, we first check if $k$ already has a value associated with it and, if so, remove the corresponding data item from the list.  Then we add $E_k(k,v)$ to the list.

The simple version has linear time overhead, but it is straightforward to eliminate that inefficiency by using hash tables with collision resolution.

Now back to the full version of the problem, which is mainly interesting in the case where the stored data will be indistinguishable from random bit strings.

@otus gives a solution to this problem, but it has three drawbacks: it is probabilistic, it requires super-quadratic space to have low error probability, and it the eventual size of the data structure must be known in advance.  The first and third drawbacks seem to me inescapable, though I have no proof of this conjecture.  I have an idea about how to eliminate the second drawback, but it depends on the existence of a certain kind of error-correcting code.

The data structure is an array of $N$ bits initialized to random values.  To store $(k,v)$, we use $k$ to seed a pseudo-random number generator to generate a sequence of indices into the table.  We blow up $E_k(v)$ to double its original size using an error-correcting code, and we store the successive bits of this blown up version of $E_k(V)$ at the successive pseudo-random indices into the table.  This code can correct errors in up to half bits, so as long as the probability of a collision at any bit is significantly less than a half, we can be virtually certain of recovering the data.  If the table is four times size of the data stored in it then the expected number of bits stored at each index will be 1/2.  We can think of the number of collisions at a location as following a Poisson distribution with mean 1/2, so the probability of no collisions at a location will be about .61.  Assuming the data is long, there will be an overwhelmingly high probability that we can recover it from the code.  And the total space requirement is only four times the amount of space we need to hold the data.

The only problem is that with normal error-correcting codes, it is easy to tell whether an bit string is a code or not, and it is probably also easy to tell if a bit string is close to being a code in the Hamming metric.  So an attacker in possession of $k$ would be able to confirm that $k$ was likely a key, precisely what we don't want.  I am not sure if this problem dooms the whole approach I am contemplating here or whether there are special codes that do not have this problem.  Now with any code there will be some bit strings that it is easy to see are not code words because they have short Hamming distance to bit strings that decode to something different.  But maybe such bit strings could be rare, or even impossible to find, and bit strings that do not have that property would be indistinguishable from codes.