$\newcommand{\alicebob}[3]{#1 & \ra{#2} & #3\\[-5pt]}$ $\newcommand{\bobalice}[3]{#1 & \la{#2} & #3\\[-5pt]}$ $\newcommand{\alicework}[1]{#1 & &\\[-5pt]}$ $\newcommand{\bobwork}[1]{ & & #1\\[-5pt]}$ $\newcommand{\work}[2]{#1 & & #2\\}$ $\newcommand{\allwork}[1]{ & #1 & \\}$ $\newcommand{\aliceseparator}{-------&&\\}$ $\newcommand{\bobseparator}{&&-------\\}$ $\newcommand{\foo}{\phantom{\text{bigarrowfitsallthis}}}$ $\newcommand{\ra}[1]{% \vphantom{\xrightarrow{asd}}% \smash{\xrightarrow[\foo]{#1}}% }$ $\newcommand{\la}[1]{% \vphantom{\xleftarrow{asd}}% \smash{\xleftarrow[\foo]{#1}}% }$ $\newcommand{\z}[1]{\mathbb{Z}_{#1}}$ $\newcommand{\zq}{\mathbb{Z}_\varq}$ $\newcommand{\zqs}{\mathbb{Z}_q^\ast}$ $\newcommand{\zps}{\mathbb{Z}_p^\ast}$ $\newcommand{\zns}[1]{\mathbb{Z}_{#1}^\ast}$ $\require{action} \newcommand{\sampleSymb}{ {\overset{\$}{\leftarrow}} }$ $\newcommand{\field}[1]{\mathbb{F}_{#1}}$ $\newcommand{\sample}[1]{#1\sampleSymb\zq}$ $\newcommand{\sampleGeneric}[2]{#1\sampleSymb#2}$ $\newcommand{\sampleInterval}[2]{#1\sampleSymb\interval{#2}}$ $\newcommand{\sampleRange}[2]{#1\sampleSymb\range{#2}}$ $\newcommand{\samplezqs}[1]{\class{hover}{#1\sampleSymb\zqs}}$ $\newcommand{\sampleN}[2]{\class{hover}{#1\sampleSymb\z{#2}}}$ $\newcommand{\sampleNs}[2]{\class{hover}{#1\sampleSymb\z{#2}^\ast}}$ $\newcommand{\equalQ}{\overset{?}{=}}$ $\newcommand{\gQ}{\overset{?}{>}}$ $\newcommand{\inQ}{\overset{?}{\in}}$ $\newcommand{\cgroup}{\mathbb{G}}$ $\newcommand{\hash}[1]{\mathsf{Hash}({#1})}$ $\newcommand{\hashbit}[2]{\mathsf{Hash}({#1})\verb+[0:#2]+}$ $\newcommand{\naturals}{\mathbb{N}}$ $\newcommand{\sqfree}{L_\mathsf{square-free}}$ $\newcommand{\ceil}[1]{\lceil #1 \rceil}$ $\newcommand{\sampleSet}[2]{\class{hover}{#1\sampleSymb#2}}$ $\newcommand{\bunch}[1]{\{ #1_i\}_{i=1}^m}$ $\newcommand{\bunchi}[1]{\{ #1\}_{i=1}^m}$ $\newcommand{\forb}{\text{ for }i=1,\ldots,m}$ $\newcommand{\interval}[1]{[0, #1[}$ $\newcommand{\range}[1]{[#1]}$ $\newcommand{\rangeone}[1]{\{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}}$
Random Sampling

Random sampling #

In most protocols, it is required to sample uniformly from groups like $\zq$ or $\zqs$. Here we will describe how to sample in these specific groups, and a general procedure to sample via rejection sampling.

Uniform sampling in $\zq$ #

Since we identify the elements of $\zq$ with the set of integers $\range{q}$, to uniformly sample we only need to sample from the set $\range{q}$.

We should always use a suitable cryptographic random number library to sample uniformly. For instance, in python, we can use secrets.

1
2
3
4
import secrets

def sample_Zq():
    return secrets.randbelow(q)

Never do this: When you only have access to sampling elements of a fixed bit-size but want to sample over $\z{1337}$ do not do this:

1
2
def wrong_sampling():
    return sample_32_bits() % 1337

The wrong_sampling function introduces modulo-bias in the generation of elements, and some elements will be more likely to appear than others. In these cases you need to use rejection sampling.

Rejection sampling #

Suppose we know how to sample from a set $S$ and would like to sample from a subset $T\subseteq S$. To do this, we need to check membership in $T$ and perform rejection sampling. In a loop:

  1. sample element $e \in S$.
  2. if $e \in T$, return $e$, otherwise repeat step 1.

This is how we must perform sampling in $\zq$ if we cannot use a library like secrets. In this case, rejection sampling would look like this:

1
2
3
4
5
def correct_sampling():
    while True:
        e = sample_32_bits()
        if e >= 0 and e < 1337:
            return e

Depending on the set we can sample from, this method can take longer, but in practice, we should always be able to sample from spaces only slightly larger than our target space.

Uniform sampling in $\zqs$ #

Sampling in $\zqs$ requires an extra step. The elements of $\zqs$ are the elements invertible modulo $q$ and for $e$ to be invertible means that $\gcd(e, q) = 1$. So, to obtain these elements we need to perform rejection sampling. In a loop,

  1. sample element $e \in \zq$ using the previous section.
  2. if $\gcd(e, q) = 1$ return $e$, otherwise repeat step 1.
1
2
3
4
5
6
7
8
import secrets
import math

def sample_Zqstar():
    while True:
        e = sample_Zq()
        if math.gcd(e, q) == 1:
            return e
Note: Since $\gcd(0, q)$ is never 1, we can sample $e$ from the set $\rangeone{q}$.