1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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.) $\endgroup$
    – K.G.
    Commented May 8 at 9:32

1 Answer 1

2
$\begingroup$

I don't believe Dilithium uses special soundness. See for example A Concrete Treatment of Fiat-Shamir Signatures in the Quantum Random-Oracle Model. In Figure 1 (and the surrounding text) they discuss that while special soundness is typically used, it requires the forking lemma, and leads to non-tight QROM proofs. For this reason, an alternative property ("lossiness") is used instead. For applications to (a simplified variant of) Dilithium, see Appendix B.

As to your question

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

$\endgroup$
1
  • $\begingroup$ Hi Mark Thank you for the answer, you're a legend! Currently I'm only interested in showing the security of Dilithium in ROM via the deduction chain: (one-way and special soundness)->(security against direct attacks), (security against direct attacks and HVZK) -> (security against eavesdropping attacks), (security against eavesdropping attacks and unpredictable commitments) -> (Fiat-Shamir signature is EUF-CMA secure) $\endgroup$ Commented May 13 at 9:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.