$\newcommand{\coinheads}{\mathsf{HEADS}}$ $\newcommand{\cointails}{\mathsf{TAILS}}$ $\newcommand{\varalice}{\class{var var_Alice}{\text{Alice}}}$ $\newcommand{\varbob}{\class{var var_Bob}{\text{Bob}}}$ $\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{\dupwork}[1]{#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{\sampleCgroup}[1]{#1\sampleSymb\cgroup}$ $\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}{\mathsf{Hash}}$ $\newcommand{\hash}[1]{\Hash({#1})}$ $\newcommand{\HashToField}{\mathsf{HashToField}}$ $\newcommand{\hashtofield}[1]{\HashToField({#1})}$ $\newcommand{\HashToGroup}{\mathsf{HashToGroup}}$ $\newcommand{\hashtogroup}[1]{\HashToGroup({#1})}$ $\newcommand{\hashbit}[2]{\mathsf{Hash}({#1})\verb+[0:#2]+}$ $\newcommand{\hmac}[2]{\mathsf{HMAC}_{#1}\left(#2\right)}$ $\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{\varH}{\class{var var_H}{H}}$ $\newcommand{\varg}{\class{var var_g}{g}}$ $\newcommand{\varG}{\class{var var_G}{G}}$ $\newcommand{\vari}{\class{var var_i}{i}}$ $\newcommand{\varj}{\class{var var_j}{j}}$ $\newcommand{\vars}{\class{var var_s}{s}}$ $\newcommand{\vart}{\class{var var_t}{t}}$ $\newcommand{\varu}{\class{var var_u}{u}}$ $\newcommand{\varU}{\class{var var_U}{U}}$ $\newcommand{\varl}{\class{var var_l}{l}}$ $\newcommand{\varm}{\class{var var_m}{m}}$ $\newcommand{\varn}{\class{var var_n}{n}}$ $\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{\varv}{\class{var var_v}{v}}$ $\newcommand{\varw}{\class{var var_w}{w}}$ $\newcommand{\varC}{\class{var var_C}{C}}$ $\newcommand{\varf}{\class{var var_f}{f}}$ $\newcommand{\varA}{\class{var var_A}{A}}$ $\newcommand{\varB}{\class{var var_B}{B}}$ $\newcommand{\varC}{\class{var var_C}{C}}$ $\newcommand{\varL}{\class{var var_L}{L}}$ $\newcommand{\varP}{\class{var var_P}{P}}$ $\newcommand{\varR}{\class{var var_R}{R}}$ $\newcommand{\varT}{\class{var var_T}{T}}$ $\newcommand{\varX}{\class{var var_X}{X}}$ $\newcommand{\varalpha}{\class{var var_alpha}{\alpha}}$ $\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}}$ $\renewcommand{\vec}[1]{\mathbf{#1}}$ $\newcommand{\veca}{\vec{\class{var var_vec_a}{a}}}$ $\newcommand{\vecb}{\vec{\class{var var_vec_b}{b}}}$ $\newcommand{\vecc}{\vec{\class{var var_vec_c}{c}}}$ $\newcommand{\vecs}{\vec{\class{var var_vec_s}{s}}}$ $\newcommand{\vecG}{\vec{\class{var var_vec_G}{G}}}$ $\newcommand{\vecH}{\vec{\class{var var_vec_H}{H}}}$ $\newcommand{\vecg}{\vec{\class{var var_vec_g}{g}}}$ $\newcommand{\vech}{\vec{\class{var var_vec_h}{h}}}$ $\newcommand{\true}{\mathsf{true}}$ $\newcommand{\false}{\mathsf{false}}$ $\newcommand{\ctx}{\mathsf{ctx}}$ $\newcommand{\coloneqq}{≔}$ $\newcommand{\ip}[2]{\left\langle #1, #2 \right\rangle}$ $\newcommand{\uwork}[2]{\underline{#1} & & \underline{#2}\\}$ $\newcommand{\aliceworks}[1]{#1 & &\\[-2pt]}$ $\newcommand{\bobworks}[1]{ & & #1\\[-2pt]}$ $\newcommand{\Halving}{\text{Halving}}$ $\newcommand{\HalveProof}{\text{HalveProof}}$ $\newcommand{\HalveVerify}{\text{HalveVerify}}$ $\newcommand{\indent}{\qquad}$ $\newcommand{\append}{\mathrm{append}}$ $\newcommand{\schnorrvalidate}{\mathsf{schnorr}\_\mathsf{validate}}$
Schnorr's identification protocol

Schnorr’s identification protocol #

Schnorr’s identification protocol is the simplest example of a zero-knowledge protocol. With it, $\varprover$ can convince $\varverifier$ that they know the discrete logarithm $\varx$ of some value $\varh = \varg^\varx$, without revealing $\varx$.

Goal: $\varprover$ convinces $\varverifier$ that they know $\varx$ such that $\varh = \varg^\varx$.
  • Public input: cyclic group $\cgroup$ of prime order $\varq$, a $\cgroup$ generator $\varg$ and $\varh\in \cgroup$.
  • Private input: $\varprover$ knows secret $\varx\in\zq$ such that $\varh = \varg^\varx$.

Interactive protocol #

The Schnorr interactive identification protocol

$$ \begin{array}{c} \work{\varprover}{\varverifier} \alicework{\samplezqs{\varr}} \alicework{\varu = \varg^\varr} \alicebob{}{\varu}{} \bobwork{\schnorrvalidate(\varu, \varh)} \bobseparator \bobwork{\sample{\varc}} \bobalice{}{\varc}{} \alicework{\varz = \varr + \varx\cdot \varc} \alicebob{}{\varz}{} \bobwork{\varz \neq 0 \mod \varq} \bobseparator \bobwork{\varg^{\varz} \equalQ \varu \cdot \varh^\varc } \end{array} $$

Non-interactive protocol #

We can transform this identification scheme into a non-interactive protocol using the Fiat-Shamir heuristic. Here, the prover creates the random challenge $c$ hashing all public values $\{\varg, \varq, \varh, \varu\}$.

$$ \begin{array}{c} \work{\varprover}{\varverifier} \alicework{\samplezqs{\varr}} \alicework{\varu = \varg^\varr} \alicework{\varc = \hash{\varg, \varq, \varh, \varu}} \alicework{\varz = \varr + \varx\cdot \varc} \alicebob{}{\varu, \varc, \varz}{} \bobwork{\schnorrvalidate(\varu, \varh)} \bobwork{\varz \neq 0 \mod \varq} \bobseparator \bobwork{\varc \equalQ \hash{\varg, \varq, \varh, \varu}} \bobwork{\varg^\varz \equalQ \varu \cdot \varh ^\varc } \end{array} $$

Interactive protocol #

The Schnorr interactive identification protocol

$$ \begin{array}{c} \work{\varprover}{\varverifier} \alicework{\samplezqs{\varr}} \alicework{\varu = \varr\cdot\varg} \alicebob{}{\varu}{} \bobwork{\schnorrvalidate(\varu, \varh)} \bobseparator \bobwork{\sample{\varc}} \bobalice{}{\varc}{} \alicework{\varz = \varr + \varx\cdot \varc} \alicebob{}{\varz}{} \bobwork{\varz \neq 0 \mod \varq} \bobseparator \bobwork{\varg^{\varz} \equalQ \varu \cdot \varh^\varc } \end{array} $$

Non-interactive protocol #

We can transform this identification scheme into a non-interactive protocol using the Fiat-Shamir heuristic. Here, the prover creates the random challenge $c$ hashing all public values $\{\varg, \varq, \varh, \varu\}$.

$$ \begin{array}{c} \work{\varprover}{\varverifier} \alicework{\samplezqs{\varr}} \alicework{\varu = \varr\cdot \varg} \alicework{\varc = \hash{\varg, \varq, \varh, \varu}} \alicework{\varz = \varr + \varx\cdot \varc} \alicebob{}{\varu, \varc, \varz}{} \bobwork{\schnorrvalidate(\varu, \varh)} \bobwork{\varz \neq 0 \mod \varq} \bobseparator \bobwork{\varc \equalQ \hash{\varg, \varq, \varh, \varu}} \bobwork{\varz \cdot \varg \equalQ \varu + \varc\cdot\varh} \end{array} $$

where $\schnorrvalidate(\varu, \varh)$ aborts if any of the following conditions are not met:

  • $\varu, \varh \neq 0 \text{ (point at infinity for EC groups)}$ and
  • $\varu, \varh \inQ \cgroup\text{ (on curve check for EC groups)}$.

Security pitfalls #

  • Verifier input validation: Each of the items above the dotted line for the $\varverifier$ is essential to the security of the protocol. If any of these checks are missing or insufficient it is likely a severe security issue.
  • Verifier trusts prover: On the verification check, the verifier uses $g$ and $q$ provided with the proof instead of using publicly known values. On the NI version, the verifier assumes that the hash $\varc$ is correctly computed and does not compute it themself. Both are high severity issues since $\varprover$ can forge proofs.
  • Weak Fiat-Shamir transformation: In the non-interactive protocol, it is a common occurrence that some parameters are missing on the hash computation $\hash{\varg, \varq, \varh, \varu}$:
    • $\varh$ or $\varu$ missing: high severity issue. Read Fiat-Shamir transformation for more details.
    • $\varg$ or $\varq$ missing: usually no issue, but it might be one if the Verifier uses these parameters directly from the proof structure. This way, the prover can provide bad generators or orders to forge the proof.
  • Weak randomness: Bad randomness may cause the secret $\varx$ to leak. If $\varr$ is reused twice with two different interactive challenges, or different data on the non-interactive version then $$ \frac{\varz - \varz’}{\varc-\varc’} = \frac{\varr -\varr + \varx\cdot(\varc - \varc’)}{\varc-\varc’} = \varx $$
  • Replay attacks: After a non-interactive proof is public, it will always be valid and anyone could pretend to know the secret value. To prevent this, consider adding the ID of both the prover and the verifier inside of the Fiat-Shamir hash computation.

Security assumptions #

  • Hash function: The hash function should be either TupleHash or SHA-256 where each input is domain separated with a unique string together with the length of each element.
  • Hardness of the discrete logarithm: The order of the cyclic group $\cgroup$ should be at least $\varq>2^{K}$ where $K=256$, for a generic group $\cgroup$. If $\cgroup$ is a (prime-order) subgroup of $\zps$, then $p$ should be greater than $2^{\kappa}$ for $\kappa=3072$ to avoid subexponential attacks based on the extra structure of $\zps$. Note that this requires $p - 1 = q\cdot r$ with some potentially composite number $r$. Refer to table 2 (pp. 54-55) of the NIST recommendations for an overview of different bit security levels for finite field discrete logarithms.

References #