$\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}}$
Variants of Schnorr's identification protocol

Variants of Schnorr’s identification protocol #

All variants of Schnorr’s protocol prove the knowledge of an $\varx$ such that $\varh = \varg^\varx$ for a public $\varh$.

The differences are tradeoffs between the size of the proof statements and a more costly proof verification, and smaller communication overhead.

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$.

We present all variants in their non-interactive version.

Non-interactive protocols #

Original #

$$ \begin{array}{c} \work{\varprover}{\varverifier} \alicework{\sampleNs{\varr}{\varq}} \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} $$

Slim Original #

In this variant, the prover does not send the value of $\varc$ which has to be computed by the verifier. $$ \begin{array}{c} \work{\varprover}{\varverifier} \alicework{\sampleNs{\varr}{\varq}} \alicework{\varu = \varg^\varr} \alicework{\varc = \hash{\varg, \varq, \varh, \varu}} \alicework{\varz = \varr + \varx\cdot \varc} \alicebob{}{\varu, \varz}{} \bobwork{\schnorrvalidate(\varu, \varh)} \bobwork{\varz \neq 0 \mod \varq} \bobseparator \bobwork{\bar{\varc} = \hash{\varg, \varq, \varh, \varu}} \bobwork{\varg^\varz \equalQ \varu \cdot \varh ^\overline{\varc} } \end{array} $$

Subtract #

In this variant, the prover uses a subtraction to compute the value of $\varz$.

$$ \begin{array}{c} \work{\varprover}{\varverifier} \alicework{\sampleNs{\varr}{\varq}} \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 \cdot \varh ^\varc \equalQ \varu } \end{array} $$

Subtract + Derive #

In this variant, the prover uses a subtraction to compute the value of $\varz$ and does not send $\varu$, which the verifier derives from the values they know.

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

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

  • $\varh \neq 0 \text{ (point at infinity for EC groups)}$ and
  • $\varh \inQ \cgroup\text{ (on curve check for EC groups)}$. If called with two arguments, $\schnorrvalidate(\varu, \varh)$ will abort if any of the following conditions are not met by either argument.

Security pitfalls #

These variants suffer from the same pitfalls as the original Schnorr scheme, with some adjustments when $\varz$ is computed with a subtraction:

  • 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:
    • $\varverifier$ uses $g$ and $q$ provided in the proof instead of using publicly known values.
    • When the $\varprover$ sends $\varc$, if the $\varverifier$ 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: It is a common issue 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 non-interactive challenges then: $$ \frac{\varz - \varz’}{\varc-\varc’} = \frac{\varr -\varr + \varx\cdot(\varc - \varc’)}{\varc-\varc’} = \varx \enspace,$$ or when $\varz$ is computed with a subtraction: $$ \frac{\varz - \varz’}{\varc’-\varc} = \frac{\varr -\varr + \varx\cdot(\varc’ - \varc)}{\varc’-\varc} = \varx \enspace.$$
  • 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.

References #