On the section 4.2, page 10, of the paper Order-Preserving Symmetric Encryption, the authors define two subroutines: the first one is called $HGD$ and the second one is $GetCoins$.
I have doubts about both, but I am mainly interested on the first.
It is said that
The first, denoted $HGD$, takes inputs $D$, $R$, and $y \in R$ to return $x \in D$ such that for each $x^∗ \in D$ we have $x = x^*$ with probability $P_{HGD}(x−d; |R|, |D|, y−r)$ over the coins of $HGD$, where $d = min(D)−1$ and $r = min(R)−1$.
So, my questions are the following:
1 - What does "over the coins of $HGD$" mean?
2 - Since $D$ is a set, it does not have repeated elements, so, the probability of $x$ being equal to $x^*$ is $\frac{1}{|D|}$, isn't it? Well, I don't understand how can I fix a element $x$ in $D$ such that the probability of any other element being equal to $x$ follows a hyper-geometric...
Any help will be appreciated.