$\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}}$
Two prime divisors

Number has exactly two prime divisors #

To prove that a number is the product of two distinct primes, one step is showing that the number only has two prime divisors, i.e., showing that $\varN$ is not of the form $\varN = pqr$.

This protocol allows to prove in zero-knowledge –without revealing its factors– that a number is in the set $$L_{ppp} = \{\varN \in \naturals : \varN \text{ is odd and has exactly two distinct prime divisors}\}.$$

Goal: $\varprover$ convinces $\varverifier$ that $\varN$ only has two distinct prime divisors without revealing its factorization.
  • Public input: $\varN\in\naturals$
  • Private input: $\varprover$ knows the factorization of $\varN = \varp\varq$
  • Security parameters: $\kappa, m = \ceil{\kappa \cdot 32 \cdot \ln(2)}$

The protocol works because an honest prover can calculate square-roots of arbitrary numbers in $\z{\varN}$.

Both parties have to agree on the security parameter $\kappa$ prior to the execution of the protocol.

Interactive protocol #

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{\sampleSet{\rhovar_i}{J_\varN}, \text{ for }i=1,\ldots,m} \bobalice{}{\{\rhovar_i\}_{i=1}^m}{} \alicework{\sigmavar_i = \begin{cases} \sqrt{\rhovar_i} \mod \varN &\text{ if }\rhovar_i \in QR_\varN \\ 0 &\text{ otherwise} \end{cases} } \alicework{\text{ for }i=1,\ldots,m} \alicebob{}{\{\sigmavar_i\}_{i=1}^m}{} \bobwork{\varN \gQ 1} \bobwork{\varN \mod 2 \equalQ 1} \bobwork{\mathsf{isPrime}(\varN) \equalQ false} \bobwork{\mathsf{isPrimePower}(\varN) \equalQ false} \bobwork{\gcd(\varN, \Pi_\alpha) \equalQ 1} \bobseparator \bobwork{|\{\sigmavar_i \text{ for }i=1,\ldots,m| \sigmavar_i \neq 0 \mod \varN\}| \gQ 3m/8} \bobwork{\text{if } \sigmavar_i \neq 0 \mod \varN \text{ then }\rhovar_i \equalQ \sigmavar_i^2 \mod \varN} \end{array} $$

In this protocol we need to uniformly sample from the $J_\varN$, the set of integers modulo $\varN$ with Jacobi symbol $1$. The prover also needs to check membership of the $QR_\varN$, the set of quadratic residues modulo $\varN$. Both computations, the Jacobi symbol and quadratic residuosity, can be done efficiently.

Non-interactive protocol #

The non-interactive version of the protocol replaces the verifier-side sampling of $\rhovar_i$ and generates them using the $\mathsf{gen}_\rhovar$ function. The participants only exchange one message and this proof can be used in the context of malicious verifiers. $$ \begin{array}{c} \work{\varprover}{\varverifier} \alicework{\rhovar_i = \mathsf{gen}_\rhovar(J_\varN, \{\varN,i, F\})} \alicework{\sigmavar_i = \begin{cases} \sqrt{\rhovar_i} \mod \varN &\text{ if }\rhovar_i \in QR_\varN \\ 0 &\text{ otherwise} \end{cases} } \alicework{\text{ for }i=1,\ldots,m} \alicebob{}{\bunchi{\sigmavar_i}, F}{} \bobwork{\varN \gQ 1} \bobwork{\varN \mod 2 \equalQ 1} \bobwork{\mathsf{isPrime}(\varN) \equalQ false} \bobwork{\mathsf{isPrimePower}(\varN) \equalQ false} \bobwork{\gcd(\varN, \Pi_\alpha) \equalQ 1} \bobseparator \bobwork{\rhovar_i = \mathsf{gen}_\rhovar(J_\varN, \{\varN,i, F\})} \bobwork{|\{\sigmavar_i \text{ for }i=1,\ldots,m| \sigmavar_i \neq 0 \mod \varN\}| \gQ 3m/8} \bobwork{\text{if } \sigmavar_i \neq 0 \mod \varN \text{ then }\rhovar_i \equalQ \sigmavar_i^2 \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.
  • 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, allows $\varprover$ to forge proofs by sampling $\sampleSet{\sigmavar_i}{\z\varN}$ and setting $\rhovar_i = \sigmavar_i^2\mod \varN$.
  • Failing to include a fresh value in $\mathsf{gen}_\rhovar$: potential high severity issue since this means that all proofs for the same $\varN$ will have the same $\rhovar_i$; if the prover uses a probabilistic algorithm to compute square-roots, he can leak two different square-roots of the same value, allowing an attacker to factor $\varN$ using the same attack as Using HVZKP in the wrong context. If the square-root algorithm always returns the same square-root for a given $\rhovar_i$ this is not an issue.
  • 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 it. To prevent this, consider adding additional information to the hash function such as an ID of both the prover and the verifier and a timestamp.

Choice of security parameters $\kappa$ #

The protocol uses the security parameter $\kappa$ to determine the number of exchanged elements.

For different $\kappa$ values, we obtain

  • $m(\kappa=64) = 1420$
  • $m(\kappa=128) = 2840$

Honest parameter generation $\mathsf{gen}_\rhovar$ #

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

Auxiliary algorithms #

References #