In the paper Multi-Signatures in the Plain Public-Key Model and a General Forking Lemma, the authors Bellare and Neven use notation which looks like left arrow with dollar sign above it.

Authors provide an explanation for one variable:

$s \overset{{\scriptstyle \$}}{\longleftarrow S}$ denotes the operation of assigning to $s$ an element of $S$ chosen at random

However, in this paper they use it with multiple variables like this:

$s_1, \ldots, s_N \overset{{\scriptstyle \$}}{\longleftarrow S}$

What is the definition of this notation? Can we chose dependent random variables for $s_i$? Do we must choose all variables $(s_1, \ldots, s_N)$ at once from the set $S^N$ with uniform distribution?

  • 5
    $\begingroup$ Personally, I'd probably read this as "sample a random element of S into $s_i$ independently", but I don't know for sure. $\endgroup$
    – SEJPM
    Jul 16, 2016 at 21:09
  • 1
    $\begingroup$ Note that uniformly choosing the individual $s_i$ independently as SEJPM suggests is equivalent to your interpretation of uniformly choosing tuples from $S^N$. $\endgroup$ Jul 16, 2016 at 21:23

1 Answer 1


$s_1, ..., s_N \stackrel{\$}{\leftarrow} S$

means coordinate-wise sampling:

$s_1 \stackrel{\$}{\leftarrow} S$

$s_2 \stackrel{\$}{\leftarrow} S$


$s_N \stackrel{\$}{\leftarrow} S$

  • $\begingroup$ This is standard notation that I've used myself $\endgroup$ Jul 17, 2016 at 22:31
  • $\begingroup$ Ok, but do you remember any other paper which uses this notation? $\endgroup$
    – Student20
    Jul 17, 2016 at 22:33
  • $\begingroup$ Well, since it's Mihir's style to use this notation, it's easy to find similar examples in other paper's of his; e.g. cseweb.ucsd.edu/~mihir/papers/id-multisignatures.pdf $\endgroup$ Jul 17, 2016 at 22:38
  • $\begingroup$ Oh-- hopefully not to belabor the point, but e.g. in this second paper I linked, see Page 5 (left column preceding Section 4). The variable X_i actually cannot be regarded as a random variable over the uniform distribution over its domain -- unless $\stackrel{\$}{\leftarrow}$ is interpreted as coordinate-wise sampling. $\endgroup$ Jul 18, 2016 at 0:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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