# Showing special soundness for Dilithiums underlying $\Sigma$-protocol

I'm trying to prove the security of Dilithiums underlying $$\Sigma$$-protocol using the following theorem.

Let $$\Sigma=\left(\mathcal{P},\mathcal{V}\right)$$ be a $$\Sigma$$-protocol on an effective relation $$\mathcal{R}$$ and let $$G$$ be the key generation algorithm for $$\mathcal{R}$$. If $$\Sigma$$ provides special soundness and $$G$$ is one-way then the identification protocol $$\mathcal{I}=\left(G,\mathcal{P},\mathcal{V}\right)$$ is secure against direct attacks.

The $$\Sigma$$-protocol can be defined in the following way.

1. $$\mathcal{P}((A,t,s_1,s_2))$$ samples $$y\gets S_{\gamma_1-1}^{\ell}$$ and computes $$w_1 = \text{Highbits}(Ay,2\gamma_2)$$.
2. $$\mathcal{P}$$ sends $$w_1$$ to $$\mathcal{V}$$
3. $$\mathcal{V}$$ picks $$c\in B_{\tau}$$, where $$B_{\tau}$$ is the subset of $$\mathbb{Z}_q[x]/\langle x^{256}+1 \rangle$$ containing polynomials with $$\tau$$ coefficients which has value $$\pm 1$$ and the rest are $$0$$.
4. $$\mathcal{V}$$ sends $$c$$ to $$\mathcal{P}$$.
5. $$\mathcal{P}$$ calculates $$z = y+cs_1$$ such that $$||z||_{\infty}<\gamma_1-\beta$$ and $$||\text{Lowbits}(Ay-cs_2,2\gamma_2)<\gamma_2-\beta$$
6. $$\mathcal{P}$$ sends $$z$$ to $$\mathcal{V}(A,t)$$
7. $$\mathcal{V}$$ verifies that $$||z||_{\infty}<\gamma_1-\beta$$ and that $$\text{Highbits}(Az-ct,2\gamma_2) = w_1$$

I have the following proof-sketch:

Let an adversary, $$\mathcal{A}$$ be given the public key, $$x=\left(A,t\right)$$, and two conversations $$\left(w_1,c,z\right)$$ and $$\left(w_1,c',z'\right)$$ such that $$c\neq c'$$. $$\mathcal{A}$$ can now compute a witness for $$x$$ by doing the following:

Given $$z=y+cs_1$$ and $$z'=y+c's_1$$ we have that:

\begin{align*} z-z'&=cs_1-c's_1\\ &= s_1\left(c-c'\right) \end{align*} Which implies: $$s_1 = \frac{z-z'}{c-c'}$$ This is possible since $$c-c'\neq 0$$

We also have that: $$s_2 = t-As_1$$ The underlying $$\Sigma$$-protocol therefore provides special soundness.

However I'm not sure how to prove that $$(c-c')^{-1}\in \mathbb{Z}_q[x]/\langle x^{256}+1 \rangle$$, which is necessary for this proof.

Any help is much appreciated.

• Why do you want it to have special soundness? Also, does it have special soundness? (It’s been a while since I looked at it, but I seem to remember that they used a different proof strategy for the signature scheme.)
– K.G.
Commented May 8 at 9:32

However I'm not sure how to prove that $$(c−c′)^{-1}\in \mathbb{Z}_q[x] / (x^{256}+1)$$
Essentially, this follows from the choice of the challenge set $$B_\tau$$. See