Cryptography
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: 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?

## Solution

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