4.12 Practical Product Proof from Lattice Commitments

One contribution of [ALS20], building on [LS18], is the observation that polynomial ring elements cannot split into many factors for a short invertible challenge set. More specifically, consider the particular setting of a power-of-two ring from theorem 4.10.1 and theorem 4.10.6.

Then theorem 4.10.1 can be updated as follows.

We also update theorem 4.10.6 as follows.

For pairwise difference of distinct challenges being invertible (to reduce binding to the openings to SIS hardness), we need $q^{1/\mathrm{\ell }}\cdot {\mathrm{\ell }}^{-1/2}>2$, and eventually $q>{\left(2\sqrt{\mathrm{\ell }}\right)}^{\mathrm{\ell }}$. The following table shows that the polynomial ring cannot split into many irreducible factors without making the modulus too large for computational efficiency.

This gives rise to the question behind [ALS20]: what if the challenge set is not globally invertible, but the probability that a pairwise difference is noninvertible is low, such as $\mathrm{𝗉𝗈𝗅𝗒}(q^{-1})$? The goal is a good challenge set even when the ring splits into a large number of irreducible factors.

To describe the splitting in corollary 4.12.2 better, we point out that $R_q$ has a group of automorphisms $\mathrm{𝖠𝗎𝗍}(R_q)$ that is isomorphic to ${\mathbb{Z}}_{2d}^{\ast }$. We write $\mathrm{𝖠𝗎𝗍}(R_q)$ for the cyclotomic automorphism subgroup consisting of the maps $f(X)\mapsto f(X^i)$ for $i\in {\mathbb{Z}}_{2d}^{\ast }$. This group is isomorphic to ${\mathbb{Z}}_{2d}^{\ast }$:

where

The group $\mathrm{𝖠𝗎𝗍}(R_q)$ acts transitively on prime ideals $(X^{d/\mathrm{\ell }}-\xi )$ in $R_q$, and every ${\sigma }_i$ factors through field isomorphisms

Concretely, by automorphism, we have

in $R_q$, then for $𝐟\in R_q$,

The multiplicative subgroup $⟨2\mathrm{\ell }+1⟩\subseteq {\mathbb{Z}}_{2d}^{\ast }$ has order $d/\mathrm{\ell }$ by corollary 4.12.2, and any $i\in ⟨2\mathrm{\ell }+1⟩$ stabilizes the prime ideal $\left(X^{d/\mathrm{\ell }}-\xi \right)$, namely

as $\xi$ is a primitive $2{\mathrm{\ell }}^{\mathrm{th}}$ root of unity, then $i\in ⟨2\mathrm{\ell }+1⟩\subset {\mathbb{Z}}_{2d}^{\ast }$ has ${\xi }^{i^{-1}}=\xi$. The quotient group ${\mathbb{Z}}_{2d}^{\ast }/⟨2\mathrm{\ell }+1⟩\cong {\mathbb{Z}}_{2\mathrm{\ell }}^{\ast }$ has order $\mathrm{\ell }$, and since elements in $⟨2\mathrm{\ell }+1⟩$ stabilize the prime ideal, we can index the $\mathrm{\ell }$ prime ideals by

Moreover, for $k\mid \mathrm{\ell }$ with , $⟨2\mathrm{\ell }/k+1⟩\subset {\mathbb{Z}}_{2d}^{\ast }$ has order $kd/\mathrm{\ell }$, and thus $⟨2\mathrm{\ell }/k+1⟩/⟨2\mathrm{\ell }+1⟩$ has order $k$. Then

and therefore

Another way of showing it is, let $\sigma ={\sigma }_{2\mathrm{\ell }/k+1}$, since ${\{{\left(2\mathrm{\ell }/k+1\right)}^{i}mod2d\}}_{i\in [0,k-1]}$ gives $⟨2\mathrm{\ell }/k+1⟩/⟨2\mathrm{\ell }+1⟩$, then

By ${\mathbb{Z}}_{2d}^{\ast }/⟨2\mathrm{\ell }/k+1⟩\cong {\mathbb{Z}}_{2\mathrm{\ell }/k}^{\ast }$, then

where the prime ideals are indexed by ${\mathbb{Z}}_{2\mathrm{\ell }/k}^{\ast }\times [0,k-1]$.

Consider the distribution for the coefficients in $R_q={\mathbb{Z}}_q[X]/(X^d+1)$, where each coefficient is over $\{-1,0,1\}$, $0$ has probability $p$, and $\pm 1$ has probability $(1-p)/2$ each. Such distribution $𝒞$ is the distribution for the challenge set.

Let $\alpha =d/\mathrm{\ell }$. We reorder the coefficients of $𝐜\leftarrow 𝒞$ as follows:

Hence, the $d/\mathrm{\ell }$ coefficients of $𝐜mod\left(X^{\alpha }-\xi \right)$ are i.i.d., which can be shown as

where each row, namely each coefficient of $𝐜mod\left(X^{\alpha }-\xi \right)$, is represented by the random variable

and the $X_i$ are i.i.d. according to the $\{-1,0,1\}$ distribution. We now present the lemma for the distribution of $Y$.

By taking advantage of symmetry, we can reduce the number of terms needed to compute the probability upper bound by a factor of $2\mathrm{\ell }$.

Each row can be represented in Horner’s polynomial evaluation form

which can be transformed into a Markov chain: $Z_0=0$, $Z_{i+1}=\xi Z_i+X_i$ where $X_i$ follows the $\{-1,0,1\}$ distribution.

We recall the assumptions underlying the binding and hiding properties of the commitment scheme in [ALS20].

Fix a coefficient distribution $\chi$ over $\mathbb{Z}$. As before, ${\chi }^{kd}$ denotes independent sampling of all coefficients in $R^k$.

Following [ALS20], we omit $m$ and write ${\mathrm{𝖬𝖲𝖨𝖲}}_{n,B}$ and ${\mathrm{𝖬𝖫𝖶𝖤}}_{n,\chi }$. The BDLOP commitment matrix follows, where $\mu$ and $\lambda$ denote the module ranks for MSIS and MLWE, respectively.

For $L$ committed ring elements, put $N=\mu +\lambda +L$. The block structure used in [BLS19] generalizes to

where $𝐔\stackrel{\text{r}}{\leftarrow }{R}_q^{\mu \times L}$, $𝐕\stackrel{\text{r}}{\leftarrow }{R}_q^{\mu \times \lambda }$, and $𝐖\stackrel{\text{r}}{\leftarrow }{R}_q^{L\times \lambda }$. The instance in [BLS19] has $\mu =\lambda =1$ and $L=4$, and for the instance in [ALS20], the binding and hiding relies on ${\mathrm{𝖬𝖲𝖨𝖲}}_{\mu ,8\kappa \beta }$ and ${\mathrm{𝖬𝖫𝖶𝖤}}_{\lambda ,\chi }$.

In [ALS20], the public matrix is sampled uniformly with the same dimensions by $𝐁\stackrel{\text{r}}{\leftarrow }{R}_q^{(\mu +L)\times N}$ (for readability). For the hiding property, supposing the first $\mu +L$ columns form an invertible $𝐂\in R_q^{(\mu +L)\times (\mu +L)}$, such that

then multiplying $𝐄$ with $\overline{𝐫}\leftarrow {\chi }^{Nd}$ yields a MLWE sample $\overline{𝐠}$, and $\overline{𝐠}$ multiplying with invertible $𝐂$ makes the result computationally indistinguishable to a uniform sample, so as to mask the message $\overline{𝐦}$. The formal argument is the knapsack-MLWE duality, see [EZS+19, Appendix C]. The binding is still reduced to ${\mathrm{𝖬𝖲𝖨𝖲}}_{\mu ,8\kappa \beta }$ in the same reduction.

Another way of seeing is

where $𝐑$ is uniform over invertible $R_q^{(\mu +L)\times (\mu +L)}$, then hiding and binding are still reduced to ${\mathrm{𝖬𝖫𝖶𝖤}}_{\lambda ,\chi }$ and ${\mathrm{𝖬𝖲𝖨𝖲}}_{\mu ,8\kappa \beta }$.

To commit to $\overline{𝐦}={({𝐦}_1,\mathrm{\dots },{𝐦}_L)}^{𝖳}\in R_q^L$, sample $\overline{𝐫}\leftarrow {\chi }^{Nd}$ and output

An immediate application of the result on the NTT slot coefficient distribution is a distribution over $𝒞$ under which the coefficients are sampled i.i.d. over $\{0,1\}$. ²³²³23 A bit flawed construction, elaborate later. Hence, a difference of independently sampled distinct elements is non-invertible with probability at most $\mathrm{\ell }{p}^{d/\mathrm{\ell }}$ by union bound.

It is helpful to start from the BDLOP construction, as [ALS20] improves on [BDL+18b] with a challenge set without the property of globally invertible pairwise differences. Regarding the commitment

in the proof of opening, the prover commits to a short masking vector $\overline{𝐲}$ from a discrete Gaussian distribution, sends $\overline{𝐰}={𝐁}_0\overline{𝐲}$, the verifier challenges with $𝐜\leftarrow 𝒞$, the prover replies with $\overline{𝐳}=\overline{𝐲}+𝐜\cdot \overline{𝐫}$, and rejection sampling is used to make $\overline{𝐳}$ statistically close to a discrete Gaussian sample centered at $\mathrm{𝟎}$. The verifier checks ${\Vert \overline{𝐳}\Vert }_2\le \beta$ and ${𝐁}_0\overline{𝐳}=\overline{𝐰}+𝐜\cdot {\overline{𝐭}}_0$.

If $𝒞$ has this property, the best [BDL+18b] can extract from the proof of opening is the relaxed opening eq. 4.6.

• •

  On one hand, one cannot guarantee that ${𝐟}^{-1}\cdot \overline{𝐫}$ is short after cancelling out $𝐟$ from $\overline{𝐫}$, which can be arbitrarily long.

• •

  On the other hand, the binding property should prevent a single commitment from admitting relaxed openings to distinct messages; otherwise, the opening proof would be meaningless.

  The binding reduction to the SIS is achieved by the pairwise difference being invertible, see eq. 4.10.

Hence, the best [BDL+18b] can do is the relaxed opening, and uniquely interpolating ${\overline{𝐫}}^{\ast }$ and ${\overline{𝐲}}^{\ast }$ out of a pair of forked accepting transcripts. But the scheme cannot guarantee the shortness of ${\overline{𝐫}}^{\ast }$ and ${\overline{𝐲}}^{\ast }$.

In [ALS20], the challenge set is not pairwise difference invertible, so an extractor can obtain a “relaxed opening” from a pair of forked accepting transcripts, but binding is not immediately reducible to SIS, and we cannot uniquely interpolate the prover’s replies $\overline{𝐳}$ and ${\overline{𝐳}}^{\prime }$ to obtain ${\overline{𝐲}}^{\ast }$ and ${\overline{𝐫}}^{\ast }$, from only a pair of forked accepting transcripts

But we can restore the interpolation for ${\overline{𝐲}}^{\ast }$ and ${\overline{𝐫}}^{\ast }$, by piecing together local interpolations over each prime ideal splitting $R_q$. More specifically, though $\mathrm{\Delta }𝐜=𝐜-{𝐜}^{\prime }$ is not invertible, not all of the CRT slots are zeroed out. Suppose that

where ${\phi }_1,\mathrm{\dots },{\phi }_{\mathrm{\ell }}$ are irreducible polynomial factors, and supposing $\mathrm{\Delta }𝐜\not\equiv 0mod{\phi }_i$, then interpolation over the $i^{\mathrm{th}}$ CRT slot gives

and by piecing together the interpolated ${\overline{𝐫}}_i^{\ast }$ and ${\overline{𝐲}}_i^{\ast }$ over each CRT slot $i\in [1,\mathrm{\ell }]$, we have a pair $({\overline{𝐫}}^{\ast },{\overline{𝐲}}^{\ast })$.

Moreover, we will show in the following, for this pair of global interpolations $({\overline{𝐲}}^{\ast },{\overline{𝐫}}^{\ast })$ pieced out CRT slot-wise, on every accepting transcript prefixed by $\overline{𝐰}$, the prover must reply in the degree-1 affine form in eq. 4.20.

Lemma 4.12.9 is helpful, as it explains that the prover has to reply in the degree-1 form w.r.t. the challenge, and it gives rise to the following augmentation of the relaxed opening, allowing for binding reduction to SIS even if we don’t rely on the pairwise difference invertibility property.

The key point is to supply $\mathrm{\ell }$ pairwise differences of challenges, such that each CRT slot is nonzero, and eventually this allows for binding reduction to SIS, which shows as follows.

Looking back, we can reverse engineer the motivation from [BDL+18b] as follows. Starting from a challenge set that is not globally pairwise difference invertible, then to obtain an augmentation of the relaxed opening, we should collect $\mathrm{\ell }$ pairs of forked accepting transcripts starting from $\overline{𝐰}$ the commitment to the masking vector, such that each CRT slot is once nonzero, and we piece out a global interpolation over $R_q$ by local interpolations over $R_q/({\phi }_i)$. What is different from [BDL+18b] in [ALS20] is that we need to interpolate many times, while in [BDL+18b] one interpolation is sufficient, as $𝒞$ in [BDL+18b] is globally pairwise difference invertible. To ensure that the linearity of the prover reply $𝐳$ against the short challenge set elements is still preserved, the lemma 4.12.9 shows that the affine form is respected for all accepting transcripts beginning with $\overline{𝐰}$ for the commitment. A good trick in lemma 4.12.9 is, on a reply that does not have the affine form, move all the eccentric parts down to the degree 0 constant ${\overline{𝐲}}^{{\ast }^{\prime }}$, breaking SIS.

With lemma 4.12.9, the form of definition 4.12.10 makes sense, as lemma 4.12.9 rules out the non-linearity in each “relaxed opening” in the weak opening, so ${\overline{𝐲}}^{\ast }$ is always cancelled out. Finally, the lemma 4.12.11 concludes that the weak opening binds against the commitment by SIS hardness.

All of this effort is necessary because $𝒞$ is not pairwise difference invertible, so extraction cannot be done by one pair of forked accepting transcripts, but rather interpolations over multiple pairs. The weak opening enables binding reduction to SIS by providing $\mathrm{\Delta }{𝐜}_i$ whose $i^{\mathrm{th}}$ CRT slot is non-zero, and lemma 4.12.9 rules out all other forms of extracted openings by showing the uniqueness of the line.

The analysis in [ALS20] has some interesting reasoning for a larger challenge set: Suppose the challenge set $𝒞$ is globally pairwise difference invertible, and $R_q$ is full splitting. Fix a CRT slot, there are $q$ distinct values on that CRT slot, and for the challenge set $𝒞$, by the pigeonhole principle, there are at most $q$ challenges in $𝒞$, or otherwise there exists collision on the CRT slot, then the pairwise difference is not always invertible. Hence, the soundness is at best $1/q$. Even when $R_q$ splits into a few low-degree factors, we cannot quantify the exact size of such globally pairwise difference invertible $𝒞$.

Now I should explain why footnote 23 does not work out of the box. Indeed, if $𝐜,{𝐜}^{\prime }\stackrel{\text{r}}{\leftarrow }{\{0,1\}}^d$, then the coefficients of $𝐜-{𝐜}^{\prime }$ are i.i.d. with $P(\pm 1)=1/4$ and $P(0)=1/2$. Yet it does not mean the anti-concentration bound $p$ in eq. 4.18 can be immediately applied here, whose coefficient $0$ probability is $1/2$, such that the knowledge soundness is $p^{d/\mathrm{\ell }}$. Looking closely, let $X,X^{\prime }$ be the random variables for the $j^{\mathrm{th}}$ coefficient in the $i^{\mathrm{th}}$ CRT slot of $𝐜,{𝐜}^{\prime }$, then

The last equality holds from eq. 4.18, where the inequality is equality when $x=0$ for the distribution of $X-X^{\prime }$. Hence

and hence the knowledge soundness induced by the challenge set over ${\{0,1\}}^d$ is no longer $p^{d/\mathrm{\ell }}$ but rather $p^{d/(2\mathrm{\ell })}$, as the maximum point probability of a coefficient in the $i^{\mathrm{th}}$ CRT slot of $𝐜$ is at most the square root of the anti-concentration bound formed for the $\{-1,0,1\}$ symmetric distribution.

Now we construct a BDLOP in the ring automorphism settings. By changing the challenge set distribution, say [LS18], to the distribution defined previously over ${\{-1,0,1\}}^d$, where distribution for each coefficient is i.i.d., $P(\pm 1)=1/4$ and $P(0)=1/2$, then let $p$ be the maximum probability in eq. 4.18, then the knowledge soundness should be $p^{d/\mathrm{\ell }}$. More specifically, if the prover convinces the verifier with probability $\epsilon >p^{d/\mathrm{\ell }}$, we obtain the first accepting transcript on challenge $𝐜$ in expected $1/\epsilon$ time, then for another challenge ${𝐜}^{\prime }$,

the convincing probability on ${𝐜}^{\prime }\not\equiv 𝐜mod{\phi }_i$ is at least $\epsilon -p^{d/\mathrm{\ell }}$, and the extractor runs in expected polynomial time if $\epsilon -p^{d/\mathrm{\ell }}$ is ${\mathrm{𝗉𝗈𝗅𝗒}}^{-1}(\lambda )$.

If $p^{d/\mathrm{\ell }}$ is not negligible, we can run $k$ copies of the protocol in parallel, and reduce the soundness down to $p^{kd/\mathrm{\ell }}$. To achieve this in a 3-move Sigma protocol, they challenge with $𝐜$ and its automorphisms. I suppose the observation stems from: for a $𝐜$ sampled over ${\{-1,0,1\}}^d$, a coefficient in a coarse ideal $X^{kd/\mathrm{\ell }}-{\xi }^{jk}$ takes on a value with probability at most $p$ by eq. 4.18 ²⁴²⁴24 Here the $p$ is not defined for $X^{d/\mathrm{\ell }}-{\xi }^j$ but for $X^{kd/\mathrm{\ell }}-{\xi }^{kj}$. . Recall that $\sigma ={\sigma }_{2\mathrm{\ell }/k+1}$ stabilizes the ideal $(X^{kd/\mathrm{\ell }}-{\xi }^{jk})$, such that

by eqs. 4.15 and 4.16, such that if $𝐜-{𝐜}^{\prime }\not\equiv 0mod(X^{kd/\mathrm{\ell }}-{\xi }^{jk})$, then any of ${\sigma }^i(𝐜-{𝐜}^{\prime })\not\equiv 0mod(X^{kd/\mathrm{\ell }}-{\xi }^{jk})$, and any of the CRT slot under the coarse CRT factor is at least once non-zero in the $k$ automorphisms.

The construction is then immediate. Sample $k$ random masking elements and commit to them, then the verifier replies with the challenge $𝐜$, and the prover replies with ${\overline{𝐳}}_i={\overline{𝐲}}_i+{\sigma }^i(𝐜)\cdot \overline{𝐫}$ under rejection sampling. If the prover runs in unit time and convinces the verifier with probability $\epsilon >p^{kd/\mathrm{\ell }}$, then the extraction takes

expected time, as sampling

• •

  The first accepting transcript with challenge $𝐜$ takes expected $1/\epsilon$ time.

• •

  An accepting transcript with challenge ${𝐜}_j$ with $𝐜-{𝐜}_j\not\equiv 0mod(X^{kd/\mathrm{\ell }}-{\xi }^{jk})$ takes expected ${(\epsilon -p^{kd/\mathrm{\ell }})}^{-1}$ time.