$\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}}$
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 \neq 0 \mod \varN} \bobwork{\varh \neq 0 \mod \varN} \bobwork{\varz \neq 0 \mod \varN} \bobseparator \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{\varu \neq 0 \mod \varN} \bobwork{\varh \neq 0 \mod \varN} \bobwork{\varz \neq 0 \mod \varN} \bobseparator \bobwork{\vare \equalQ \hashbit{\varg, \varN, \varh, \varu}{k}} \bobwork{\varu \equalQ \varg^{\varz} \cdot \varh^\vare \mod \varN} \end{array} $$

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