### Supporting Protocols

In this section, we specify the supporting protocols that support the signing protocol described in the previous section.

#### Feldman's VSS

Recall that in Step 2 of the key generation protocol, each participant $$P$$ has to perform Feldman's VSS to share his secret $$s$$ to other participants $$P_i$$. The process of Feldman's VSS is described as follow:

1. $$P$$ generate a random degree $$t$$ polynomial $$f(x)=a_0+a_1x+\dots+a_tx^t$$ such that $$a_0=s$$, then broadcast $$A_i=g^{a_i}$$ for $$i \in \{0,1,\dots,t\}$$. Finally $$P$$ secretly send the share $$s_i=f(i)$$ to the $$i$$-th participant $$P_i$$.

2. Each participant $$P_i$$ can verify the correctness of his share $$s_i$$ by checking $$g^{s_i}=\prod_{j=0}^tA_j^{i^j}$$. If the check fails, $$P_i$$ broadcasts a complaint to $$P$$. If $$P$$ receives a complaint he will be disqualified.

#### Zero Knowledge Proofs

Schnorr Protocol:

In Step 3 of the initial key generation process, a participant who broadcasts $$pk_i=g^{sk_i}$$ must prove the knowledge of $$sk_i$$ using Schnorr protocol. Schnorr protocol can be described as follow:

1. The prover chooses $$a \in \mathbb{Z}_p$$ and sends $$\alpha=g^a$$.

2. The verifier sends a challenge $$c \in \mathbb{Z}_p$$.

3. The prover sends $$u=a+c\sigma$$.

4. The verifier checks if $$g^u=\alpha\cdot pk_i^c$$.

Schnorr Protocol for Ring:

In Step 3.3 of the key refresh process, a participant who broadcasts $$h_1,h_2$$ must prove that there is a value $$s$$ such that $$h_2=h_1^s \pmod{N}$$ The protocol can be described as follow:

1. For each $$i=1,\dots,\lambda$$, the prover chooses $$a_1 \in \mathbb{Z_{\phi(N)}}$$ and sends $$A_i=h_1^{a_i} \pmod{N}$$ to the verifier.

2. The verifier sends a challenge $$e_i \in {0,1}$$ for each $$i=1,\dots,\lambda$$.

3. For each $$i=1,\dots,\lambda$$, the prover sends $$z_i=a_i+e_i s \pmod{\phi(N)}$$ and send $$z_i$$ to the verifier.

4. The verifier checks if $$h_1^{z_i}=A_i\cdot h_2^c \pmod{N}$$ for each $$i=1,\dots,\lambda$$.

Proof of Product of Two Primes:

In Step 3.2 of the key refresh process, a participant must prove that the RSA modulus $$N$$ is a product of two primes $$p,q$$ such that $$N=pq$$ and $$p \equiv q \equiv 3 \pmod{4}$$ and $$gcd(N,\phi(N))=1$$. The protocol process as follow:

1. The prover samples $$w \in \mathbb{Z_N}$$ s.t $$\left(\dfrac{w}{N}\right)=-1$$ where $$\left(\dfrac{w}{N}\right)$$ denotes the Jacobian symbol.

2. The verifier samples $$y_1,\dots,y_{\lambda} \in \mathbb{Z_N}$$ and send them to the prover.

3. The prover proceed as follows:

• Set $$x_i=(y_i')^{1/4} \pmod{N}$$ where $$y_i'=(-1)^{a_i}w^{b_i}y_i$$ such that $$x_i$$ is well defined.

• Compute $$z_i=y_i^{-N} \pmod{N}$$

• Send $$(x_i,a_i,b_i,z_i)_{i=1}^\lambda$$ to verifier.

4. The verifier checks that $$N$$ is not a prime, $$z_i^N \equiv y_i \pmod{N}$$ and $$x_i^4 \equiv (-1)^{a_i}w^{b_i}y_i \pmod{N}$$. Accept if and only if all checks pass.

Pallier Encryption Range Proof:

In Step 1.2 of the signing process, each participant given $$K_i=\mathsf{Enc_i}(k_i)$$ has to provide a proof $$\pi$$ certifying $$k_i<2^{3\lambda}$$. The protocol for providing $$\pi$$ proceeds as follow:

1. The protocol chooses $$N,h_1,h_2$$ to be the auxiliary set-up parameter for the protocol, where $$N$$ is a product of two safe prime and $$h_1,h_2$$ generate the same multiplicative group modulo $$N$$.

2. The prover samples $$\alpha \in [-2^{3\lambda},\dots,2^{3\lambda}]$$, $$\delta \in [-2^{3\lambda}\cdot N,\dots,2^{3\lambda}\cdot N]$$, $$u \in [-2^{\lambda}\cdot N,\dots,2^{\lambda}\cdot N]$$, $$r \in \mathbb{Z_{N_1}}$$

3. The prover computes $$S=h_1^k h_2^u \pmod{N}$$, $$A=(1+N_1)^\alpha r^{N_1} \pmod {N_1^2}$$ and $$C=h_1^\alpha h_2^\delta \pmod{N}$$

4. The prover sends $$(S,A,C)$$ to the verifier.

5. The verifier chooses a challenge $$e \in [-p,\dots,p]$$ and sends $$e$$ to the prover.

6. The prover computes $$z_1=\alpha+ek$$, $$z_2=r\rho^e \pmod{N_1}$$ and $$z_3=\delta+eu$$

7. The prover sends $$\pi=(z_1,z_2,z_3)$$ to the verifier

8. The verifier checks if $$(1+N_1)^{z_1}z_2^{N_1}=AK^e \pmod{N_1^2}$$ and $$h_1^{z_1}h_2^{z_3}=CS^e \pmod{N}$$

9 The verifier checks that $$z_i \in [-2^{3\lambda},\dots,2^{3\lambda}]$$

Proof of Paillier Encryption given Group Commitment:

In Step 2.4 of the signing process, each participant has public input $$(C,X)$$ and secret input $$x$$ and has to provide a proof $$\pi$$ which proves that $$((C,X),x) \in \mathcal{R}$$, where

$$\mathcal{R}=\{((C,X),(x,\rho))\ |\ X=g^{x}\ \land\ C=\mathsf{Enc_1}(x,\rho)\ \land\ x \le 2^{3\lambda}\}$$. The protocol for providing $$\pi$$ proceeds as follow:

1. The protocol chooses $$N,h_1,h_2$$ to be the auxiliary set-up parameter for the protocol, where $$N$$ is a product of two safe prime and $$h_1,h_2$$ generate the same multiplicative group modulo $$N$$.

2. The prover samples $$\alpha \in [-2^{3\lambda},\dots,2^{3\lambda}]$$, $$\delta \in [-2^{3\lambda}\cdot N,\dots,2^{3\lambda}\cdot N]$$, $$u \in [-2^{\lambda}\cdot N,\dots,2^{\lambda}\cdot N]$$, $$r \in \mathbb{Z_{N_1}}$$

3. The prover computes $$S=h_1^xh_2^u \pmod{N}$$, $$A=(1+N_1)^\alpha r^N_1 \pmod{N_1^2}$$, $$Y=g^\alpha$$, $$D=h_1^\alpha h_2^\gamma \pmod{N}$$

4. The prover sends $$S,A,Y,D,F$$ to the verifier.

5. The verifier chooses a challenge $$e \in [-p,\dots,p]$$ and sends $$e$$ to the prover.

6. The prover computes $$z_1=\alpha+ek$$, $$z_2=r\rho^e \pmod{N_1}$$ and $$z_3=\gamma+eu$$

7. The prover sends $$\pi=(z_1,z_2,z_3)$$ to the verifier.

8. The verifier checks that $$(1+N_1)^{z_1}z_2^{N_1}=AC^e \pmod{N_1^2}$$, $$g^{z_1}=YX^e$$ and $$h_1^{z_1}h_2^{z_3}=DS^e \pmod{N}$$

9. The verifier check that $$z_1 \in [-2^{3\lambda},\dots,2^{3\lambda}]$$

Proof of Paillier Operation given Group Commitment:

In Step 2.5 and 2.6 of the signing process, each participant has public input $$(C,X,K,Y)$$ and secret input $$(x,y)$$ and has to provide a proof $$\pi$$ which proves that $$((C,X,K,Y),(x,y)) \in \mathcal{R}$$, where

$$\mathcal{R}=\{((C,X,K,Y),(x,y,\rho,\rho_y))\ |\ C=x\cdot K-\mathsf{Enc_1}(y,\rho)\ \land\ X=g^{x}\ \land\ Y=\mathsf{Enc_2}(y,\rho_y)\ \land\ x<2^{3\lambda}\ \land \ y \le 2^{7\lambda}\}$$ The protocol for providing $$\pi$$ proceeds as follow:

1. The protocol chooses $$N,h_1,h_2$$ to be the auxiliary set-up parameter for the protocol, where $$N$$ is a product of two safe prime and $$h_1,h_2$$ generate the same multiplicative group modulo $$N$$.

2. The prover samples $$\alpha\in [-2^{3\lambda},\dots,2^{3\lambda}]$$, $$\beta\in [-2^{7\lambda},\dots,2^{7\lambda}]$$, $$\gamma, \delta \in [-2^{3\lambda}\cdot N,\dots,2^{3\lambda}\cdot N]$$, $$m, u \in [-2^{\lambda}\cdot N,\dots,2^{\lambda}\cdot N]$$, $$r \in \mathbb{Z_{N_1}}$$ and $$r_y \in \mathbb{Z_{N_2}}$$

3. The prover computes $$A=K^\alpha((1+N_1)^\beta r^{N_1}) \pmod {N_1^2}$$, $$B_x=g^\alpha$$, $$B_y=(1+N_2)^\beta r_y$$, $$E=h_1^\alpha h_2^\gamma \pmod{N}$$, $$F=h_1^\beta h_2^\gamma \pmod{N}$$, $$S=h_1^xh_2^m \pmod{N}$$, $$T=h_1^yh_2^u \pmod{N}$$

4. The prover sends $$S,T,A,B_x,B_y,E,F$$ to the verifier.

5. The verifier chooses a challenge $$e \in [-p,\dots,p]$$ and sends $$e$$ to the prover.

6. The prover compute $$z_1=\alpha+ex$$, $$z_2=\beta+ey$$, $$z_3=\gamma+em$$, $$z_4=\delta+eu$$, $$w=r \rho^e \pmod{N_1}$$, $$w_y=r \rho_y^e \pmod{N_2}$$

7. The prover sends $$\pi=(z_1,z_2,z_3,z_4,w,w_y)$$ to the verifier.

8. The verifier checks that $$K^{z_1}(1+N_1)^{z_2}w^{N_1} = A C^e \pmod{N}$$, $$g^{z_1}=B_xX^e$$, $$(1+N_2)^{z_2}w_y^{N_2}=B_yY^e \pmod{N_2}$$, $$h_1^{z_1}h_2^{z_3}=ES^e \pmod{N}$$, $$h_1^{z_2}h_2^{z_4}=FT^e \pmod{N}$$

9. The verifier check that $$z_1 \in [-2^{3\lambda},\dots,2^{3\lambda}]$$ and $$z_1 \in [-2^{7\lambda},\dots,2^{7\lambda}]$$

#### Commitment Scheme

In Step 1 of the Key Generation protocol, we require participants to commit their messages using a commitment scheme $$\mathsf{Com}$$. In practice, one can use a cryptographic hash function $$\mathsf{H}$$ and define the commitment of $$X$$ to be $$\mathsf{H}(X,r)$$ where $$r$$ is chosen uniformly.