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

Understanding this notation for the probability distribution of order preserving encryption

I'm reading this PDF: about order preserving encryption functions and there's this on page 9 (or 232):

enter image description here

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]$".