# Building index for Bloom filter using cryptographic hash functions

I want to apply this secure index scheme for my Bloom filter, i.e. to use secret keys to insert items into the filter. In the paper to insert a word $$w$$ to the Bloom filter, they use a set of $$r$$ keys $$\{k_1,...,k_r\}$$ and calculate $$r$$ values $$h_1 = h(w,k_1), h_2(w,k_2),...,h_r = h(w,k_r)$$ as the bit positions. Actually I don't quite understand how the bits are really obtained from the hash values, let's say my filter has 1024 bits, should I use $$h_r \% 1024$$? And now since I want to reduce the computation, I use only 1 key $$k$$ and divided the value $$h(w,k)$$ to $$r$$ chunks of 10 bits. The value of each chunk will serve as 1 index. Will this scheme make my bits less uniformly distributed?

• If you could provide more information about what is actually done in that paper and what you want to change, this would make this question is easier to answer. In general: If there are several keys used, and that has a reason and chances are really good that you break the security of the scheme if you just use one key.
– tylo
Apr 7, 2017 at 7:59
• This scheme uses a different key for each word in the index. If you only use one key you might get away with a much simpler scheme like encrypting your index. Can you provide more details on your attack model? Apr 7, 2017 at 8:36
• I added more details to my question. Apr 10, 2017 at 3:11

At a glance, it seems that the paper you linked to does not actually specify how to convert the PRF outputs to Bloom filter indexes. As far as I can tell, however, any scheme that does not introduce a significant bias should be fine. For example, if the Bloom filter array size $$m = 2^b$$ is a power of two, simply taking the first (or last, or any) $$b$$ bits of the PRF output should be fine. For non-power-of-2 array sizes, reducing the $$s$$-bit PRF output modulo $$m$$ should also be acceptable, at least provided that $$m \ll 2^s$$.

Indeed, the method used to convert the PRF output to the Bloom filter array index should not have any effect on security, since the conversion is only applied to PRF outputs which, by definition, are effectively indistinguishable from random. However, obviously, a highly biased conversion method could reduce the entropy of the index distribution, and thus increase the false positive rate.

BTW, looking at the scheme presented in the paper, the use of $$r$$ separate PRF invocations seems somewhat inefficient, both in terms of processing speed and in terms of the size of the "trapdoor" representation. As far as I can see, a more efficient variant of the scheme would look something like this:

Let $$m = 2^b$$ be the array size and $$r$$ the per-element index set count of the underlying Bloom filter, and let $$s$$ be an arbitrary security parameter (say, $$s = 256$$). Choose the PRF families $$f_T : \{0,1\}^* \times \{0,1\}^s \to \{0,1\}^s$$ and $$f_B : \{0,1\}^* \times \{0,1\}^s \to \{0,1\}^{rb}$$ (where, as in the paper, the second argument denotes the key input).

For example, for $$s = 256$$, we could choose $$f_T(w,k) = \text{HMAC}_{\text{SHA256}, k}(w)$$ and define $$f_B(d,k)$$ as the first $$rb$$ bits of $$\text{HMAC}_{\text{SHA256}, k}(1 \,\|\, d) \,\|\, \text{HMAC}_{\text{SHA256}, k}(2 \,\|\, d) \,\|\, \dots \,\|\, \text{HMAC}_{\text{SHA256}, k}(\lceil rb / 256 \rceil \,\|\, d),$$ where the numeric prefixes are all padded to some fixed length. Alternatively, we could just instantiate both $$f_T$$ and $$f_B$$ with KMAC (possibly with different customization inputs, although that shouldn't actually be necessary).

Define:

• $$\textsf{Keygen}(s)$$: Choose a random $$s$$ bit master keys $$K_{priv}$$ and return it.

• $$\textsf{Trapdoor}(w, K_{priv})$$: Given an arbitrary word $$w$$, output its trapdoor representation $$T_w = f_T(w, K_{priv})$$

• $$\textsf{BuildIndex}(D, K_{priv})$$: Given a document $$D$$ with unique ID $$D_{id} \in \{0,1\}^*$$ and a list of distinct words $$(w_1, w_2, \dots, w_t)$$, initialize the $$m = 2^b$$ bit Bloom filter array $$B$$ to all zeros and, for each word $$w_i$$:

1. Compute the trapdoor token $$x_i = f_T(w_i, K_{priv})$$.
2. Compute the $$rb$$ bit codeword $$f_B(D_{id}, x_i)$$ and split it into $$r$$ indices $$(y_{i,1}, y_{i,2}, \dots, y_{i,r})$$ of $$b$$ bits each.
3. Set the bits $$y_{i,1}, y_{i,2}, \dots, y_{i,r}$$ of the Bloom filter array $$B$$ to $$1$$.

Finally, to hide the number of distinct words in the document, pick (with replacement) $$(u-t)r$$ additional random bits of the Bloom filter array $$B$$, where $$u$$ is some publicly known upper bound on the number of words in the document $$D$$, and set them to $$1$$. Output $$(D_{id}, B)$$ as the index of the document $$D$$.

• $$\textsf{SearchIndex}(T_w, D_{id}, B)$$: Compute the $$rb$$ bit codeword $$f_B(D_{id}, T_w)$$ and split it into $$r$$ indices $$(y_1, y_2, \dots, y_r)$$ of $$b$$ bits each. Output $$B_{y_1} \land B_{y_2} \land \dots \land B_{y_r}$$, where $$B_i$$ denotes the $$i$$-th bit of the Bloom filter array $$B$$, and $$\land$$ denotes bitwise AND.

With these modifications, the "trapdoor" tokens are only $$s$$ bits long (rather than $$sr$$ bits as in Goh's original scheme), and computing them requires only one PRF invocation. Similarly, e.g. using the HMAC-based construction of $$f_B$$ above, an insertion or a lookup of each word requires only $$\lceil \tfrac{rb}\ell \rceil$$ HMAC invocations, where $$\ell$$ is the HMAC output length, rather than $$r$$ invocations as in the original scheme. Since typically $$b \ll \ell$$, this also saves considerable computation time.

BTW, note that this "double PRF" design looks quite similar to the "extract and expand" paradigm used in some key derivation functions like HKDF. Indeed, we could implement $$f_T$$ as HKDF-Extract (which is really just HMAC) and $$f_B$$ as HKDF-Expand (which is similar to the simple concatenated HMAC scheme described above). In effect, the client wishing to query the index for a word extracts a pseudorandom key (PRK in HKDF terminology, trapdoor in Goh's terminology) from their private key using the query word as the salt, and then sends this PRK to the index server, which expands it into a distinct Bloom filter index set for each document (using the document ID as the "context specific information" to make the index sets distinct).

Also note that the scheme described above can be modified to support hierarchical indexing, arbitrary updates, occurrence search, IND2-CKA security and/or boolean (or limited regexp) queries in exactly the same ways as Goh's original scheme. However, the shortened trapdoor tokens do prevent the use of the "heuristic security increase" technique (i.e. sending only part of the token to the server to hopefully disguise the word being queried) described in section 5.1 of the paper.

Of course, I cannot guarantee that I haven't made some silly mistake above that somehow compromises the security of the modified scheme, nor have I carried out a detailed security analysis like the one given for the original scheme in the paper. All I can say is that, as far as I can tell, it looks to me like it should be just as secure as the original scheme.

edit: complete re-write

Actually I don't quite understand how the bits are really obtained from the hash values, let's say my filter has $1024$ bits, should I use $h_r \% 1024$?

Regarding the modulus, yes, that's right. If the output of the function $h$ is much larger than the length of the Bloom filter. If you take $h_r(x) \mod l$ for length $l$ of the bitarray $a$, then those elements are (almost) uniformly distributed over all indices of the array.

However, $h$ is not a cryptographic hash function - the security definition of cryptographic hash functions does not fit with the required properties. From the abstract "We also develop an efficient ind-cka secure index construction called z-idx using pseudo-random functions and Bloom filters". A PRF is related to hash functions, and HMAC is one commonly used construction for PRFs, but they are not the same.

And now since I want to reduce the computation, I use only $1$ key $k$ and divided the value $h(w,k)$ to $r$ chunks of $10$ bits. The value of each chunk will serve as $1$ index. Will this scheme make my bits less uniformly distributed?

To answer the question you stated: No, the almost-uniform distribution of each $10$ bit block doesn't change. To be more precise: The output of a PRF is indistinguishable from a truly random value over the output domain. If we consider the range of the PRF to be $\{1,2,2^x - 1\}$ for some integer $x$ and its binary representation, then we can consider the ouput bits to be uniformly distributed and statistically independent (otherwise it would not be indistinguishable from a random value).

Then splitting the output like you suggested works - as long as your length is a power of $2$. Otherwise the operation modulo $l$ (for length $l$ of the array) might not be (almost) uniformly distributed any more, because your individual parts are not much larger than the length of the array. One simple solution would be to consider the arithmetic encoding with base $l$ instead, and then use the $l$-ary digits as values in the correct range.

However, the question you should be asking is: Does this break the security?

And the answer to that is: It depends. First you need to ensure that the assumptions about the distributions are actually met by your choice of parameters including the array-length, output length of the PRF, number of PRFs you need, etc. But a uniform distribution is only necessary and might not be sufficient for the security of the scheme. If you extract multiple values from a single PRF output, then those values are not independent of each other unlike using two different PRFs or a PRF with different keys, and that might make a difference in the security proof of that paper. But I don't think this can be answered without knowing the scheme and its proof in detail.

• You're right about it being easy to generate "trapdoor tokens" that produce every possible bit pattern if the Bloom filter is small enough, but as far as I can tell, that doesn't actually compromise the IND-CKA security the scheme is supposed to satisfy. Of course, in practice, such tiny Bloom filters would typically have impractically high false positive rates. May 10, 2017 at 18:42
• @IlmariKaronen I rewrote the answer (started yesterday already, and didn't notice you wrote one yourself). But your answer does provide a lot more detail than mine.
– tylo
May 11, 2017 at 11:52