$\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}}$
Paillier-Blum Modulus

Paillier-Blum Modulus #

This protocol allows the prover to show that a public modulus is the product of two $3 \; \mathsf{mod}\; 4$ prime numbers. Since safe-primes – primes of the form $p = 2q + 1$ where $q$ is also prime – are congruent with $3\; \mathsf{mod}\; 4$, this proof system can be used in those cases. Similar to the proof for Product of two primes, this system also uses the proof of Square freeness. This proof system is also much more efficient than the one for the Product of two primes.

Goal: $\varprover$ convinces $\varverifier$ that $\varN$ is the product of two primes congruent with $3\; \mathsf{mod}\; 4$, and that $\gcd(\varN, \varphi(\varN)) = 1$, without revealing its factorization.
  • Public input: modulus $\varN$
  • Private input: $\varprover$ knows $p,q$ such that $\varN = p q$. These are primes congruent with $3\; \mathsf{mod}\; 4$.
  • Security parameters: $m$ to achieve a cheating probability of $2^{-m}$

Interactive protocol #

Security note: The protocol is zero-knowledge (does not reveal the factorization of $\varN$) only when the verifier is honest and randomly generates each $\vary_i$. If the verifier chooses these values maliciously, they can recover the factorization of $\varN$. If your attacker model considers this, use the non-interactive version. More details on Using HVZKP in the wrong context.
$$ \begin{array}{c} \work{\varprover}{\varverifier} \alicework{\sampleN{\varw}{\varN} \text{ with }J(\varw, \varN) = -1} \alicebob{}{\varw}{} \bobwork{\sampleNs{\vary_i}{\varN} } \bobalice{}{\bunch{\vary}}{} \alicework{\varz_i = \vary_i^{\varN^{-1} \mod \varphi ( \varN )}} \alicework{\varx_i = \sqrt[4]{\vary_i'} \mod \varN} \alicework{\text{where } \vary_i' = (-1)^{\vara_i} \varw^{\varb_i} \vary_i \in QR_\varN} \alicework{\text{and } \vara_i, \varb_i \in \{0, 1\}\enspace\;\;} \alicework{\text{ for }i=1,\ldots,m} \alicebob{}{\bunchi{(\varx_i, \vara_i, \varb_i), \varz_i}}{} \bobwork{\varN \gQ 1} \bobwork{\varN \mod 2 \equalQ 1} \bobwork{\mathsf{isPrime}(\varN) \equalQ false} \bobwork{\varw \mod \varN \gQ 0} \bobwork{\varx_i \mod \varN \gQ 0} \bobwork{\varz_i \mod \varN \gQ 0} \bobwork{\vara_i, \varb_i \inQ \{0, 1\} } \bobwork{\text{ for }i=1,\ldots,m} \bobseparator \bobwork{ \varz_i ^\varN \equalQ \vary_i \mod \varN } \bobwork{ \varx_i ^4 \equalQ (-1)^{\vara_i} \varw^{\varb_i} \vary_i \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 $\vary_i$ and generates them using the $\mathsf{gen}_\vary$ 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{\sampleN{\varw}{\varN} \text{ with }J(\varw, \varN) = -1} \alicework{\vary_i = \mathsf{gen}_\vary(\zns{\varN}, \{\varN, \varw, i\})} \alicework{\varz_i = \vary_i^{\varN^{-1} \mod \varphi ( \varN )}} \alicework{\varx_i = \sqrt[4]{\vary_i'} \mod \varN} \alicework{\text{where } \vary_i' = (-1)^{\vara_i} \varw^{\varb_i} \vary_i \in QR_\varN} \alicework{\text{and } \vara_i, \varb_i \in \{0, 1\}\enspace\;\;} \alicework{\text{ for }i=1,\ldots,m} \alicebob{}{\varw, \bunchi{(\varx_i, \vara_i, \varb_i), \varz_i}}{} \bobwork{\varN \gQ 1} \bobwork{\varN \mod 2 \equalQ 1} \bobwork{\mathsf{isPrime}(\varN) \equalQ false} \bobwork{J(\varw, \varN) \equalQ -1} \bobwork{\varw \mod \varN \gQ 0} \bobwork{\varx_i \mod \varN \gQ 0} \bobwork{\varz_i \mod \varN \gQ 0} \bobwork{\vara_i, \varb_i \inQ \{0, 1\} } \bobwork{\text{ for }i=1,\ldots,m} \bobseparator \bobwork{\vary_i = \mathsf{gen}_\vary(\zns{\varN}, \{\varN, \varw, i\})} \bobwork{ \varz_i ^\varN \equalQ \vary_i \mod \varN } \bobwork{ \varx_i ^4 \equalQ (-1)^{\vara_i} \varw^{\varb_i} \vary_i \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 the modulus $\varN$; see Using HVZKP in the wrong context.
  • Not checking that $\varN \mod 2 \equalQ 1$ and $\varN \gQ 1$ before computing the Jacobi symbol $J(\varw, \varN)$: the Jacobi symbol is only defined when $\varN$ is an odd positive integer. Failing to verify this might lead to a program panic, as in the Go library.
  • Verifier trusting prover on the non-interactive protocol:
    • $\varverifier$ does not check that $J(\varw, \varN) = -1$: high severity issue since this allows $\varprover$ to submit a proof forgery with $\varw = 0$ and $\varx_i = 0$.
    • $\varverifier$ uses $\vary_i$ values provided by $\varprover$ instead of generating them: high severity issue since the prover can trivially forge proofs (e.g., by sending $\rhovar_i=1, \sigmavar_i=1$).
    • $\varverifier$ does not validate $\varw, \varz_i, \varx_i$ as valid values modulo $\varN$ (between 0 and $\varN -1)$: this allows replaying the same proof with different values with $\varz_i + k\varN$.
    • $\varverifier$ does not compare the number of received tuples $(\varx_i, \vara_i, \varb_i), \varz_i$ with $m$: this can lead to the prover bypassing proof verification by sending an empty list, or fewer than $m$ elements.
  • Reusing the same $\varw$ for further proofs of $\varN$: reusing the same $\varw$ value means that for a fixed $\varN$, the $\vary_i$ values will be the same; if the algorithm that computes the fourth-root is probabilistic, it can reveal different fourth-roots for the same value $\vary_i’$, allowing an attacker to factor $\varN$. Solve this in one of two ways: either add a fresh value to the parameters of $\mathsf{gen}_\vary$ and share it with $\varverifier$, or ensure that you deterministically compute the fourth-roots.
  • 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 $\vary_i$ 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.

Choice of security parameters #

To achieve a safe security level, choose:

  • $|\varN| = 2048$
  • $m = 80$.

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

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

Auxiliary algorithms #

  • The function $J(\varw, \varN)$ is the Jacobi symbol of $\varw$ modulo $\varN$. To implement it use Algorithm 2.149 of the Handbook of Applied Cryptography.
  • Compute modular fourth-roots using [HOC - Fact 2.160]: if $x$ is a quadratic residue modulo $\varN = p q$ (and $p,q$ are $3\mod 4$) then $\sqrt[2]{x} = x^{(\varphi + 4)/8} \mod \varN$, where $\varphi = (p-1)\cdot(q-1)$. Applying this computation twice yields the modular fourth-root: $\sqrt[4]{x} = x^{((\varphi + 4)/8)^2} \mod \varN$. Since the exponent does not depend on the input $x$, it can be computed once and for all.
  • The prover has to check if an element is a quadratic residue modulo $\varN$. To do this, use [HOC - Fact 2.137]: $x$ is a quadratic residue modulo $\varN = pq$ if and only if it is a quadratic residue modulo $p$ and modulo $q$. A number $x$ is a quadratic residue modulo a prime $p$, if $x^{(p-1)/2} = 1$. Thus, $x$ is a quadratic residue modulo $\varN = pq$ if and only if $x^{(p-1)/2} = 1$ and $x^{(q-1)/2} = 1$.
  • Most libraries will have a primality testing routine for the $\mathsf{isPrime}$ function.

References #