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:

1. $k$ can be any number between $0$ and something impressively large, like $2^{256}-1$.
2. If there is some $v$ such that $\mathsf{set}(k,v)$ has been called then $\mathsf{get}(k)$ returns the most recent such $v$.
3. 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).
4. 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 sounds distantly related to multiple-message encoding in steganography. Alice carefully constructs an image that appears to be an innocent cat photo, but embeds multiple messages inside such that Oscar can extract one message from Alice, Trent can extract another message from Alice, but Oscar and Trent (assuming they don't collaborate) can't even detect that any other message exists in the image. Can one of the multiple-message encoding techniques be adapted to solve this problem? – David Cary Sep 27 '14 at 16:06
• Thanks, David. I glanced at the paper, and it looks to me like it is not closely related to my problem. There is a big difference between a keyspace of size 2 and a keyspace of size $2^{256}$! – gmr Sep 28 '14 at 5:40
• OK, so maybe I'm not seeing the issue here, but it seems to me you could accomplish this pretty trivially. Suppose set(k,v) hashes k (up to 256-bit) into a 512-bit value (to avoid the birthday problem). Then store (hash(k), v) as a key-value pair in an ordered list. Lookup would be O(log(num_k_ever_set)). You could even encrypt v with different hash of k in order to make it indistinguishable as well. Am I missing the core issue here? – Reid Rankin Oct 1 '14 at 22:06
• 1. Are you looking for a history-independent data structure? I suspect that's the term used in the literature for this concept. There is lots of work in the crypto literature on history-independent data structures for various purposes. 2. What does the attacker get to see? Does the attacker only get to see the state of the data structure after all get/set operations have completed? Or can he see its state at various points along the way? – D.W. Oct 4 '14 at 5:18
• You could consider variations, but in the question as posed 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. – gmr Oct 4 '14 at 18:36

I'm looking forward to reading other answers -- a structure with these properties would be very useful for plausibly deniable encryption.

Perhaps something like this might be adequate:

// untested pseudocode
initialize():
global_current_index = 0
global_array = []
for each word in a dictionary of plausible words:
set( word, get_random_value() ) // dummy data

set(k,v):
// would the winner of the [password hashing competition][2] be overkill
// for this one-way function?
tag = one-way-function( k )
ciphertext = encrypt( key=k, data=v )
location = binary_search( global_array, key=tag )
// forget and overwrite old value if it exists; otherwise append new value
if not_found(location):
location = global_current_index
global_current_index = global_current_index + 1
global_array[location] = (tag, ciphertext)
dummy_k = get_random_value()
tag = one-way function( dummy_k )
ciphertext = encrypt( key=dummy_k, data=get_random_value() )
global_array[global_current_index] = (tag, ciphertext) // dummy data
global_current_index = global_current_index + 1
sort( global_array )

get(k):
tag = one-way-function( k )
location = binary_search( global_array, key=tag )
if not_found(location):
log( "k:" + k + "not detected: unauthorized guessing ?" )
return get_random_value()
else:
ciphertext = global_array[ location ]
plaintext = decrypt( key=k, data=ciphertext)
return plaintext


Space complexity: After the initial dummy dictionary, the size of the array increases by 2 entries each time set(k,v) is called with some new unique k value -- one real entry and one dummy entry. Each entry is relatively small -- the size of the encrypted v value (perhaps exactly the same length as the plaintext v value with classic deterministic encryption algorithms, or perhaps a little longer to handle an IV, padding, etc) plus the size of the tag entry (perhaps 256 bits if we use SHA256() as the one-way function).

Time complexity: get() uses a binary search, so it's O(n ln n) where n is the number of previous calls to set.

set also uses a binary search, so it has the same O(n ln n).

If an attacker get a single copy of this array of size N and knows you've been using this algorithm, he knows you've stored somewhere between 1 entry of actual data -- and overwritten it N times -- up to at most N/2 entries of actual data.

However, if you are using a non-broken one-way function, and a non-broken encryption routine, then it seems difficult to extract what data you've stored or what keys you stored them under without brute-force guessing.

This structure does leak a lot of data about what keys you've never used -- the attacker can make a guess, and if the one-way-function of that guess is not stored as a tag in the array, then the attacker knows you've never stored anything under that guess.

On the other hand, if you know ahead of time what guesses the attacker might make, and you've pre-loaded them in the "dictionary of plausible words", then the attacker might not be tell if you've stored something under that guess or not.

• If I understand correctly, you are basically proposing the special case solution I gave in the first part of my answer with the added element that we seed the data structure with some fake data. Is that right? (It doesn't take account of the dummy_k thing or the fact that the get routine seems to be trying to do something sneaky by returning a random value even though the threat model is that the attacker has full access to the table.) Anyway, seeding the data structure with fake data might add security in some applications, but it doesn't really help with the full version of the problem. – gmr Sep 29 '14 at 5:54
• @gmr: yes, very similar to your solution, except this proposal doesn't require decrypting the 'k' value and checking if the decrypted 'k' value matches the current 'k' value. So this proposal apparently runs a little faster. – David Cary Sep 29 '14 at 13:03

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.

• +1. And thank you for making "Is deniable error-correction possible?" a separate question. – David Cary Sep 29 '14 at 13:39
• If the person writing data could keep track of exactly what key,value pairs he has written so far (in some in-RAM structure that the attacker, and hence the reader, won't have access to once the computer is shut down), then perhaps the surprising-to-me dirty paper coding approach could be used -- rather than "most recent value wins" every collision, sometimes "let the older value win this collision" is better when there is enough error correction that the new value can still be recovered from other, non-colliding bits. – David Cary Sep 29 '14 at 14:50
• Dirty paper coding sounds like a really interesting concept, though the Wikipedia page does not explain it very well, and googling around I could not find any explanation written at a level I could understand. I don't see how it would help with my problem, but that might just be because I don't understand it very well. As for the more general idea of sometimes letting the older value win, that does seem like an interesting thing to consider; conceivably just letting the older value win with chance x, where x might depend on how full the table is, could improve utilization. – gmr Sep 29 '14 at 18:31

You can create a lossy version of the data structure using a hash table. If the $k$ values are not uniformly randomly distributed, you would initially hash them $k' = H(k)$ and use that as $k$ below.

Initialize the table of size $N$ with random data. When inserting $(k,v)$, encrypt $v$ using $k$ as the key with some symmetric encryption algorithm $E_k(v)$. Then write that ciphertext into the table position $k \mod N$.

Now you can query the key $k$ using $D_k(x)$, where $x$ is the data in the position $k \mod N$. That always returns some data, so an attacker wouldn't know if it was previously inserted or not. (This has to be the case for the encryption algorithm, so many padding modes wouldn't work. Any unauthenticated stream cipher would.)

However, if two $k$ values collide, the second $(k',v')$ will overwrite the first value $v$ with garbage data. You can avoid this only by preallocating a large enough hash table that collisions are unlikely. I.e. if you need it to handle $2^n$ values without collision, you would need it to be larger than $2^{2n}$ items – how much larger depending on how unlikely collisions must be.

I don't see a way to extend this approach to a non-lossy/probabilistic data structure.

The choice of where to find the value in memory must only depend on $k$, since it has to return the same item even if every other item in the data structure has been changed. There can't be any way to verify the chosen item was the correct one either (like using MAC-then-encrypt) or else an attacker can test which $k$ have not been inserted. This means anything that needs comparisons, like trees or hash table collision resolution, won't work.

• Thank you. This answer is not satisfying to me, but it gave me ideas that led me to what I think is a full solution to my problem. I will try to write it up as an answer tomorrow in case anyone else is interested. (Maybe not since the question got zero votes.) – gmr Sep 23 '14 at 9:01
• @gmr, I'd like to see it. The reason I haven't voted has more to do with lack of clarity than anything else. – otus Sep 23 '14 at 11:41
• OK, so actually it is harder than I thought. Your solution has three drawbacks: it's probabilistic, the approximate number of keys must be known in advance, and it requires quadratic space (with a high constant if you want a vanishingly small probability of error). The first two drawbacks seem unavoidable, though I don't have any proof that they are. The third I think I can eliminate if a certain kind of error-correcting codes exist. Basically, the codes must be indistinguishable from random bits. Do you know if that is possible? – gmr Sep 23 '14 at 19:19
• @gmr, you should be able to get an indistinguishable ECC from any ECC using suitable encryption (with the key). However, unless you have a significantly different approach, I think every time you halve the table size you double the need for ECC. – otus Sep 23 '14 at 19:41
• I think my approach is different from what you are thinking, but I would need the ECC to be indistinguishable (with high probability -- there can be some bit strings that are obviously not ECC codes) even to someone in possession of the key. – gmr Sep 23 '14 at 19:53