$\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}}$
Product of two primes

Number is the product of two primes #

To show that a number is the product of two distinct primes, we make use of the previous protocols to show that:

Formally, we show that $\varN$ is in the set $$L_{pp} = \{N \in \naturals | N \text{ is odd and is the product of two distinct primes}\} = L_{ppp} \cap \sqfree.$$ For this, we run the protocols from Square-free and Two prime divisors in parallel for the same $N$.

Goal: $\varprover$ convinces $\varverifier$ that $\varN$ is the product of two distinct primes without revealing its factorization.
  • Public input: $\varN\in\naturals$
  • Private input: $\varprover$ knows the factorization of $\varN = \varp\varq$
  • Security parameters: $\alpha, \kappa, m_1 = \ceil{\kappa/ \log_2 \alpha}$, $m_2 = \ceil{\kappa \cdot 32 \cdot \ln(2)}$

We only present the non-interactive version of this protocol, suitable to use in the context of malicious verifiers.

Non-interactive protocol #

$$ \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_1} \aliceseparator \alicework{\thetavar_i = \mathsf{gen}_\rhovar(J_\varN, \{\varN, m_1 + i, F\})} \alicework{\muvar_i = \begin{cases} \sqrt{\thetavar_i} \mod \varN &\text{ if }\thetavar_i \in QR_\varN \\ 0 &\text{ otherwise} \end{cases} } \alicework{\text{ for }i=1,\ldots,m_2} \alicebob{}{\{\sigmavar_i\}_{i=1}^{m_1}, \{\muvar_i\}_{i=1}^{m_2}, 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} \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_1} \bobwork{\thetavar_i = \mathsf{gen}_\rhovar(J_\varN, \{\varN, m_1 + i, F\})} \bobwork{|\{\muvar_i \text{ for }i=1,\ldots,m| \muvar_i \neq 0 \mod \varN\}| \gQ 3m_2/8} \bobwork{\text{if } \muvar_i \neq 0 \mod \varN \text{ then }\thetavar_i \equalQ \muvar_i^2 \mod \varN} \bobwork{\text{ for }i=1,\ldots,m_2} \end{array} $$

Security parameters #

  • $\kappa = 128$
  • $m_1(\kappa=128, \alpha=65537) = 8$
  • $m_2(\kappa=128) = 2840$

Security pitfalls #

This protocol suffers from the same pitfalls as the Square-free and Two prime divisors protocols. We include them here for clarity:

  • 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.
  • Sampling the $\rhovar_i$ or $\thetavar_i$ values uniformly and not using honest generation: high severity issue that allows $\varprover$ to forge proofs by sampling $\sampleSet{\sigmavar_i,\muvar_i}{\z\varN}$, and setting $\rhovar_i = \sigmavar_i^\varN\mod \varN$ and $\thetavar_i = \muvar_i^2\mod \varN$ .
  • Failing to include a fresh value in $\mathsf{gen}_\rhovar$ to generate $\thetavar_i$: potential high severity issue since this means that all proofs for the same $\varN$ will have the same $\thetavar_i$ values; 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$ or $\thetavar_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$ and $\thetavar_i = 1, \muvar_i=1$).
    • $\varverifier$ does not validate $\sigmavar_i$, $\muvar_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$, $\muvar_i + k’\varN$.
    • $\varverifier$ does not compare the number of received $\sigmavar_i$ with $m_1$ and $\muvar_i$ with $m_2$: this can lead to the prover bypassing proof verification by sending an empty list, or fewer than $m_1$ or $m_2$ 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$ and $\thetavar_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.

Performance considerations #

For the desired security level of $\kappa=128$, we need to generate 2840 $\muvar_i$ elements. Because of this, this proof system can be very computationally expensive. If this dramatically affects the performance of your protocol, and your $\varN$ is the product of two primes congruent with $3\mod 4$, we recommend using an alternative proof system, the Paillier-Blum modulus proof.

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

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

Auxiliary algorithms #

References #