$\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}}$
Number is square-free

Number is square-free #

To prove that a number is the product of two distinct primes, the first step is showing that the number is free of squares, i.e., that $\varN$ is not of the form $\varN = p^2 r$.

This proof shows in zero-knowledge –without revealing the factors of the number– that an element belongs to the set $$\sqfree = \{\varN \in \naturals : \text{there is no prime }p \text{ such that }p^2|N \}.$$

The protocol uses the fact that an honest prover can calculate $\varN$-th roots of arbitrary numbers in $\z{\varN}$.

Goal: $\varprover$ convinces $\varverifier$ that $\varN$ is square-free without revealing its factorization.
  • Public input: $\varN\in\naturals$
  • Private input: $\varprover$ knows the factorization of $\varN = \varp\varq$
  • Security parameters: $\alpha, \kappa, m = \ceil{\kappa/ \log_2 \alpha}$

The protocol uses the constant $\displaystyle\Pi_\alpha = \prod_\underset{p\text{ prime}}{p<\alpha} p$, the product of the primes smaller than $\alpha$.

We assume that both parties agree with the security parameters $\alpha, \kappa$ and $m$ prior to the execution of the protocol.

Interactive protocol (HVZK) #

Security note: The protocol is zero-knowledge (does not reveal the factorization of $\varN$) only when the verifier is honest and generates each $\rhovar_i$ randomly. If the verifier choses these values maliciously they can recover the factorization of $\varN$. If your attacker model takes this into consideration, use the non-interactive version. More details on Using HVZKP in the wrong context.
$$ \begin{array}{c} \work{\varprover}{\varverifier} \bobwork{\sampleN{\rhovar_i}{\varN}, \text{ for }i=1,\ldots,m} \bobalice{}{\{\rhovar_i\}_{i=1}^m}{} \alicework{\sigmavar_i = (\rhovar_i)^{\varN^{-1}\mod \varphi(\varN)} \mod \varN,} \alicework{\text{ for }i=1,\ldots,m} \alicebob{}{\{\sigmavar_i\}_{i=1}^m}{} \bobwork{\varN \gQ 1} \bobwork{\gcd(\varN, \Pi_\alpha) \equalQ 1} \bobwork{\sigmavar_i \mod \varN \gQ 0,} \bobseparator \bobwork{\rhovar_i \equalQ \sigmavar_i^\varN \mod \varN,} \bobwork{\text{ for }i=1,\ldots,m} \end{array} $$

Non-interactive protocol #

The non-interactive version of the protocol replaces the verifier-side sampling of $\rhovar_i$ elements and generates them using the Fiat-Shamir transformation. The participants only exchange one message, and there is no risk of leaking the factorization of $\varN$ using maliciously chosen $\rhovar_i$ values. $$ \begin{array}{c} \work{\varprover}{\varverifier} \alicework{\rhovar_i = \mathsf{gen}_\rhovar(\z{\varN}, \{\varN,i\})} \alicework{\sigmavar_i = (\rhovar_i)^{\varN^{-1}\mod \varphi(\varN)} \mod \varN,} \alicework{\text{ for }i=1,\ldots,m} \alicebob{}{\{\sigmavar_i\}_{i=1}^m}{} \bobwork{\varN \gQ 1} \bobwork{\gcd(\varN, \Pi_\alpha) \equalQ 1} \bobwork{\sigmavar_i \mod \varN \gQ 0 ,} \bobseparator \bobwork{\rhovar_i = \mathsf{gen}_\rhovar(\z{\varN}, \{\varN,i\})} \bobwork{\rhovar_i \equalQ \sigmavar_i^\varN \mod \varN,} \bobwork{\text{ for }i=1,\ldots,m} \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.
  • Using the interactive protocol in a malicious verifier context: high severity issue which allows factoring $\varN$; see Using HVZKP in the wrong context.
  • Sampling $\rhovar_i$ values uniformly and not using honest generation: high severity issue that allows $\varprover$ to forge proofs by sampling $\sampleSet{\sigmavar_i}{\z\varN}$ and setting $\rhovar_i = \sigmavar_i^\varN\mod \varN$.
  • Verifier trusting prover on the non-interactive protocol:
    • $\varverifier$ uses $\rhovar_i$ values provided by $\varprover$ instead of generating them: this is a high severity issue since the prover can trivially forge proofs (e.g., by sending $\rhovar_i=1, \sigmavar_i=1$).
    • $\varverifier$ does not validate $\sigmavar_i$ as valid values modulo $\varN$ (between 0 and $\varN -1)$: this allows replaying the same proof with different values with $\sigmavar_i + k\varN$.
    • $\varverifier$ does not compare the number of received $\sigmavar_i$ with $m$: this can lead to the prover bypassing proof verification by sending an empty list, or fewer than $m$ elements.
  • 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 generation of $\rhovar_i$ values such as an ID of both the prover and the verifier, and a timestamp. The verifier must check the validity of these values when they verify the proof.

Auxiliary functions - $\mathsf{gen}_\rhovar$ #

  • Generate the $\rhovar_i$ values with a standard nothing-up-my-sleeve construction in $\z{\varN}$, use binding parameters $\{\varN, i\}$, bitsize of $|\varN|$, and salt $\mathsf{“squarefreeproof”}$. To prevent replay attacks consider including, in the binding parameters, ID’s unique to the prover and verifier.

Choice of security parameters $\alpha$, $\kappa$ #

The security of the protocol depends $\alpha$ and $\kappa$ which define the number of witnesses that $\varprover$ has to give $\varverifier$. The protocol achieves a statistical soundness error of $2^{-\kappa}$, which means $\varprover$ cannot cheat except with probability $2^{-\kappa}$.

Parameter $\alpha$ is tunable and controls proving and verification time. Higher $\alpha$ values will generally decrease proving time and verification time, until some limit is reached and the verification time starts increasing.

Recommended values for the security parameters are:

  • $\kappa = 128$
  • $\alpha = 65537, 319567$ can be tried and the best performing one chosen.

These values yield $m$ values of

  • $m(\kappa=128, \alpha=65537) = 8$ and
  • $m(\kappa=128, \alpha=319567) = 7$.

References #