Probability and Sampling Notation in Lattice Cryptography

Lattice cryptography is full of randomness: secrets, errors and signature masks are all sampled. This page lists the notation for that randomness as it appears on this site. Each row says how to read the symbol, what it means here, and which chapters use it. Two things trip up most readers: the arrow $\leftarrow$ means two different things, and Gaussian widths are quoted in two different units. Both are covered below.

Sampling and assignment

Symbol	Read as	Meaning on this site	Example	Used in
$x \leftarrow S$ `x \leftarrow S`	“x is sampled uniformly from S”	When the right side is a finite set, draw an element uniformly at random.	$a \leftarrow \mathbb{Z}_q^n$ : a uniformly random vector mod $q$	2.3
$x \leftarrow \chi$	“x is drawn from χ”	When the right side is a distribution, draw from that distribution.	$e \leftarrow \chi$ : an error sampled from the error distribution	2.3, 2.5
$x \leftarrow x + 1$	“x becomes x + 1”	In pseudocode the same arrow is plain assignment, with no randomness.	$k \leftarrow k + 1$ in the LLL loop	4.1, 4.2, 2.2
$x \sim \mathcal{D}$	“x is distributed as D”	A statement about the distribution of $x$ , often used in place of the sampling arrow.	$(s_1, s_2) \sim D_{\Lambda + H(m), \sigma}$	4.5

Many papers write $x \xleftarrow{\$} S$ or $x \leftarrow U(S)$ to make uniform sampling explicit. This site does not use either form; read a plain arrow into a set as uniform sampling. Also note that $\sim$ sometimes means “roughly”, as in $\sim 2^{29}$ on the lattice reduction page; the context tells you which.

Distributions

Symbol	Read as	Meaning on this site	Example	Used in
$\chi$ `\chi`	“chi”	The error distribution of an LWE instance: any distribution of small integers mod $q$ .	parameters $(n, q, \chi)$	2.3
$A_{s,\chi}$ `A_{s,\chi}`	“the LWE distribution for s and chi”	Pairs $(a, b)$ with $a$ uniform and $b = \langle a, s\rangle + e \bmod q$ , $e \leftarrow \chi$ .	$(a_i, b_i) \leftarrow A_{s,\chi}$	2.3
$D_{\mathbb{Z},\sigma}$ `D_{\mathbb{Z},\sigma}`	“discrete Gaussian over the integers with parameter sigma”	Each integer $x$ gets probability proportional to $e^{-x^2/(2\sigma^2)}$ . Here $\sigma$ is the standard deviation.	$\chi = D_{\mathbb{Z},\sigma}$ with $\sigma \ll q$	2.3, 2.5
$D_{\Lambda,s}$ , $D_{\Lambda,s,c}$	“discrete Gaussian over Λ with width s (and centre c)”	Each lattice point $v$ gets probability proportional to $\rho_{s,c}(v)$ . Here $s$ is a width, not a standard deviation.	$D_{\mathbb{Z},s}$ is the case $\Lambda = \mathbb{Z}$	1.4, 6.3, 4.5
$B_\eta$ `B_\eta`	“centred binomial with parameter eta”	Sample $2\eta$ random bits and return (sum of the first $\eta$ ) − (sum of the last $\eta$ ). Values lie in $\{-\eta,\dots,\eta\}$ , variance $\eta/2$ . The ML-KEM standard calls it $\mathrm{CBD}_\eta$ .	$B_2$ : $P(0) = 6/16$ , $P(\pm1) = 4/16$ , $P(\pm2) = 1/16$	3.1, 2.3, 3.4
$\{-\eta,\dots,\eta\}$	“integers from minus eta to eta”	A range of small integers. In ML-DSA the secret coefficients are uniform on it; in ML-KEM the same range is the support of $B_\eta$ , which is not uniform.	$\eta = 2$ : five values, each with probability 1/5 in ML-DSA	3.3, 3.4
$[-\gamma_1 + 1, \gamma_1]$	“integers from one minus gamma-one to gamma-one”	The range of the uniformly sampled ML-DSA signing mask $y$ .	$\gamma_1 = 2^{17}$ for ML-DSA-44	3.3

Gaussian functions and the two width conventions

The Gaussian function with width $s$ and centre $c$ is

\rho_{s,c}(x) = \exp\!\left(-\pi \frac{\|x - c\|^2}{s^2}\right), \qquad \rho_s = \rho_{s,0}, \qquad \rho_s(S) = \sum_{x \in S} \rho_s(x).

Read $\rho_s$ as “rho s”. The last form, the Gaussian mass of a set, is how the smoothing parameter is defined. A discrete Gaussian divides $\rho_{s,c}$ by the mass of the whole lattice so the probabilities sum to 1.

Two conventions describe how wide the bell is, and this site uses both:

Parameter	Density shape	Where on this site
width $s$	$\exp(-\pi x^2 / s^2)$	1.4, 6.3 ( $D_{\Lambda,s}$ , $\rho_s$ , $\eta_\varepsilon$ )
standard deviation $\sigma$	$\exp(-x^2 / (2\sigma^2))$	2.3, 2.2, 7.4, 3.4

They describe the same bell curve when

s = \sqrt{2\pi}\,\sigma \approx 2.5066\,\sigma.

The discrete Gaussian guide states the same relation the other way round: per-coordinate standard deviation $s/\sqrt{2\pi}$ . For a discrete Gaussian the true standard deviation equals $s/\sqrt{2\pi}$ only approximately, but the error is negligible once $\sigma$ is about 1 or more. When a paper quotes “a Gaussian of parameter 3.2”, check which formula it uses before comparing numbers.

Worked example: $D_{\mathbb{Z},\sigma}$ with $\sigma = 1$

Take standard deviation $\sigma = 1$ , so width $s = \sqrt{2\pi} \approx 2.5066$ . Summing $\rho_s(x)$ over all integers gives a normaliser of about 2.5066, and dividing gives these probabilities:

$x$	0	±1	±2	±3	±4
$P(x)$ (each sign)	0.3989	0.2420	0.0540	0.0044	0.0001

So a sample lands in $\{-1, 0, 1\}$ with probability 0.883 and in $\{-2,\dots,2\}$ with probability 0.991, and the standard deviation of the discrete distribution is 1.0000 to four decimals. For comparison, $B_2$ from ML-KEM also has variance 1 but never leaves $\{-2,\dots,2\}$ .

Smoothing parameter

Symbol	Read as	Meaning on this site	Example	Used in
$\eta_\varepsilon(\Lambda)$ `\eta_\varepsilon(\Lambda)`	“eta epsilon of lambda”	The smallest width $s$ with $\rho_{1/s}(\Lambda^* \setminus \{0\}) \le \varepsilon$ . Above it, a Gaussian of width $s$ reduced modulo $\Lambda$ is almost uniform, with the error controlled by $\varepsilon$ .	samplers need $s \geq \eta_\varepsilon(\Lambda)$	1.4, 6.3
$\varepsilon$	“epsilon”	A small error tolerance. In $\eta_\varepsilon$ it bounds leftover Gaussian mass. On 3.4 the letter $\epsilon$ is instead a distinguishing advantage.	$T = 1/\epsilon^2$ repetitions	1.4, 3.4

Probabilities, expectations and security levels

Symbol	Read as	Meaning on this site	Example	Used in
$\Pr[E]$ , $P[E]$	“the probability of E”	Probability of an event. Both spellings appear; they mean the same.	$\Pr[\text{failure}] < 2^{-139}$	3.4, 4.3
$\mathbb{E}[X]$ , $\mathrm{Var}(X)$	“expected value of X”, “variance of X”	Mean and spread of a random quantity. Not written as formulas on this site, but implied whenever a norm is estimated.	$\mathrm{Var}(B_\eta) = \eta/2$	—
$\\|e\\| \approx \sigma\sqrt{n}$	“the norm of e is about sigma root n”	The typical length of a vector of $n$ independent errors with standard deviation $\sigma$ : $\mathbb{E}[\\|e\\|^2] = n\sigma^2$ . A heuristic estimate, not a bound.	$n = 256$ , $\sigma = 1$ : $\\|e\\| \approx 16$	7.4, 2.2
$2^{-128}$	“two to the minus 128”	A probability so small it is treated as zero in practice. Security targets and failure rates are stated this way.	decryption failure below $2^{-139}$	3.4, 2.3, 2.6, 3.3
$\lambda$ (bits)	“lambda bits of security”	The security level: the best known attack costs about $2^\lambda$ operations. Unrelated to the successive minimum $\lambda_1$ , which always carries a subscript.	$\lambda = \lfloor 0.292\,\beta^* \rfloor$	3.4

Theory papers state the same idea asymptotically. A function is negligible, written $\mathrm{negl}(\lambda)$ , if it shrinks faster than every inverse polynomial in the security parameter; an event holds with overwhelming probability if its failure probability is negligible. This site quotes concrete numbers such as $2^{-128}$ instead.

Same symbol, different meaning

Symbol	Meanings on this site
$\leftarrow$	Random sampling (2.3); assignment in pseudocode (4.1, 4.2).
$\rho$	Gaussian function $\rho_s$ (1.4, 6.3); packing radius $\rho = \lambda_1/2$ (1.3, 1.4); a public random seed (3.1, 3.3).
$\sigma$ , $s$	Standard deviation versus Gaussian width; convert with $s = \sqrt{2\pi}\sigma$ . On 4.5, $D_{\Lambda + H(m),\sigma}$ names the Falcon sampler’s parameter $\sigma$ .
$\eta$	Smoothing parameter $\eta_\varepsilon$ (1.4); secret bound in ML-KEM and ML-DSA (3.1, 3.3); LLL size-reduction constant 0.501 (4.6).
$\varepsilon$ , $\epsilon$	Mass tolerance in $\eta_\varepsilon$ (1.4); distinguishing advantage (3.4); signs $\epsilon_i = \pm 1$ in sieving (4.3).
$\lambda$	Security level in bits (3.4); with a subscript, the successive minima $\lambda_i$ of a lattice (see 8.3).
$D$	A discrete Gaussian in $D_{\mathbb{Z},\sigma}$ and $D_{\Lambda,s}$ . On 2.5, $D_{\gamma_1}^\ell$ and $D_{\mathbb{Z}^m}$ denote the mask and target distributions of the signature, described there as uniform over a range.

Conventions we follow

An arrow into a set means uniform sampling; an arrow into a named distribution means sampling from it.
Gaussian widths written $s$ use $\exp(-\pi x^2/s^2)$ ; widths written $\sigma$ are standard deviations.
Probabilities are stated as concrete powers of two, such as $2^{-128}$ , rather than asymptotically.
A bare $\lambda$ is a security level in bits; $\lambda_1, \lambda_2, \dots$ are successive minima.

8.5 Probability and sampling

Sampling and assignment

Distributions

Gaussian functions and the two width conventions

Worked example: $D_{\mathbb{Z},\sigma}$ with $\sigma = 1$

Smoothing parameter

Probabilities, expectations and security levels

Same symbol, different meaning

Conventions we follow

Further reading

Sampling and assignment

Distributions

Gaussian functions and the two width conventions

Worked example: DZ,σD_{\mathbb{Z},\sigma}DZ,σ​ with σ=1\sigma = 1σ=1

Smoothing parameter

Probabilities, expectations and security levels

Same symbol, different meaning

Conventions we follow

Further reading

Worked example: $D_{\mathbb{Z},\sigma}$ with $\sigma = 1$