Notations & Definitions

This page is a glossary for notation and concepts present in the documentation.

Sets and Groups #

$\mathbb{Z}$ is the set of integers, $\{\dots, -2, -2, -1, 0, 1, 2, \dots\}$ .
$\mathbb{N}$ is the set of integers greater than or equal to 0, $\{0,1,2,\dots\}$ .
$[n]$ is the finite set of integers $\{1, \dots ,n\}$ .
$\mathbb{Z}_n$ are the integers modulo $n$ , a set associated with the equivalence classes of integers $\{0,1, \dots ,n−1\}$ .
$\mathbb{Z}_n^∗$ is the multiplicative group of integers modulo $n$ : an element $e$ from $\mathbb{Z}_n$ is in $\mathbb{Z}_n^∗$ iff $\gcd(e,n)=1$ , that is $\mathbb{Z}_n^* = \{e \in \mathbb{Z}_n: \gcd(e, n) = 1 \}$ . When $n$ is prime, then $\mathbb{Z}_n^* = \{1, \dots, n-1\}$ .
$\mathbb{F}_p$ is the finite field of order $p$ ; when $p$ is a prime number, these are the integers modulo $p$ , $\mathbb{Z}_p$ ; when $p$ is a prime power $q^k$ , these are Galois fields.
$|S|$ is the order of a set $S$ , i.e., its number of elements. For example, $|\mathbb{Z}_n^*| = \Phi(n)$ , and for a prime $n$ , $|\mathbb{Z}^*_n| = n - 1$ .
$\mathcal{L}$ : An evaluation domain, typically used in FFT-based polynomial commitment schemes (e.g., domains of size a power of two).
$\mathcal{R}$ : A relation or constraint system, such as an R1CS (Rank-1 Constraint System).
$\mathsf{RS}$ : Reed-Solomon codes.

$\bm{a} \in \mathbb{Z}_q^n$ is a vector $(a_1, \dots ,a_n)$ with $a_i \in \mathbb{Z}_q$ for all $i$ .
$c \cdot \bm{a}$ denotes the scalar product $(c \cdot a_1, \cdots ,c \cdot a_n)$ .
$\lang \bm{a}, \bm{b} \rang$ denotes the inner product $\sum_{i = 1}^n = a_i \cdot b_i$

In protocol specifications, we will often need to uniformly sample elements from sets. We will use the following notation:

$x \stackrel{\$}{\leftarrow} X$ , where $x$ is uniformly sampled from the set $X$ .

We will use assertions in protocol descriptions. When the assertions do not hold, the protocol must abort to avoid leaking secret information.

$a\stackrel{?}=b$ , requires $a=b$ , and aborts otherwise
$a \stackrel{?}> b$ , requires $a>b$ , and aborts otherwise
$a \stackrel{?}\in S$ , requires that $a$ is in the set $S$ , and aborts otherwise.

$\mathsf{Hash}(\cdot)$ is a cryptographically secure domain-separated hash function.
$\mathsf{Hash}(\cdot)[0:k]$ is a cryptographically secure domain-separated hash function with specific output-size of kk-bits.

$\deg(f)$ : The degree of a polynomial $f$ , i.e., the highest exponent with non-zero coefficient in $f$ .
$\log x$ : The logarithm of $x$ (base context-dependent, often base 2 in crypto).
$\max(x_1, \dots, x_n)$ : The maximum of a set of values.
$\min(x_1, \dots, x_n)$ : The minimum of a set of values.
$\gcd(n,m)$ is the positive greatest common divisor of integers $n$ and $m$ ; when $\gcd(n,m)=1$
, $n$ and $m$ are said to be coprime.
$\varphi(n)$ is Euler’s totient function; for $n \ge 1$ , it is the number of integers in $\{1, \dots ,n\}$ coprime with $n$ .

A Montgomery form of $a \in \mathbb{Z}_N$ is represented by $\bar{a} = aR \mod N$ , given a modulus $N$ and a Montgomery radix $R$ such that $\gcd (N, R) = 1$ .

Last updated 2 months ago