- notation probability order-preserving
- Updated Thu, 07 Jul 2022 14:34:58 GMT

I'm reading this PDF: https://link.springer.com/content/pdf/10.1007/978-3-642-01001-9_13.pdf about order preserving encryption functions and there's this on page 9 (or 232):

It's describing the formula for the probability distribution. So I guess it's saying that the probability distribution of some variable.

What is the dollar sign, the `<-`

and how do I interpret this `Pr`

?

In cryptography the notation of $x\stackrel{\\\$}{\gets}S$ (also sometimes seen as $x\gets_{\\\$}S$) means that $x$ is chosen uniformly at random from the set $S$. If an algorithm is on the right side of the $\stackrel{\\\$}{\gets}$ then it typically means that the algorithm is invoked and may use randomness, for algorithms the $\\\$$ is also sometimes omitted.

The stated probability should be read as "The probability that $f(x)\leq y\leq f(x+1)$ holds assuming that $f$ is drawn uniformly at random from the set of all order-preserving functions from the set $[M]$ to $[N]$".

External links referenced by this document: