6
$\begingroup$

In a certain function mapping like this,

$x \xleftarrow{\$} \{0,1\}^k$

(Lecture Notes on Cryptography by S. Goldwasser and M. Bellare, page 18)

I fail to understand what exactly does this \$ sign mean. This has been put here without any explanation or further elaboration.

It may be very trivial or may be very silly of me asking it like this, but I want to understand what is means.

Google search (function, dollar, arrow) has not returned any result.

http://en.wikipedia.org/wiki/List_of_mathematical_symbols does not mention anything as well.

$\endgroup$
1
  • $\begingroup$ Good point, indeed. $\endgroup$
    – Julien
    May 19, 2013 at 14:57

3 Answers 3

Reset to default
10
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Nice find. Surprised no one pointed this out to them before $\endgroup$
    – muzzlator
    May 19, 2013 at 14:38
  • $\begingroup$ I guess mistakes like these happen easily with lecture notes. $\endgroup$
    – Samuel
    May 19, 2013 at 14:40
  • $\begingroup$ @Samuel Thanks a lot, I have not progressed that far. $\endgroup$
    – Masroor
    May 19, 2013 at 14:40
  • $\begingroup$ @Samuel, now I'm curious. Please, post here his definition for the symbol. $\endgroup$
    – Sigur
    May 19, 2013 at 14:43
  • 4
    $\begingroup$ @Sigur That page (63) mentions, We denote by $K\xleftarrow{\$}\cal{K}$ the operation of selecting a random string from $\cal{K}$ and naming it $K$. So, the particular function under question, $x\xleftarrow{\$}\{0,1\}^k$, means that binary string $x$ of length $k$ is generated by some random function. $\endgroup$
    – Masroor
    May 19, 2013 at 15:33
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.