Understanding the definition of HGD

Question

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.

Answer 1

1. In cryptography it is common to reason about the probability of an event in the probability space of all the random choices made (i.e. the random bits generated) during an algorithm's execution. So, in this description, "over the random coins of HGD" means the probability is computed over the probability space defined by the random bits used during HGD sampling.
2. You are, I think, confused here by the difference between the uniform and hypergeometric distributions. If the sampling is uniform, the probability of the sample $x$ being equal to any other particular $x^*$ is exactly $\frac{1}{|D|}$. However, the sampling here is actually done according to the hypergeometric distribution, so the probability of the sample $x$ being equal to some $x^* \in D$ is exactly $P_{HGD}(x−d;|R|,|D|,y−r)$.

The wording here is on the formal side, but the intuitive takeaway is that the distribution of the output of the HGD subroutine is hypergeometric. Think of it as a black box that takes in some arguments (and random bits) and spits out a sample from the right distribution.