$\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}}$
Short factoring proofs

Short factoring proofs #

This system proves knowledge of the factorization of an integer $\varN$. Unlike Product of two primes, this is not a proof that $\varN$ has two prime factors, only that the prover knows its factorization! This protocol is not easy to implement securely, so we recommend special attention to sections Choice of security parameters and Security pitfalls.

Goal: $\varprover$ convinces $\varverifier$ that they know the factorization of $\varN$ without revealing it.
  • Public input: An integer $\varN$
  • Private input: $\varprover$ knows the factorization of $\varN =\prod_i p_i^{e_i}$
  • Security parameters: The parameters $A, B, \ell, m$, and $K$ all depend on $k$ and the bit-size of $\varN$.

Vanilla interactive protocol #

Note: This version assumes that $\varverifier$ is honest. A dishonest one would send $\vare$ with similar size to $B$ and factor $\varN$ using this attack.

The following diagram shows one of the protocol’s $\ell$ iterations. $$ \begin{array}{c} \work{\varprover}{\varverifier} \alicework{\sampleRange{\varr}{A}} \alicework{\varz_i = \mathsf{gen}_\varz(\zns{\varN}, \{\varN, i\})} \alicework{\varx_i = \varz_i^\varr \mod \varN} \alicework{\forb} \alicebob{}{\bunch{\varx}, \bunch{\varz}}{} \bobwork{\sampleRange{\vare}{B}} \bobalice{}{\vare}{} \alicework{\vary = \varr + (\varN - \varphi(\varN))\cdot \vare \in \naturals} \alicebob{}{\vary}{} \bobwork{\vary \inQ \range{A}} \bobwork{\varN \gQ 1} \bobseparator \bobwork{\varx_i \equalQ \varz_i^{\vary- \vare\cdot\varN} \mod \varN \forb} \end{array} $$

Improved interactive protocol #

Note: This version assumes that $\varverifier$ is honest. A dishonest one would send $\vare$ with similar size to $B$ and factor $\varN$ using this attack.
$$ \begin{array}{c} \work{\varprover}{\varverifier} \alicework{\sampleRange{\varr}{A}} \alicework{\varz_i = \mathsf{gen}_\varz(\zns{\varN}, \{\varN, i\})} \alicework{\varX = \hash{\bunchi{\varz_i^\varr \mod \varN}}} \alicebob{}{\varX, \bunch{\varz}}{} \bobwork{\sampleRange{\vare}{B}} \bobalice{}{\vare}{} \alicework{\vary = \varr + (\varN - \varphi(\varN))\cdot \vare \in \naturals} \alicebob{}{\vary}{} \bobwork{\vary \inQ \range{A}} \bobwork{\varN \gQ 1} \bobseparator \bobwork{\varX \equalQ \hash{\bunchi{\varz_i^{\vary- \vare\cdot\varN} \mod \varN}}} \end{array} $$

Non-interactive protocol #

We use the Fiat-Shamir heuristic, and the prover creates $\vare$ using a $|B|$-bit sized hash function $\hashbit{\cdot}{|B|}$ and past public values. $$ \begin{array}{c} \work{\varprover}{\varverifier} \alicework{\sampleRange{\varr}{A}} \alicework{\varz_i = \mathsf{gen}_\varz(\zns{\varN}, \{\varN, i\})} \alicework{\varX = \hash{\bunchi{\varz_i^\varr \mod \varN}}} \alicework{\vare = \hashbit{\varN, \bunch{\varz},\varX}{|B|}} \alicework{\vary = \varr + (\varN - \varphi(\varN))\cdot \vare \in \naturals} \alicebob{}{\vare, \vary, \varX}{} \bobwork{\vary \inQ \range{A}} \bobwork{\varN \gQ 1} \bobseparator \bobwork{\varz_i = \mathsf{gen}_\varz(\zns{\varN}, \{\varN, i\})} \bobwork{\vare = \hashbit{\varN, \bunch{\varz},\varX}{|B|}} \bobwork{\varX \equalQ \hash{\bunchi{\varz_i^{\vary- \vare\cdot\varN} \mod \varN}}} \end{array} $$

Choice of security parameters #

We detail the choice of security parameters based on the bit-size of $\varN$:

  • $k$ – the security parameter; the cheating probability of the protocol is $2^{-k}$. Choose 80, 128 or 256.
  • $B$ and $\ell$ – the size of the challenge space and number of iterations; $B$ and $\ell$ should satisfy $\ell\cdot \log B = \theta(k)$, so chose $\ell=1$ and $B=2^k$ in the non-interactive protocol.
  • $A$ – the size of the commit space; $A$ must be smaller than $\varN$ and satisfy $(\varN - \varphi(\varN) ) \ell B \ll A < \varN$. If you are sure that public moduli are of a fixed size –like $|\varN| = 2048$– chose $A=2^{|\varN|}$. If the public modulus can have smaller bit-size but never below $|\varN| - 4$, chose $A=2^{|\varN| - 4}$.

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.

  • The two interactive protocols assume an honest verifier. To use this protocol in the context of malicious verifiers, use the non-interactive version. See Using HVZKP in the wrong context.

  • Implementers of this proof system need to carefully choose the security parameters since failing to do it correctly leaks $\varphi(\varN)$:

    Consider the example where $\varN$ is 2048 bits, the product of two 1024 bit primes. $\varprover$ computes over $\naturals$ the value $$\vary = \varr + (\varN - \varphi(\varN))\cdot \vare$$ where $\sampleRange{\varr}{A}$ and $\sampleRange{\vare}{B}$. If $A$ and $B$ have similar size then $\frac{r}{e}$ will be very small and $\varverifier$ can compute $$-\left\lfloor \frac{\vary}{e} \right \rfloor + \varN = \left\lfloor \frac{r}{e} \right \rfloor + \varphi (\varN) \approx \varphi(\varN) \enspace ,$$ recovering $\varphi(\varN)$.

    A variant of this attack happens when $|\frac{r}{e}| < \frac{|\varphi(\varN)|}{4}$: in this case, a quarter of the least significant bits of $\varphi(\varN)$ are unknown, but this still allows an attacker to factor $\varN$ using Coppersmith’s attack.

  • Using high security parameters with small modulus allows proof forgery: the security parameters $A=2^{2048}$, $B=2^{128}$ are configured to be used with modulus of size 2048 but the verification routine does not check the size of the modulus. A dishonest prover can send a proof of knowledge for a 1024 modulus and $$\vary = \varN \cdot \vare$$ will still be in the set $\range{A}$ since $\varN\cdot \vare < 2^{1025 + 129} < 2^{2048} = A$.

  • Verifier trusting prover on the non-interactive protocol: The $\varverifier$ does not generate the $\varz_i$ values and parses them from the proof without proper validation. The $\varz_i$ values should be generated as described here. Failing to do so, and not checking that $\varz_i\in\zns{\varN}$, $\varz_i \mod \varN \not\in \{ -1 , 0, 1\}$ leads to trivial proofs: when $\varz_i \equiv -1, 0, 1 \mod \varN$, all proofs are valid as long as $y\in \range{A}$.

  • Weak Fiat-Shamir transformation: In the non-interactive protocol, it is a common mistake to not include all values in the hash computation $\hashbit{\varN, \bunch{\varz},\varX}{|B|}$. If any of these values are not included in this computation, it could lead to a high severity issue where the prover can forge proofs. See Fiat-Shamir transformation for more details.

  • 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 generation of the $\varz$ values, such as an ID of the prover and the verifier and a timestamp. The verifier must check the validity of these values when they verify the proof.

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

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

Auxiliary procedures #

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

References #