<figure><img src="image_1.png" /></figure>

HAL
open science

# Compact zero-knowledge arguments for Blum integers

Jules Maire, Damien Vergnaud

► To cite this version:

Jules Maire, Damien Vergnaud. Compact zero-knowledge arguments for Blum integers. Theoretical Computer Science, 2025, 1038, pp.115155. 10.1016/j.tcs.2025.115155. hal-04987985

HAL Id: hal-04987985

https://hal.science/hal-04987985v1

Submitted on 13 Mar 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
## 1.1. Related work

The problem of proving properties of integers, especially their structure and primality, has been extensively studied in cryptography. Blum's pioneering work [4] introduced a cryptographic protocol that leverages Blum integers to enable secure coin flipping, providing a foundation for verifiable cryptographic protocols and solving problems that seemed impossible in traditional communication settings. The use of Blum integers in cryptographic protocols has found numerous applications (e.g. in digital signatures [13], pseudo-random generators [3], public-key encryption [14], identity-based encryption [7], ...). In these applications, it is of utmost importance for security to ensure that the used integer $n$ is indeed of the form $n = pq$ where $p$ and $q$ are prime numbers with $p \equiv q \equiv 3 \mod 4$ and $p \approx q \approx \sqrt{n}$ without revealing any further information on $p$ and $q$.

Blum [4] and Van de Graaf and Peralta [21] proposed zero-knowledge proofs that an integer $n$ is of the form $n = p^s q^r$ where $p \equiv q \equiv 3 \mod 4$ are primes. Boyar, Friedl and Lund [6] and Gennaro, Micciancio and Rabin [9] presented proofs that an integer $n$ is square-free. Liskov and Silverman [17] described a protocol to prove that $n$ is a product of two nearly equal primes. By combining these techniques, one can obtain zero-knowledge proofs that an integer is indeed well-formed for the aforementioned applications. Many works have been devoted to improving these protocols and we refer to Mao's comprehensive work [20] and the recent practical optimizations due to Liu, Weng, Zhang, He and Huang [18]. For a 128-bit security level and a 2048-bit integer $n$, the most communication-efficient protocol from [18] that only proves that $n$ is a Blum integer (but not that $p \approx q \approx \sqrt{n}$) has a communication complexity of more than 32 KBytes. Using [17], a proof $p \approx q \approx \sqrt{n}$ will increase the proof size by more than 98 KBytes (for a total proof size of over 131 KBytes).

## 1.2. Contributions of the paper

In this work, we employ the “MPC-in-the-head” paradigm [15] to construct a succinct argument of knowledge for the factorization of Blum integers. This cryptographic technique transforms secure multi-party computation (MPC) protocols into efficient zero-knowledge proof/argument systems. The prover simulates an MPC protocol “in their head”, acting as all parties involved in the computation. Instead of executing the protocol over a network, the prover commits to the simulated views of the parties and selectively reveals information based on a challenge from the verifier. This process ensures that the verifier can check the correctness of the computation without learning anything about the prover’s private inputs. In our protocol, the prover performs an additive sharing of the prime numbers $p$ and $q$ over the integers (instead of using modular additive sharing, as is often the case within the “MPC-in-the-head” paradigm). This approach was introduced in [8] in other settings and allows for a very straightforward demonstration that $p \approx q \approx \sqrt{n}$ without relying on costly range proofs on $p$ and $q$. It also permits proving readily that $p \equiv q \equiv 3 \mod 4$. It thus only remains to prove that the integers $p$ and $q$ are indeed prime numbers and, for that, we use the Boneh-Franklin “biprimality” test [5] that is perfectly suited for MPC computation with additive sharing. For a 128-bit security level and a 2048-bit integer $n$, we can obtain an argument as small as 6.3 KBytes (with a prover and verifier computational efficiency comparable to the 131 KBytes proof obtained by combining [18] and [17]).

## 2. Preliminaries

We assume the reader is familiar with standard cryptographic concepts and the MPC-in-the-Head paradigm; for details, we refer to [1,2,8,15]. We denote the set of integers $\{m, ..., n\}$ by $[m, n]$ with $m < n$ and by $\mathbb{P}$ the set of prime numbers. All logarithms are base 2. Pr denotes a probability function. For computationally secure algorithms, $\lambda$ denotes the security parameter, given as input in unary form $1^{\lambda}$. Unless otherwise stated, algorithms are randomized, and PPT stands for “probabilistic polynomial-time” in the security parameter. Two distributions $\{D_{\lambda}\}_{\lambda}$ and $\{\tilde{D}_{\lambda}\}_{\lambda}$ are called $(t, \zeta)$-indistinguishable if, for any algorithm A running in time at most $t(\lambda)$, we have

$$|\Pr[A(1^{\lambda}, x) = 1 | x \stackrel{s}{\leftarrow} D_{\lambda}] - \Pr[A(1^{\lambda}, x) = 1 | x \stackrel{s}{\leftarrow} \tilde{D}_{\lambda}]| \le \zeta(\lambda).$$

### 2.1. MPC-in-the-head

**Zero-knowledge argument** A zero-knowledge protocol for a polynomial-time decidable binary relation $\mathcal{R}$ involves a prover $P$ and a verifier $V$, both given a common input $x$. Moreover, $P$ holds a witness $w$ such that $(x, w) \in \mathcal{R}$. The protocol consists of a set of passes between $P$ and $V$ until $V$ outputs a bit $b$ (1 to accept the proof, 0 to reject). This sequence is called transcript, denoted as $\langle P(x, w), V(x) \rangle$. In this work, one considers a family of such proofs, named zero-knowledge arguments of knowledge (ZKA), where a PPT prover convinces a PPT verifier that they know $w$. Such a ZKA shall satisfy:

- $\alpha$-completeness: if for all $\lambda \in \mathbb{N}$ and all $(x, w) \in \mathcal{R}$ with $x \in \{0, 1\}^{\lambda}$, $\Pr[\langle P(x, w), V(x) \rangle = 1] \ge 1 - \alpha(\lambda)$ (i.e. $P$ succeeds in convincing $V$ except with probability $\alpha$).

- $\epsilon$-knowledge soundness, if for all PPT malicious prover $\tilde{P}$ such that for all $\lambda \in \mathbb{N}$ and all $x \in \{0, 1\}^{\lambda}$, $\tilde{\epsilon}(\lambda) := \Pr[\langle \tilde{P}(x), V(x) \rangle = 1] > \epsilon(\lambda)$, there exists a PPT algorithm $E$ (called the extractor) which, given rewindable black-box access to $\tilde{P}$, outputs a witness $w$ such that $(x, w) \in \mathcal{R}$ in time poly$(\lambda, (\tilde{\epsilon} - \epsilon)^{-1})$ with probability at least $1/2$.

- $(t, \zeta)$-zero-knowledge, if for every PPT malicious verifier $\tilde{V}$, there exists a PPT algorithm $S$ (called the simulator) which, for all $\lambda \in \mathbb{N}$ and all $(x, w) \in \mathcal{R}$ with $x \in \{0, 1\}^{\lambda}$, given the input statement $x \in \{0, 1\}^{\lambda}$ and rewindable black-box access to $\tilde{V}$, $S$ outputs a simulated transcript whose distribution is $(t, \zeta)$-indistinguishable from $\langle P(x, w), \tilde{V}(x) \rangle$.
If the zero-knowledge property holds only for the genuine verifier V, then the protocol is deemed honest-verifier zero-knowledge. In that case, S is given random challenges instead of a rewindable black-box access to $\tilde{V}$.

**Multiparty-computation** Multiparty-computation involves multiple parties collaborating to compute a function. Secure multiparty computation (MPC) aims to ensure that this distributed computing is both correct in its output and private in its inputs.

**MPC-in-the-head** The concept of MPC-in-the-head (MPCitH) [15] offers an elegant way to construct ZKAs using secure MPC protocols. Given an $\mathcal{N}^d$-statement $x \in \mathcal{L}$ for a relation $\mathcal{R}$, the MPCitH paradigm builds a ZKA for a witness $w$ for this statement (i.e., $\mathcal{R}(x, w) = 1$). Specifically, it relies on computing a broadcasting MPC realizing the functionality $f$ defined as:

$$f(x, w) = \begin{cases} 1 & \text{if } \mathcal{R}(x, w) = 1, \\ 0 & \text{otherwise.} \end{cases}$$

The prover first shares the secret input $w$ among $N$ virtual parties, simulates all the parties' computation, and commits to each party's view (including input share, secret random tape, and broadcast values) to V. Then, V requests P to reveal all-but-one parties' views. Upon receiving them, V verifies their consistency with an honest execution of the MPC protocol and the commitments. The security of the ZKA relies on the one of the MPC protocol. A malicious prover who does not know a valid witness has at most $1/N$ chance of not being caught by V (its best strategy is to cheat on one party).

Some common optimizations like the use of so-called GGM trees [10] to reduce the communication are used in this paper.

## 2.2. Hypercube optimization

Aguilar Melchor, Gama, Howe, Hülsing, Joseph and Yue [1] introduced a geometrical approach to optimize the MPC emulation phase based on additive sharing. In a nutshell, instead of simulating an MPC with $N$ parties, P emulates $\log(N)$ MPCs with 2 parties. Given $N = k^d$ parties, let us consider some $d$-dimensional hypercube of length $k$ formed by the $N$ shares. By fixing one dimension, the $N$ shares are regrouped into $k$ subsets (with the rule that shares belong to the same subset if they lie over the same hyperplane). Applying the addition law on these subsets produces $k$ hyper-shares. This process extends to the $d$ dimensions, reducing the problem to $d$ MPCs with $k$ parties. With $k=2$ and $d = \log(N)$, the party count reduces to $\log(N) + 1$. This optimization often makes MPC emulation less computationally expensive, allowing larger party sizes and smaller proof sizes, while keeping the computational cost of the proof manageable. However, the initial setup, like generating the GGM tree and preparing shares, can still be costly, independent of the hypercubing optimization. We refer to [1] for further details.

## 2.3. Sharing over the integers

We also make use of an efficient technique developed in [8] to encode a secret $x \in [0, \ell]$ over the integers in the MPCitH paradigm, i.e. $x = \sum_{i=1}^N \llbracket x \rrbracket_i + \Delta x$ where $\llbracket x \rrbracket_i \stackrel{\$}{\leftarrow} [0, A-1]$ (with no modular reduction). This technique was first introduced to share small elements $x < B \ll \ell$ over large rings $Z_\ell$ by taking $B \ll A \ll \ell$. Typically, if $B=2$ (i.e. $x$ is a bit), Feneuil, Maire, Rivain and Vergnaud [8] considered $A \approx 2^{13}$ which drastically reduced the sharing cost for large $\ell$ like $\ell \approx 2^{256}$. To avoid information leakage, Feneuil et al. introduced the possibility for P to abort depending on the views to open requested by V. This induces a rejection rate of $(B-1)/A$ in the protocol that can be decreased by increasing $A$ (but it increases communication complexity). This technique can be extended to share any (not necessarily small) element $x \in Z_\ell$ over the integers by selecting $A \gg \ell$, and the rejection rate of the sharing becomes $(\ell - 1)/A$. We refer to [8] for further details.

## 2.4. Product verification

The MPCitH framework used in conjunction with a linear secret sharing scheme makes all linear operations free to prove in terms of elements to send to V. Multiplicative relationships in a finite field $\mathbb{F}$, on the other hand, are the most cumbersome part.

Given a triple of linear shareings $(\llbracket x \rrbracket, \llbracket y \rrbracket, \llbracket z \rrbracket)$ with $x, y, z \in \mathbb{F}$, we would like to build a protocol to check that $xy = z$. To this end, we can use the solution suggested in [16,2] by "sacrificing" another triple $(\llbracket a \rrbracket, \llbracket b \rrbracket, \llbracket c \rrbracket)$ that satisfies $ab = c$. The second triple can be used a single time (to preserve the zero-knowledge property), hence the "sacrifice". As an optimization, we can take $a$ at random, and fix $b = y$. A description of the protocol is presented in Protocol 1.

1. The parties get a random $\epsilon \in \mathbb{F}$ from the verifier;

2. The parties locally sets $\llbracket \alpha \rrbracket = \epsilon \llbracket x \rrbracket + \llbracket a \rrbracket$;

3. The parties open $\alpha$ by broadcasting their shares;

4. The parties locally sets $\llbracket v \rrbracket = \alpha \llbracket y \rrbracket - \llbracket c \rrbracket - \epsilon \llbracket z \rrbracket$;

5. The parties open $v$ by broadcasting their shares;

6. The parties output 1 if $v=0$ and 0 otherwise.

Protocol 1: Baum-Nof protocol for product verification.

If $(\llbracket x \rrbracket, \llbracket y \rrbracket, \llbracket z \rrbracket)$ is an incorrect multiplication triple, or if $(\llbracket a \rrbracket, \llbracket c \rrbracket)$ does not satisfy the relation $ay = c$, then the parties accept with probability at most $|\mathbb{F}|^{-1}$. In terms of complexity, since $b = y$ and $a$ is a random field element, the communication cost of the sacrifice
triple is the cost of the sharing of $c$, that is of an auxiliary value $\Delta c$ (using common optimizations in MPCitH). Moreover, the prover has to send the broadcast value $\alpha$. The overall number of bits to send is then $2 \log |\mathbb{F}|$.

## 2.5. Boneh-Franklin biprimality test

Let $n$ be an integer. Boneh and Franklin [5] considered the groups $\mathbb{Z}_n$ and $\mathbb{T}_n = (\mathbb{Z}_n[X]/(X^2 + 1))/(\mathbb{Z}_n)^*$ to design the following bi-primality test:

**Lemma 1.** Let $n = pq$ be an integer with $p \equiv q \equiv 3 \pmod 4$. Let $g$ be a random element in $\mathbb{Z}_n^*$ such that the Jacobi symbol $(\frac{g}{n}) \neq 1$ and $h \in \mathbb{T}_n$, and let us consider $t := g^{(n-p-q+1)/4}$ mod $n$ and $u := h^{n+p+q+1} \in \mathbb{T}_n$. If $n$ is a product of two distinct primes, then $t \equiv \pm 1 \pmod n$ and $u = 1$. Otherwise, with probability at least $1/2$ (over the random choice of $g$ and $h$), $t \neq \pm 1 \pmod n$ or $u \neq 1$.

**Proof.** See Lemma 4.1 in [5].

# 3. Description of our zero-knowledge argument

## 3.1. MPC protocol to check that a number is a Blum integer

Let $n = pq$ be a Blum integer with $p, q$ distinct $\gamma$-bit prime numbers such that $p \equiv q \equiv 3 \pmod 4$. Let $m \in \mathbb{N}$ be such that $n = 4m + 1$ (it exists since $n$ is a Blum integer). In this section, we present a MPC protocol for $N \ge 2$ parties, whose purpose is to check whether the secrets $p, q$ (shared additively over the integers among the $N$ parties) are two distinct primes congruent to 3 modulo 4, and whether they satisfy $pq = n$, without revealing any information about the factors of $n$. For ease of exposition, we assume that the parties actually hold additive share of $p' = (p-3)/4$ and $q' = (q-3)/4$ such that $n = (4p' + 3) \cdot (4q' + 3)$ and $p'$ and $q'$ are $\lambda - 2$-bits integers. Each party thus holds shares $[[p']_i$ and $[[q']_i$ in $[0, A-1]$ for some integer $A > 2^{\gamma-3}$ such that $p' = [[p']_1 + \cdots + [[p']_N$ and $q' = [[q']_1 + \cdots + [[q']_N$. To ensure the soundness of the future ZKA, we introduce this protocol with a random prime number $\ell$ in $[2^{\kappa-1}, 2^{\kappa-1}]$, a set of $\eta$ random elements $g_1, \dots, g_\eta \in \mathbb{Z}_n^*$ whose Jacobi symbol satisfy $(\frac{g_j}{n}) \neq 1$ for all $j \in [1, \eta]$ and a set of $\eta$ public random $h_1, \dots, h_\eta \in \mathbb{T}_n$. We denote $[[p'] = ([[p']_1, \dots, [[p']_N)$ the sharing of $p'$, $[[p]] = [[4p' + 3]] = (([4p' + 3])_1, [[4p']_2, \dots, [[4p']_N)$ the corresponding sharing of $p$ (and similarly for $q'$ and $q$) and $[[n]] = (n, 0, \dots, 0)$ the sharing of the public integer $n$. A description of the MPC protocol is presented in Protocol 2.

**Input:** The parties hold two secret shareings over the integers of the $(\lambda-2)$-bit integers $p' = (p-3)/4$ and $q' = (q-3)/4$, a prime number $\ell$ in $[2^{\kappa-1}, 2^{\kappa-1}]$, a set of $\eta$ public random $g_1, \dots, g_\eta \in \mathbb{Z}_n^*$ such that the Jacobi symbol $(\frac{g_j}{n}) \neq 1$ for each $j \in [1, \eta]$ and a set of $\eta$ public random $h_1, \dots, h_\eta \in \mathbb{T}_n$.

1. The parties check that $(4[[p'] + 3)(4[[q'] + 3)] = [[p]][[q]] = [[n]] \mod \ell$ via the Baum-Nof Protocol 1 in the finite field $\mathbb{Z}_\ell$.

2. Each party $i \in [1, N]$ locally computes $t_{i,j} := g_j^{[[p']_i + [[q']_i]}$, mod $n$ and $u_{i,j} = n^4([[[p']_i] + [[q']_i]]^\lambda)$ for every $j \in [1, \eta]$ and broadcasts them.

3. The parties output 1 if they output 1 in the Protocol 1 and if $g_j^{(m-1)/\prod_{i=1}^N t_{i,j}} = \pm 1 \pmod n$ and $h_j^{m+7} \prod_{i=1}^N u_{i,j} = 1$ for all $j \in [1, \eta]$, otherwise they output 0.

**Protocol 2:** MPC protocol to check that a number is a Blum integer.

In this protocol, one uses that $n - (p + q) + 1 = 4m + 1 - (4p' + 3 + 4q' + 3) + 1 = 4(m - 1 - p' - q')$ is a multiple of 4. Note that the $t_{i,j}$ and $u_{i,j}$ can be locally computed by the parties, leading to a multiplicative sharing of $g_j^{(n-p-q+1)/4}$ in $\mathbb{Z}_n^*$ and $h_j^{n+p+q+1}$ in $\mathbb{T}_n$ for all $j \in [1, \eta]$. This implicit conversion from additive sharing (over the integers) to multiplicative sharing (in $\mathbb{Z}_n^*$ and $\mathbb{T}_n$) is similar to the one used in [19].

## 3.2. Our zero-knowledge argument

We describe our identification Scheme 3 for Blum integers relying on the MPC Protocol 2. The protocol makes use of a pseudo-random generator PRG, a tree-based pseudo-random generator TreePRG, two collision-resistant hash functions $H_1, H_2$ and a commitment scheme Com. The protocol halts if the Check procedure is not fulfilled.

**Performances** Let $\epsilon$ be the soundness error of one repetition of the protocol. To reach a target soundness error of $2^{-\lambda}$, we repeat our protocol $\tau$ times during parallel executions such that $\epsilon^\tau \le 2^{-\lambda}$, yielding to a total size of the messages sent by the prover of:

$$ \underbrace{4\lambda}_{h,h'} + \tau(2\log_2 \ell + 2\log_2(A-1)) + \underbrace{\lambda \log_2 N}_{y_1, y_2} + \underbrace{2\lambda}_{\text{co-path}_{j*}} + \underbrace{\eta}_{t_1, \dots, t_\eta} ) \text{ bits.} $$

For a modulus $n$ of 2028 bits (achieving 112 bits of security for RSA) with $p$ and $q$ of 1024 bits and targeting 128 bits of security for our ZKA, with $N = 2^8$ parties and $\eta = \log_2 N$, we get a proof size of 8.13 KB with a rejection rate below 14% (with $A = 2^{1033}$ and $\kappa = 21$). By taking larger $N = 2^{11}$ (thanks to the hypercubing technique), we can decrease the proof size to 6.23 KB with a rejection rate below 0.8% (with $A = 2^{1037}$ and $\kappa = 25$).
$$ \mathcal{L} = \{n \in \mathbb{N} \mid \exists p, q \in \mathbb{P} \text{ with } p \neq q, pq = n, \text{ and } p \equiv q \equiv 3 \mod 4, p, q < 2^{\gamma-1}\} $$

with $(1 - \frac{2^{\gamma-3}}{A})^2$-completeness, and $[\frac{1}{N} + (1 - \frac{1}{N})(\frac{2\log(NA)+1}{2^{\kappa-1}} + \frac{1}{2^{\eta}}) + \text{negl}]$-special soundness, where N is the number of parties emulated by the prover, $\Lambda, \kappa, \eta \in \mathbb{N}$ are parameters of the scheme, and negl is a negligible function in the security parameter.

**Sketch of proof.** Completeness. For any sampling of the random coins of P and V, if the computation described in the Protocol 3 is honestly performed, and if there is no abort, all the checks of V pass. The completeness probability is therefore of $1 - \text{Pr[abort]} = (1 - \frac{2^{\gamma-3}}{A})^2$, where “abort” denotes the abortion event, which from [8] implies the theorem statement. We note that the square appears since we are dealing with two shareings over the integers and that we are sharing elements smaller than $2^{\gamma-3}$ over a set $[0, A-1]$ with $A > 2^{\gamma-3}$. Moreover, Lemma 1 proves that the test of biprimality used in our protocol always outputs 1 when it is honestly performed.

**Soundness.** For simplicity, we assume that the commitment scheme is perfectly binding (if it were computationally binding, we would need to handle cases where the extractor produces a commitment collision). For any two successful transcripts $T_1, T_2$ with the same commitment and two different challenges for the unopened party $i_{T_1}^* \neq i_{T_2}^*$, either the opened shares of $[[p']]$ (or $[[q']]$) are inconsistent, leading to a hash collision, or the openings are unique, defining the witness $p, q$ (and this witness can be recovered). Let us call $[[p'], [[q']]]$ a valid witness if $(4p' + 3)(4q' + 3) = pq = n$, and if $p \equiv q \equiv 3 \mod 4$ are distinct primes. For the rest, we assume that the extractor only processes consistent shares (otherwise, it would detect a hash collision). Let $R_h$ denote the randomness used by $\tilde{P}$ to generate the initial commitment $h$, and $r_h$ a possible realization of $R_h$. The extractor procedure is described as follows:

1. Repeat $+\infty$ times:

2. Run $\tilde{P}$ with honest V to get transcript $T_1$

3. If $T_1$ is not a successful transcript, go to the next iteration

4. Do $N_1$ times:

5. Run $\tilde{P}$ with honest V and same $r_h$ as $T_1$ to get transcript $T_2$

6. If $T_2$ is a successful transcript, $i_{T_1}^* \neq i_{T_2}^*$ and $(T_1, T_2)$ reveals a valid witness

7. Return $(T_1, T_2)$

**Protocol 4: Extractor E.**

We estimate the extraction complexity, i.e., the average number of times the extractor calls $\tilde{P}$.

Let $\text{succ}_{\tilde{P}}$ be the event that $\tilde{P}$ convinces V, with $\text{Pr}[\text{succ}_{\tilde{P}}] = \tilde{\epsilon}$. Fix $\alpha \in (0, 1)$ such that $(1 - \alpha)\tilde{\epsilon} > \epsilon$. Call $r_h$ good if $\text{Pr}[\text{succ}_{\tilde{P}} | R_h = r_h] \ge (1 - \alpha)\tilde{\epsilon}$. By the Splitting Lemma, $\text{Pr}[r_h \text{ good} | \text{succ}_{\tilde{P}}] \ge \alpha$. Assume that we sample a successful transcript $T_1$ with a good $r_h$.

Let us prove by contraposition that if $r_h$ is good, then the witness is valid. Assume that the witness in $T_1$ is invalid. This means that, if the shareings are genuine, either the product test or the bi-primality test outputs a false positive. Let $\text{FP}_0$ be the event that the random prime $\ell$ divides the integer $n - (4p' + 3)(4q' + 3)$ if it is different from 0. By the size check, the absolute value of this integer is smaller that $(NA)^2$ and is thus divisible by at most $2\log(NA)/(\kappa - 1)$ $\kappa$-bit primes. Since the number of such primes is at least $2^{\kappa-1}/(\kappa - 1)$, we get $\text{Pr}[\text{FP}_0] \le \frac{2\log(NA)}{2^{\kappa-1}}$. Let $\text{FP}_1$ be the event of a false positive in the product check (i.e. $\text{Pr}[\text{FP}_1] \le \frac{1}{\ell}$), and $\text{FP}_2$ be the event of a false positive in the bi-primality check (i.e. $\text{Pr}[\text{FP}_2] \le \frac{1}{2^\eta}$). Then, the event of a false positive (FP) of Protocol 2 has probability $\text{Pr}[\text{FP}] \le \text{Pr}[\text{FP}_0] + \text{Pr}[\text{FP}_1] + \text{Pr}[\text{FP}_2] \le \frac{2\log(NA)+1}{2^{\kappa-1}} + \frac{1}{2^\eta}$. The probability that the inner loop finds a successful transcript is:

$$ \text{Pr}[\text{succ}_{\tilde{P}} | R_h = r_h] \le \text{Pr}[\text{succ}_{\tilde{P}}, \text{FP} | R_h = r_h] + \text{Pr}[\text{succ}_{\tilde{P}}, \neg \text{FP} | R_h = r_h] \\ \le \frac{2\log(NA)+1}{2^{\kappa-1}} + \frac{1}{2^\eta} + \left(1 - \frac{2\log(NA)+1}{2^{\kappa-1}} - \frac{1}{2^\eta}\right) \text{Pr}[\text{succ}_{\tilde{P}} | \neg \text{FP}, R_h = r_h]. $$

Having a successful transcript when $\neg \text{FP}$ occurs implies the prover must cheat for at least one party. Cheating for multiple parties fails, while cheating for exactly one party succeeds with probability at most $1/N$. Thus, $\text{Pr}[\text{succ}_{\tilde{P}} | R_h = r_h, \neg \text{FP}] \le 1/N$ and we have $\text{Pr}[\text{succ}_{\tilde{P}} | R_h = r_h] \le \frac{2\log(NA)+1}{2^{\kappa-1}} + \frac{1}{2^\eta} + \left(1 - \frac{2\log(NA)+1}{2^{\kappa-1}} - \frac{1}{2^\eta}\right) \frac{1}{N} = \epsilon < (1 - \alpha)\tilde{\epsilon}$, meaning that $r_h$ is not good. By contraposition, we get that if $r_h$ is good, then the witness is valid. Now, let us lower bound the probability that the i-th iteration of the inner loop finds a successful transcript $T_2$ (whose event is denoted as $\text{succ}_{\tilde{P}}^{T_2}$) such that $i_{T_1}^* \neq i_{T_2}^*$ given a good $r_h$.

$$ \begin{align*} \text{Pr}[\text{succ}_{\tilde{P}}^{T_2} \cap (i_{T_1}^* \neq i_{T_2}^*) | r_h \text{ good}] & \\ &= \text{Pr}[\text{succ}_{\tilde{P}}^{T_2} | r_h \text{ good}] - \text{Pr}[\text{succ}_{\tilde{P}}^{T_2} \cap (i_{T_1}^* = i_{T_2}^*) | r_h \text{ good}] \\ &\ge (1 - \alpha)\tilde{\epsilon} - \text{Pr}[i_{T_1}^* = i_{T_2}^* | r_h \text{ good}] \\ &= (1 - \alpha)\tilde{\epsilon} - 1/N \\ &\ge (1 - \alpha)\tilde{\epsilon} - \epsilon. \end{align*} $$
Let define $p_0 := (1 - \alpha)\tilde{c} - \epsilon$. By running $\rho$ times $\tilde{P}$ with the same $r_h$ as for $T_1$, we hence obtain a second non-colliding transcript $T_2$ with probability at least $1/2$ when $\rho \approx \frac{\ln(2)}{\ln(\frac{1}{1-p_0})} \le \frac{\ln(2)}{p_0}$.

Let $C$ denote the number of calls to $\tilde{P}$ made by the extractor before finishing. In each iteration, the extractor makes one call to $\tilde{P}$ to obtain $T_1$. If $T_1$ is not successful, which occurs with probability at least $(1 - \text{Pr}[\text{succ}_{\tilde{P}}])$, the extractor continues to the next iteration and makes an average of $\mathbb{E}[C]$ calls to $\tilde{P}$. If $T_1$ is successful, which occurs with probability $\text{Pr}[\text{succ}_{\tilde{P}}]$, either $r_h$ is good which happens with probability $\alpha$ and the extractor makes at most $\rho$ calls to $\tilde{P}$ in the inner loop of $E$ and outputs a pair $(T_1, T_2)$ with probability $1/2$, or the extractor makes $\rho$ calls to $\tilde{P}$ in the inner loop of $E$ without stopping, with probability at most $(1 - \frac{\alpha}{2})$. The expected number of calls to $\tilde{P}$ hence satisfies:

$$ \begin{aligned} \mathbb{E}[C] &\le 1 + (1 - \text{Pr}[\text{succ}_{\tilde{P}}])\mathbb{E}[C] + \text{Pr}[\text{succ}_{\tilde{P}}]\left(\rho + \left(1 - \frac{\alpha}{2}\right)\mathbb{E}[C]\right) \\ &\underbrace{\qquad\qquad\qquad\qquad\qquad\qquad}_{T_1 \text{ unsuccessful}} \\ &\le 1 + \tilde{c}\rho + \mathbb{E}[C]\left(1 - \frac{\tilde{c}\alpha}{2}\right) \\ &\le \frac{2}{\alpha\tilde{c}}(1 + \tilde{c}\rho) \\ &\le \frac{2}{\alpha\tilde{c}}\left(1 + \tilde{c}\frac{\ln(2)}{(1 - \alpha)\tilde{c} - \epsilon}\right) \end{aligned} $$

To obtain an $\alpha$-free formula, let us take $\alpha$ such that $(1 - \alpha)\tilde{c} = \frac{1}{2}(\tilde{c} + \epsilon)$. We have $\alpha = \frac{1}{2}(1 - \frac{\epsilon}{\tilde{c}})$ and the average number of calls to $\tilde{P}$ is upper bounded by $\frac{4}{\tilde{c}-\epsilon}(1 + \tilde{c}\frac{2\ln(2)}{\tilde{c}-\epsilon})$ which concludes the proof.

**Zero-knowledge.** The abortion event must be independent of the secret $(p, q)$ to ensure no information is leaked by the abortion, as shown in [8]. When there is no abort, the transcript includes $(y_1, y_2)$, computed from the secret. It can be shown that, given no abort and the shares $\{\|p'\|_i\}_{i \ne i^*}$, the distribution of $y_1$ is uniform in $[2^{\gamma-3} - A, 0]$, ensuring no information about the secret is leaked. The same applies to $y_2$.

Now, we describe the simulator $S$ (which produces transcripts indistinguishable from real ones without knowing the secret), with oracle access to some PPT $\tilde{V}$, as follows:

1. Sample a challenge $i^* \stackrel{S}{\leftarrow} [1, N]$.

2. Sample mseed $\stackrel{S}{\leftarrow} \{0, 1\}^\lambda$.

3. Compute parties' seeds $(\text{seed}_i, \rho_i)_{i \in [1, N]}$ with TreePRG(mseed).

4. For each party $i \in [1, N] \setminus \{i^*\}$, set $\|p'\|_i, \|q'\|_i, \|\alpha\|_i, \|c\|_i \leftarrow \text{PRG}(\text{seed}_i)$ and $\text{com}_i = \text{Com}(\text{seed}_i; \rho_i)$.

5. Sample $y_1, y_2 \stackrel{S}{\leftarrow} \{2^{\gamma-3} - A, \dots, 0\}$, and $\{\Delta t_j \stackrel{S}{\leftarrow} \mathbb{Z}_n\}_{j \in [1, \eta]}$. Define $\Delta p' = y_1 - \sum_{i \ne i^*} \|p'\|_i$ and $\Delta q' = y_2 - \sum_{i \ne i^*} \|q'\|_i$.

6. Sample a random commitment $\text{com}_{i^*}$.

7. Call $\tilde{V}$ with the hash digest $h$ of $\Delta p'$, $\Delta q'$ (and of the commitments of the seed and associated randomness of each party) and get a random prime $\ell$.

8. Sample $\Delta c \stackrel{S}{\leftarrow} \mathbb{Z}_\ell$ and send it to $\tilde{V}$ to get challenges $\epsilon, \{g_j\}_{j \in [1, \eta]}$ and $\{h_j\}_{j \in [1, \eta]}$.

9. Sample $\alpha \stackrel{S}{\leftarrow} \mathbb{Z}_\ell$.

10. Sample $\{t_j\}_{j \in [1, \eta]} \in \{-1, 1\}^\eta$ and simulate computation of parties $i \ne i^*$ to get $\{\{t_{i,j}, u_{i,j}\}_{j \in [1, \eta]}, \|\alpha\|_i, \|v\|_i\}_{i \ne i^*}, (\Delta\alpha, \Delta v, \dots)$ and $\{\Delta t_j, \Delta u_j\}_{j \in [1, \eta]}$.

11. Adapt the messages and the outputs of the party $i^*$ as $\|\alpha\|_{i^*} = \alpha - \Delta\alpha - \sum_{i \ne i^*} \|\alpha\|_i \bmod \ell$, $t_{i^*, j} = t_j \Delta t_j / \prod_{i \ne i^*} t_{i,j} \bmod n$ for all $j \in [1, \eta]$, $\|v\|_{i^*} = -\Delta v - \sum_{i \ne i^*} \|v\|_i \bmod \ell$.

12. Call $\tilde{V}$ with the hash digest $h'$ of $\{t_{i,j}, u_{i,j}\}_{j \in [1, N]} \in [1, \eta]$, $\|\alpha\|_i, \|v\|_i$ and gets a challenge $\tilde{j}^*$. If $\tilde{j}^* \ne i^*$, then $S$ restarts the simulation from scratch.

13. Abort with probability $1 - \left(1 - \frac{2^{\gamma-3}}{\Lambda}\right)^2$.

14. Outputs the transcript $(h, \Delta c, h', (\text{seed}_i, \rho_i)_{i \ne i^*}, \text{co-path}_{i^*}, \text{com}_{i^*}, y_1, y_2, \|\alpha\|_{i^*}, t_1, \dots, t_\eta)$.

When no abortion occurs, the output transcript is identically distributed to the genuine transcript except for the commitment of the party $i^*$. Distinguishing them means breaking the commitment hiding property or the PRG security. The above simulator $S$ is a PPT algorithm since the challenge set $[1, N]$ (from which $i^*$ is sampled) has a polynomial size in the security parameter. $\square$

CRediT authorship contribution statement

**Jules Maire:** Formal analysis, Investigation, Methodology, Writing – original draft, Writing – review & editing. **Damien Vergnaud:** Formal analysis, Funding acquisition, Investigation, Methodology, Writing – original draft, Writing – review & editing.
**Declaration of competing interest**

None declared.

**Acknowledgements**

The authors are supported in part by the French ANR SANGRIA project (ANR-21-CE39-0006).

**Data availability**

No data was used for the research described in the article.

**References**

[1] Carlos Aguilar-Melchor, Nicolas Gama, James Howe, Andreas Hülsing, David Joseph, Dongze Yue, The return of the SDitH, in: Carmit Hazay, Martijn Stam (Eds.), Advances in Cryptology – EUROCRYPT 2023, Part V, Lyon, France, April 23–27, 2023, in: Lecture Notes in Computer Science, vol. 14008, Springer, Heidelberg, Germany, 2023, pp. 564–596.

[2] Carsten Baum, Ariel Nof, Concretely-efficient zero-knowledge arguments for arithmetic circuits and their application to lattice-based cryptography, in: Aggelos Kiayias, Markulf Kohlweiss, Petros Wallden, Vassilis Zikas (Eds.), PKC 2020: 23rd International Conference on Theory and Practice of Public Key Cryptography, Part I, Edinburgh, UK, May 4–7, 2020, in: Lecture Notes in Computer Science, vol. 12110, Springer, Heidelberg, Germany, 2020, pp. 495–526.

[3] Lenore Blum, Manuel Blum, Mike Shub, A simple unpredictable pseudo-random number generator, SIAM J. Comput. 15 (2) (1986) 364–383.

[4] Manuel Blum, Coin flipping by telephone - a protocol for solving impossible problems, in: COMPCON'82, Digest of Papers, Twenty-Fourth IEEE Computer Society International Conference, San Francisco, California, USA, February 22–25, 1982, IEEE Computer Society, 1982, pp. 133–137.

[5] Dan Boneh, Matthew K. Franklin, Efficient generation of shared RSA keys, J. ACM 48 (4) (2001) 702–722.

[6] Joan Boyar, Katalin Friedl, Carsten Lund, Practical zero-knowledge proofs: giving hints and using deficiencies, J. Cryptol. 4 (3) (January 1991) 185–206.

[7] Clifford C. Cocks, An identity based encryption scheme based on quadratic residues, in: Bahram Honary (Ed.), Cryptography and Coding, 8th IMA International Conference, Cirencester, UK, December 17–19, 2001, Proceedings, in: Lecture Notes in Computer Science, vol. 2260, Springer, 2001, pp. 360–363.

[8] Thibauld Feneuil, Jules Maire, Matthieu Rivain, Damien Vergnaud, Zero-knowledge protocols for the subset sum problem from MPC-in-the-head with rejection, in: Shweta Agrawal, Dongdai Lin (Eds.), Advances in Cryptology – ASIACRYPT 2022, Part II, Taipei, Taiwan, December 5–9, 2022, in: Lecture Notes in Computer Science, vol. 13792, Springer, Heidelberg, Germany, 2022, pp. 371–402.

[9] Rosario Gennaro, Daniele Micciancio, Tal Rabin, An efficient non-interactive statistical zero-knowledge proof system for quasi-safe prime products, in: Li Gong, Michael K. Reiter (Eds.), ACM CCS 98: 5th Conference on Computer and Communications Security, San Francisco, CA, USA, November 2–5, 1998, ACM Press, 1988, pp. 67–72.

[10] Oded Goldreich, Shafi Goldwasser, Silvio Micali, How to construct random functions, J. ACM 33 (4) (1986) 792–807.

[11] Shafi Goldwasser, Silvio Micali, Probabilistic encryption, J. Comput. Syst. Sci. 28 (2) (1984) 270–299.

[12] Shafi Goldwasser, Silvio Micali, Charles Rackoff, The knowledge complexity of interactive proof systems, SIAM J. Comput. 18 (1) (1989) 186–208.

[13] Shafi Goldwasser, Silvio Micali, Ronald L. Rivest, A digital signature scheme secure against adaptive chosen-message attacks, SIAM J. Comput. 17 (2) (1988) 281–308.

[14] Dennis Hofheinz, Eike Kiltz, The group of signed quadratic residues and applications, in: Shai Halevi (Ed.), Advances in Cryptology – CRYPTO 2009, Santa Barbara, CA, USA, August 16–20, 2009, in: Lecture Notes in Computer Science, vol. 5677, Springer, Heidelberg, Germany, 2009, pp. 637–653.

[15] Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai, Zero-knowledge proofs from secure multiparty computation, SIAM J. Comput. 39 (3) (2009) 1121–1152.

[16] Yehuda Lindell, Ariel Nof, A framework for constructing fast MPC over arithmetic circuits with malicious adversaries and an honest-majority, in: Bhavani M. Thuraisingham, David Evans, Tal Malkin, Dongyan Xu (Eds.), ACM CCS 2017: 24th Conference on Computer and Communications Security, Dallas, TX, USA, October 31–November 2, 2017, ACM Press, 2017, pp. 259–276.

[17] Moses Liskov, R. Silverman, A statistical limited-knowledge proof for secure rsa keys, in: IEEE P1363 Working Group, 1998.

[18] Wei Liu, Jian Weng, Bingsheng Zhang, Kai He, Junjie Huang, Improvements on non-interactive zero-knowledge proof systems related to quadratic residuosity languages, Inf. Sci. 613 (2022) 324–343.

[19] Jules Maire, Damien Vergnaud, Efficient zero-knowledge arguments and digital signatures via sharing conversion in the head, in: Gene Tsudik, Mauro Conti, Kaitai Liang, Georgios Smaragdakis (Eds.), ESORICS 2023: 28th European Symposium on Research in Computer Security, Part I, the Hague, the Netherlands, September 25–29, 2023, in: Lecture Notes in Computer Science, vol. 14344, Springer, Heidelberg, Germany, 2023, pp. 435–454.

[20] Wenbo Mao, Fast Monte-Carlo primality evidence shown in the dark, Technical Report HPL-1999-30R1, HP Laboratories, 1999.

[21] Jeroen van de Graaf, René Peralta, A simple and secure way to show the validity of your public key, in: Carl Pomerance (Ed.), Advances in Cryptology – CRYPTO'87, Santa Barbara, CA, USA, August 16–20, 1988, in: Lecture Notes in Computer Science, vol. 293, Springer, Heidelberg, Germany, 1988, pp. 128–134.