$\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}}$
Girault's identification protocol

Girault’s identification protocol #

This scheme is a zero-knowledge proof for a discrete logarithm, like Schnorr’s protocol, but over a composite modulus instead of a prime modulus.

Goal: $\varprover$ convinces $\varverifier$ that they know $\varx$ such that $\varh = \varg^{-\varx} \mod \varN$
  • Public input: $\varh, \varN$ and a high order generator $\varg\in \zns{\varN}$
  • Private input: $\varprover$ knows the secret $\varx\in \range{S}$
  • Security parameters: The parameters $k, k’, S$ and $R = 2^{k+k’ + |S|}$.

Interactive protocol #

Security note: The interactive identification protocol assumes an honest verifier and should not be used in the context of malicious verifiers. A malicious verifier can send $\vare = R$ and recover the secret $\varx$ by dividing $\varz$ by $\vare$.
$$ \begin{array}{c} \work{\varprover}{\varverifier} \alicework{\varh = \varg^{-\varx} \mod \varN} \alicework{\sampleRange{\varr}{R}} \alicework{\varu = \varg^\varr \mod \varN} \alicebob{}{\varu}{} \bobwork{\sampleRange{\vare}{2^k}} \bobalice{}{\vare}{} \alicework{\varz = \varr + \varx\cdot \vare \in \naturals} \alicebob{}{\varz}{} \bobwork{\varu \equalQ \varg^{\varz} \cdot \varh^\vare \mod \varN} \end{array} $$

Non-interactive protocol #

We obtain a non-interactive protocol using the Fiat-Shamir heuristic, where the prover creates the random $k$-bit challenge $\vare$ using domain-separated hash function over the $\{\varg, \varN, \varh, \varu\}$ parameters. $$ \begin{array}{c} \work{\varprover}{\varverifier} \alicework{\varh = \varg^{-\varx} \mod \varN} \alicework{\sampleRange{\varr}{R}} \alicework{\varu = \varg^\varr \mod \varN} \alicework{\vare = \hashbit{\varg, \varN, \varh, \varu}{k}} \alicework{\varz = \varr + \varx\cdot \vare \in \naturals} \alicebob{}{\varu, \vare, \varz}{} \bobwork{\vare \equalQ \hashbit{\varg, \varN, \varh, \varu}{k}} \bobwork{\varu \equalQ \varg^{\varz} \cdot \varh^\vare \mod \varN} \end{array} $$

Security pitfalls #

  • Parameter choice: Implementers must pay special attention to the choice of parameter values, in particular the relation between $2^k$ and $R$. If these were of similar size, since $\varz$ is computed over the naturals, $\varx$ would be approximately $\lfloor \varz/\vare\rfloor$.
  • Using the interactive protocol in a malicious verifier context: high severity issue which allows recovering the secret $\varx$; see Using HVZKP in the wrong context.
  • Verifier trusting prover on the non-interactive protocol:
    • $\varverifier$ uses a $\varg$ value provided by $\varprover$ instead of using the standard generator: this is a high severity issue since the prover can trivially forge proofs (e.g., by sending $\varu=0, \varg=0$).
    • $\varverifier$ does not validate $\varu,\varh$ as valid elements of $\zns{\varN}$ (between 1 and $\varN-1$ and with $\gcd(k, \varN) = 1$): this allows replaying the same proof with different values adding multiples of $\varN$.
  • Replay attacks: After a non-interactive proof is public, it will always be valid, and anyone could pretend to know how to prove the original statement. To prevent this, consider adding additional information to the computation of the hash function: values such as an ID unique to the prover and verifier, and a timestamp. The verifier must use these values and check their validity to verify the proof.

Choice of parameter values #

  • $|\varN| = 2048$
  • $S = 2^{256}$
  • $k,k’ = 128$

Auxiliary procedures #

    • Hash function $\hashbit{\cdot}{k}$: this hash function should be domain-separated and have a specific output size of $k$-bits. Using $\mathsf{TupleHash}$ satisfies these restrictions.

References #