$\newcommand{\alicebob}{#1 & \ra{#2} & #3\\[-5pt]}$ $\newcommand{\bobalice}{#1 & \la{#2} & #3\\[-5pt]}$ $\newcommand{\alicework}{#1 & &\\[-5pt]}$ $\newcommand{\bobwork}{ & & #1\\[-5pt]}$ $\newcommand{\work}{#1 & & #2\\}$ $\newcommand{\allwork}{ & #1 & \\}$ $\newcommand{\aliceseparator}{-------&&\\}$ $\newcommand{\bobseparator}{&&-------\\}$ $\newcommand{\foo}{\phantom{\text{bigarrowfitsallthis}}}$ $\newcommand{\ra}{% \vphantom{\xrightarrow{asd}}% \smash{\xrightarrow[\foo]{#1}}% }$ $\newcommand{\la}{% \vphantom{\xleftarrow{asd}}% \smash{\xleftarrow[\foo]{#1}}% }$ $\newcommand{\z}{\mathbb{Z}_{#1}}$ $\newcommand{\zq}{\mathbb{Z}_\varq}$ $\newcommand{\zqs}{\mathbb{Z}_q^\ast}$ $\newcommand{\zps}{\mathbb{Z}_p^\ast}$ $\newcommand{\zns}{\mathbb{Z}_{#1}^\ast}$ $\require{action} \newcommand{\sampleSymb}{ {\overset{\$}{\leftarrow}} }\newcommand{\field}{\mathbb{F}_{#1}}\newcommand{\sample}{#1\sampleSymb\zq}\newcommand{\sampleGeneric}{#1\sampleSymb#2}\newcommand{\sampleInterval}{#1\sampleSymb\interval{#2}}\newcommand{\sampleRange}{#1\sampleSymb\range{#2}}\newcommand{\samplezqs}{\class{hover}{#1\sampleSymb\zqs}}\newcommand{\sampleN}{\class{hover}{#1\sampleSymb\z{#2}}}\newcommand{\sampleNs}{\class{hover}{#1\sampleSymb\z{#2}^\ast}}\newcommand{\equalQ}{\overset{?}{=}}\newcommand{\gQ}{\overset{?}{>}}\newcommand{\inQ}{\overset{?}{\in}}\newcommand{\cgroup}{\mathbb{G}}\newcommand{\hash}{\mathsf{Hash}({#1})}\newcommand{\hashbit}{\mathsf{Hash}({#1})\verb+[0:#2]+}\newcommand{\naturals}{\mathbb{N}}\newcommand{\sqfree}{L_\mathsf{square-free}}\newcommand{\ceil}{\lceil #1 \rceil}\newcommand{\sampleSet}{\class{hover}{#1\sampleSymb#2}}\newcommand{\bunch}{\{ #1_i\}_{i=1}^m}\newcommand{\bunchi}{\{ #1\}_{i=1}^m}\newcommand{\forb}{\text{ for }i=1,\ldots,m}\newcommand{\interval}{[0, #1[}\newcommand{\range}{[#1]}\newcommand{\rangeone}{\{1, \dots,#1 -1 \}}\newcommand{\vara}{\class{var var_a}{a}}\newcommand{\varb}{\class{var var_b}{b}}\newcommand{\varc}{\class{var var_c}{c}}\newcommand{\vard}{\class{var var_d}{d}}\newcommand{\varh}{\class{var var_h}{h}}\newcommand{\varg}{\class{var var_g}{g}}\newcommand{\varu}{\class{var var_u}{u}}\newcommand{\varx}{\class{var var_x}{x}}\newcommand{\varX}{\class{var var_X}{X}}\newcommand{\varz}{\class{var var_z}{z}}\newcommand{\varr}{\class{var var_r}{r}}\newcommand{\varq}{\class{var var_q}{q}}\newcommand{\varp}{\class{var var_p}{p}}\newcommand{\vare}{\class{var var_e}{e}}\newcommand{\vary}{\class{var var_y}{y}}\newcommand{\varw}{\class{var var_w}{w}}\newcommand{\varprover}{\class{var var_Prover}{\text{Prover}}}\newcommand{\varprover}{\class{var var_Prover}{\text{Prover}}}\newcommand{\varverifier}{\class{var var_Verifier}{\text{Verifier}}}\newcommand{\varN}{\class{var var_N}{N}}\newcommand{\rhovar}{\class{var var_ρ}{\rho}}\newcommand{\sigmavar}{\class{var var_σ}{\sigma}}\newcommand{\thetavar}{\class{var var_θ}{\theta}}\newcommand{\muvar}{\class{var var_μ}{\mu}}\newcommand{\true}{\mathsf{true}}\newcommand{\false}{\mathsf{false}}$Notation & Definitions # Notation and Definitions # This page is a glossary for notation and concepts present in the documentation. ## Sets, Groups, and Special Functions # •$\mathbb{Z}$is the set of integers,$\{\ldots, -2, -1, 0, 1, 2, \ldots\}$. •$\naturals$is the set of integers greater of equal than 0,$\{0, 1, 2, \ldots\}$. •$\range{b}$is the finite set of integers$\{0, \ldots, b-1\}$. •$\gcd(n, m)$is the nonnegative greatest common divisor of integers$n$and$m$; when$\gcd(n, m) = 1$,$n$and$m$are said to be coprime. •$\z{n}$are the integers modulo$n$, a set associated with the equivalence classes of integers$\{0, 1, \ldots, n-1\}$. •$\zns{n}$is the multiplicative group of integers modulo$n$: an element$e$from$\z{n}$is in$\zns{n}$iff$\gcd(e, n) = 1$, that is$\zns{n} = \{e \in \z{n}: \gcd(e, n) = 1\}$. When$n$is prime, then$\zns{n} = \{1, \ldots, n-1\}$. •$\field{p}$is the finite field of order$p$; when$p$is a prime number, these are the integers modulo$p$,$\z{p}$; when$p$is a prime power$q^k$, these are Galois fields. •$\varphi(n)$is Euler’s totient function; for$n\geq 1$, it is the number of integers in$\{1,\ldots, n\}$coprime with$n.$•$|S|$is the order of a set$S$, i.e., its number of elements. For example,$|\zns{n}| = \varphi(n)$, and for a prime$n$,$|\zns{n}| = n-1$. ## Number-theory # •$J(w, n)\in \{-1, 0, 1\}$is the Jacobi symbol of$w$modulo$n$, only defined for positive and odd$n$. •$J_n$is the set of elements of$\zns{n}$with Jacobi symbol$1$. •$QR_n$is the set of quadratic residues modulo$n$, which are elements that have a square-root, i.e.,$QR_n = \{e \in \z{n} : \exists r . r^2 = e \mod n\}$. ## Sampling # In protocol specifications, we will often need to uniformly sample elements from sets. We will use the following notation: •$\sampleGeneric{x}{X}$, where$x$is uniformly sampled from the set$X$. Consider reading the section on Random Sampling to learn how to correctly sample a number uniformly using rejection sampling, avoiding the modulo-bias issue. ## Assertions # We will use assertions in protocol descriptions. When the assertions do not hold, the protocol must abort to avoid leaking secret information. •$a \equalQ b$, requires$a=b$, and aborts otherwise •$a \gQ b$, requires$a>b$, and aborts otherwise •$a \inQ S$, requires that$a$is in the set$S$, and aborts otherwise. ## Implementations of number-theoretic algorithms # In general, we highly recommend the Handbook of Applied Cryptography, which has detailed descriptions of most algorithms. ## Hash Functions # •$\hash{\cdot}$is a cryptographically secure domain-separated hash function. •$\hashbit{\cdot}{k}$is a cryptographically secure domain-separated hash function with specific output-size of$k\$-bits.

Find more details on the particular hash functions in Nothing-up-my-sleeve constructions