$\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}}$
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{\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{\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{\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{\bar{\varu} = \varg^\varz \cdot \varh^\varc} \bobwork{\bar{\varc} = \hash{\varg, \varq, \varh, \bar{\varu}}} \bobwork{\varc \equalQ \bar{\varc} } \end{array} $$

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 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 #