I am a graduate student interested in searchable encryption research. I carefully read the Secure Indexes paper published in 2004, and I was confused about the IND-CKA, the game-based security definition.
In setup phase, the definition lets the adversary $A$ to send the collection of subsets $S^*$ to the challenger $C$, and the challenger will return all the indexes with their associated subsets. And in the challenge phase, the adversary will pick a subset $V_0$ which belongs to $S^*$ and generate another subset $V_1$ from the original word set $S$, and give both $V_0$ and $V_1$ to the challenger. The challenger then randomly picks one subset and generates the index and send the index to adversary.
What confused me is that, since the index of $V_0$ was already known to the adversary (in setup phase), the adversary can learn which subset ($V_0$ or $V_1$) was picked by $C$ in challenge phase as long as the
BuildIndex() function is deterministic. (If the index given from $C$ is same as the associate index of $V_0$ given in setup phase, the adversary will guess $0$, otherwise guess $1$)
Of course, the
BuildIndex() of Z-Index involves random inserting, but it dose not prevent the adversary winning the guess with the probability greater than
$1 \over 2$ + epsilon.
I might have some misunderstanding, and I have stacked here for several days. Thanks a lot!!