6
$\begingroup$

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?

$\endgroup$
  • 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 '16 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$ – CodesInChaos Jul 16 '16 at 21:23
4
$\begingroup$

$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$

$\endgroup$
  • $\begingroup$ This is standard notation that I've used myself $\endgroup$ – Daniel Apon Jul 17 '16 at 22:31
  • $\begingroup$ Ok, but do you remember any other paper which uses this notation? $\endgroup$ – Student20 Jul 17 '16 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$ – Daniel Apon Jul 17 '16 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$ – Daniel Apon Jul 18 '16 at 0:25

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.