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?
EDIT: added more information
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$:
  
  
  Compute the trapdoor token $x_i = f_T(w_i, K_{priv})$.
  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.
  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.