What does this dollar sign over arrow in function mapping mean?

This is standard cryptographic notation. There are three ways of writing it that are customary in cryptography:

$$x \xleftarrow{\$} A$$

$$x \xleftarrow{R} A$$

$$x \in_R A$$

All indicate that x is a random variable chosen from the finite set A using the uniform distribution. As example papers, see Provisions: Privacy-preserving proofs of solvency for Bitcoin exchanges and A Proof of Security of Yao’s Protocol for Two-Party Computation.


It is not standard notation as far as I know. I searched for dollar signs in the document, and found that he defines the notation 45 pages later on page 63.


It is standard cryptographic notation, but the origin might not be immediately clear.

In formal cryptographic papers one reasons over Turing machines. For example, probabilistic algorithm $\mathcal{A}$—which can be described by some Turing machine $M$—has not only an input tape, but a random tape as well. One says that this (binary) random tape is generated by flipping (fair) coins. (Sometimes papers actually say something like “the probability is taken over the coins of the encryption algorithm”.) The notation of the dollar sign (\$) is a nod towards these coin flips, indicating (uniform) randomness.

Notation such as $b' \buildrel\$\over\gets \mathcal{A}(1^\lambda)$ is not uncommon, indicating that a probabilistic algorithm $\mathcal{A}$ outputs $b'$ (note that this output is not necessary unique) on input $1^\lambda$ (usually $\lambda$ denotes the security parameter, e.g., the bit length of a key. The key length is written in unary notation here, which is again related to the polynomial running time of the algorithm in terms of the security parameter.)

The step to use the ‘dollar sign notation’ for sets is now easily made.

Tags:

Functions