I've seen := used in several cryptography papers where the this symbol has been used instead of assignment operator ($ \leftarrow $ ) or equal sign (=), but never with an accompanying explanation. It's not exactly possible to search the precise meaning of operator ":= ". What is the exact meaning of this symbol in terms of mathematics in cryptography is concerned.
2 Answers
Lindell and Katz, in their book Introduction to Modern Cryptography, use;
$\leftarrow$ as possibly probabilistic process assignment.
Some others use $\stackrel{r}{\gets}$, $\stackrel{\\\$}{\gets}$, $\gets_{R}$, and $\gets_{\\\$} $
Actually, the $\gets_{\\\$}$ fairly common.
$:=$ for the deterministic process assignment.
In some context, the $\leftarrow$ can be the same as Lindell and Katz 's $:=$. This former is more common. In some contexts, it is $=$
$=$ for equality
- $\stackrel{def}{=}$ for defining a variable.
More on $\leftarrow$ and variants
When $X$ is a value, the $x \leftarrow X$ is used for deterministic assignment, and
When $X$ is a probability distribution, the $x \leftarrow X$ is used for sampling.
When $X$ is a set, the $x \leftarrow_R X$ is used to denote sampling from the uniform distribution over the set $X$.
Note:
- In reading books, one needs to check the existence of the notation page(s) or the notation section. Many good books have a section like L&K's Index of Common Notation section (page #533 in the second edition).
- In the articles, the authors usually define them where they first occur, therefore, look for the first occurrence of the symbol.
-
1$\begingroup$ A quick comment about $:=$ versus $\leftarrow$ for deterministic assignement: from my experience, the second is actually much more commonly used in crypto-related papers (though the first one remains pretty common). In fact, $x \leftarrow X$ will often simultaneously mean deterministic assignment (when $X$ is a value) or sampling (when $X$ is a probability distribution); symbols such as $\leftarrow_R$ will then be used when $X$ is a set, to denote sampling from the uniform distribution over this set. $\endgroup$ Dec 10, 2020 at 10:52
-
1$\begingroup$ A second comment: many cryptographers are not programmers or particularly familiar with the notation semantics. This means that, although it is not a proper choice, $=$ is also often used (in a number of papers) for deterministic assignment. Knowing this might help not getting confused when this happens. Another point, the $=$ symbol with "def" on top is often not used, and with some abuse of notation, $\leftarrow$ is used for implicit definition of the variable (followed by a deterministic assignment or a sampling from a distribution). E.g.: "$\mathcal{A}$ samples $x\leftarrow \mathcal{D}$". $\endgroup$ Dec 10, 2020 at 10:58
-
1$\begingroup$ I don't know how thorough you're trying to be with this answer, but $\gets_\$$ is also fairly common for probabilistic assignment. $\endgroup$– MaeherDec 10, 2020 at 11:07
-
$\begingroup$ @GeoffroyCouteau thanks. updated the answer according to your valuable comments. $\endgroup$– kelalakaDec 10, 2020 at 11:38
-
There is not a single standard for pseudocode. The :=
operator is the assignment operator from Pascal, a programming language which was in widespread usage in the 1970s and 1980s, especially for teaching purposes. Many academics have thus been exposed to Pascal and remember it. In Pascal, the equality comparison is =
, which matches mathematical practice.
By comparison, the C language (and languages that build on its syntactic conventions, including Java, C# and Javascript) uses =
for assignment, thus requiring a distinct operator (==
) for equality comparison.
Nowadays, article writers tend to use the left arrow ($\leftarrow$) for assignment (or even a right arrow, with the destination on the right), which is more intuitive for the reader and does not require background knowledge of Pascal, but it is less easy to type on a keyboard. Old-timers, who know Pascal and wrote articles before the generalization of LaTeX, tend to favour the :=
operator.
-
3$\begingroup$ Before Pascal
:=
was used for assignment(note) (and=
for equality) in algol, which was semi-officially intended to be the standard language for academic publication, and was in fact widely but not universally used for that. (note: with the proviso that algol68, which invented bizarre new names for almost everything, calls assignment 'assignation'.) $\endgroup$ Apr 24, 2016 at 8:15
":=" and "=" often mean the same.
$\implies$ No, it does not mean the same thing. = is for the equality, while := is for the definition. This is semantically very different. Do not mistake it with the use of = in for example C or Java (which is why in these languages we have == for equality). $\endgroup$