4.11 Lattice-Based Exact Argument of Knowledge

The role of splitting is different in [LS18] and [BLS19]. In [LS18], the NTT coordinates are used to argue that short nonzero elements cannot vanish in any coordinate, and hence are invertible. In [BLS19], we instead use the fully splitting case to expose the witness coordinates themselves: after the NTT, the ternary condition on $\widehat{𝐬}$ is equivalent to the single ring identity $𝐬(𝐬-\mathrm{𝟏})(𝐬-\mathrm{𝟐})=\mathrm{𝟎}$. The remaining issue is no longer ring splitting, but how to enforce this identity together with $𝐀\widehat{𝐬}=\bar{u}$ inside an exact proof of knowledge. In our case, $R_q={\mathbb{Z}}_q[X]/\left({\mathrm{\Phi }}_{\mathrm{\ell }}\right)$ is a power-of-2 fully splitting cyclotomic ring by $q\equiv 1mod\mathrm{\ell }$, ${\mathrm{\Phi }}_{\mathrm{\ell }}=X^n+1$, and $n=\phi (\mathrm{\ell })$, so $\mathrm{\ell }=2n$.

The starting exact relation is to prove knowledge of a short vector $\widehat{𝐬}\in {\mathbb{Z}}_q^n$ such that

We focus on $\widehat{𝐬}\in {\{0,1,2\}}^n$. For $𝐬\in R_q$ whose NTT representation is $\widehat{𝐬}$, the ternary constraint is equivalent to

and the “shortness” check is turned into an algebraic identity over a fully splitting ring. This is how exact shortness is proved without falling back to a coordinate-wise combinatorial argument.

We start from the Commit-and-Open Sigma-Protocol, which originated from [Lyu12], and was explicitly constructed in [BDL+18b] for the approximate argument of knowledge for the commitment opening.

Since we cannot challenge $𝐀\widehat{𝐬}$ with short invertible ring elements, as $\widehat{𝐬}\in {\mathbb{Z}}_q^n$ is incompatible with the challenge applied through the polynomial product. Going down the path, for the knowledge soundness of the Sigma-Protocol, the challenge has to be from ${\mathbb{Z}}_q$ for a sufficiently large challenge set. Yet, given that the new challenge set is ${\mathbb{Z}}_q$, the norm of $c\cdot \widehat{𝐬}$ can be arbitrary, and the masking message $\bar{r}\in {\mathbb{Z}}_q^n$ has to be uniformly random. Again, this violates the commitment binding in the Commit-and-Open Sigma-Protocol, where $𝐀$ as the Ajtai commitment has to bind $\bar{r}$ to pin down the masking against the random oracle.

Looking closely, in previous approximate arguments of knowledge [BBC+18a, BDL+18b], $𝐀$ simultaneously takes over the role of the statement, and the binding commitment that binds the masking message and the last opening. The dual roles enforce that the masking and opening have to be short, or otherwise Ajtai will not bind.

In [BLS19], the role of binding commitment is lifted from $𝐀$, and moved to a lattice-based commitment scheme that binds arbitrary messages, such that the canonical representations $𝐬$ and $𝐫={\mathrm{𝖭𝖳𝖳}}^{-1}(\bar{r})$ are committed and pinned to the random oracle. In this way, $𝐀$ is treated as more of a linear system of the relation to be proved, rather than a commitment scheme that instantiates a Commit-and-Open Sigma-Protocol. The lifting of the binding role allows the challenge $c$ to be uniformly random over ${\mathbb{Z}}_q$, and the masking $\bar{r}$ for $c\cdot \widehat{𝐬}$ to be uniformly random over ${\mathbb{Z}}_q^n$.

Ajtai commitment [Ajt96] has been great as a compressing commitment, when the message is short. The binding and extractability hold by the SIS hardness assumption. However in our scenario, the NTT representation is short for the message to be committed, but not the canonical form of the message itself. Hence, we need a commitment that lets us manipulate arbitrary ring messages algebraically and homomorphically, while preserving hiding, binding, and extractability.

Now consider a commitment satisfying the requirements above, though it is not compressing like Ajtai commitment. The vanilla BDLOP commitment [BDL+18b] is constructed as follows. For $\beta >0$, write

The public parameter is a pair of matrices:

Equivalently, the commitment map is defined by the vertical stack

On message $\overline{𝐦}\in R_q^{{\mathrm{\ell }}_{\mathrm{𝖢𝗈𝗆}}}$, sample short randomness $\overline{𝐫}\stackrel{\text{r}}{\leftarrow }{S}_{\beta }^k$ and output

Thus the message is added only to the lower coordinates, while both coordinates are still linear functions of the same short randomness $\overline{𝐫}$. The relaxed opening form used in the proof system allows an extracted scalar $𝐟$ from the challenge set:

where the honest opening has $𝐟=\mathrm{𝟏}$ and $\overline{𝐫}$ remains short. This identity-block form is what makes opening proofs compact: the prover can prove knowledge of a short $\overline{𝐫}$ for the top part and recover the message from the lower part.

The hiding reduction is to ${\mathrm{𝖣𝖪𝖲}}_{n+{\mathrm{\ell }}_{\mathrm{𝖢𝗈𝗆}},k,\beta }^{\mathrm{\infty }}$: if $𝐀\overline{𝐫}$ is computationally (or statistically) indistinguishable from uniform, then adding $(\mathrm{𝟎},\overline{𝐦})$ does not reveal $\overline{𝐦}$. The binding reduction is to ${\mathrm{𝖲𝖪𝖲}}_{n,k,\gamma }^2$ for the top block ${𝐀}_1$: two different short relaxed openings give a nonzero vector of the form ${𝐟}^{\prime }\overline{𝐫}-𝐟{\overline{𝐫}}^{\prime }$ with ${𝐀}_1({𝐟}^{\prime }\overline{𝐫}-𝐟{\overline{𝐫}}^{\prime })=\mathrm{𝟎}$.

Now back to the [BLS19]. The challenge set $𝒞$ is defined by

such that $\left|𝒞\right|=\mathrm{\ell }+1=2n+1$. The challenge-difference set is $\overline{𝒞}:=(𝒞-𝒞)\setminus \{\mathrm{𝟎}\}$, and every element in $\overline{𝒞}$ is invertible: Since $R_q$ is fully splitting, then

where $\xi$ is the ${\mathrm{\ell }}^{\mathrm{th}}$ primitive root of unity. Each $X^{\alpha }-X^{\beta }\in \overline{𝒞}$ has $X^{\alpha }-X^{\beta }\equiv {\xi }^{\alpha j}-{\xi }^{\beta j}mod\left(X-{\xi }^j\right)$ for all $j\in {\mathbb{Z}}_{\mathrm{\ell }}^{\ast }$, and ${\xi }^{\alpha j}-{\xi }^{\beta j}$ is zeroed out iff $\alpha \equiv \beta mod\mathrm{\ell }$. Hence, all of the CRT slots are nonzero, and they are invertible. Differences involving $\mathrm{𝟎}$ are of form $\pm X^{\alpha }$, which are units in $R_q$ and are invertible.

Moreover, for every $\overline{𝐟}={𝐟}_1-{𝐟}_2\in \overline{𝒞}$ and $𝐚\in R$, multiplication by $\overline{𝐟}$ increases the coefficient ${\mathrm{\ell }}_2$-norm by at most a factor of $2$:

One thing to note: the ${\mathrm{\ell }}_2$-norm in [BLS19] is the canonical embedding ${\mathrm{\ell }}_2$-norm, while the ${\mathrm{\ell }}_2$-norm is the coefficient ${\mathrm{\ell }}_2$-norm. The canonical embedding ${\mathrm{\ell }}_2$-norm is the ${\mathrm{\ell }}_2$-norm for the eq. 4.1, which was shown in [LS18]. In our $R$ power-of-two cyclotomic ring, we have

where $\omega$ here is the primitive ${\mathrm{\ell }}^{\mathrm{th}}$ complex root of unity, namely $\omega =\exp \left(2\pi i/\mathrm{\ell }\right)$, as was written in eq. 4.2.

In the [BLS19] specialization for [BDL+18b], $\mathrm{𝖱𝖫𝖶𝖤}$ and $\mathrm{𝖱𝖲𝖨𝖲}$ are needed for hiding and binding.

Fix a distribution $\chi$ over $\mathbb{Z}$. We write ${\chi }^n$ for the distribution over $R$, where a sample is obtained by sampling $n$ coefficients independently from $\chi$, and ${\chi }^{kn}$ denotes the corresponding distribution over $R^k$. In the instantiation of [BLS19], the distribution $\chi$ is over $\{-1,0,1\}$, outputting $\pm 1$ with probability $5/16$ each, and $0$ with probability $3/8$.

The BDLOP commitment is specialized to commit to $\overline{𝐦}={({𝐦}_2,{𝐦}_3,{𝐦}_4,{𝐦}_5)}^{𝖳}\in R_q^4$, and the public parameter is a matrix $𝐁\in R_q^{5\times 6}$ of the form

This is the same identity-block idea as vanilla BDLOP, but with one top coordinate and four message coordinates. To commit to $\overline{𝐦}$, sample short randomness $\overline{𝐫}\leftarrow {\chi }^{6n}$ from the error distribution and output

For $\sigma >0$, let ${\rho }_{\sigma }(\overline{𝐮}):=\exp \left(-{\Vert \overline{𝐮}\Vert }_2^2/(2{\sigma }^2)\right)$, and ${\rho }_{\sigma }(S):={\sum }_{\overline{𝐱}\in S}{\rho }_{\sigma }(\overline{𝐱})$. The discrete Gaussian centered at $\overline{𝐯}\in R^k$ is

When $\overline{𝐯}=\overline{\mathrm{𝟎}}$, we write $D_{\sigma }^{kn}$.

The relaxed opening relation from extractor is

where $𝐟$ is either from the challenge-difference set $\overline{𝒞}$, or $𝐟=\mathrm{𝟏}$ for an honest opening. $\overline{𝐫}$ needs to be short, written as ${\Vert \overline{𝐫}\Vert }_2\le 2B$, with $B=\sigma \sqrt{12n}$.

In [BLS19] the hiding is reduced to the ${\mathrm{𝖱𝖫𝖶𝖤}}_5$ hardness, and the binding is reduced to the ${\mathrm{𝖱𝖲𝖨𝖲}}_{5,8B}$ hardness, where $8B$ derives from the ${\mathrm{\ell }}_2$-norm of ${𝐟}_1{\overline{𝐫}}_0-{𝐟}_0{\overline{𝐫}}_1$ in eq. 4.10, recall eq. 4.8 for factor 2 and ${\Vert \overline{𝐫}\Vert }_2\le 2B$.

A short invertible element itself cannot give knowledge with relaxed norm bounds, not even the exact knowledge. Its role is more of, so long as the elements in the challenge-difference $\overline{𝒞}$ are invertible, we can reduce binding to the hardness assumptions like SIS.

After the first definition of binding by definition 4.8.1, we define the property again as follows.

For [BDL+18b], the $(𝐟,\overline{𝐦},\overline{𝐫})$ is a relaxed opening proof. Supposing we have a pair of relaxed openings satisfying

with ${𝐦}_0\ne {𝐦}_1$, then cancelling out $\overline{𝐭}$ term, we have

separating by the vertical stack

It is that ${𝐟}_0\cdot {𝐟}_1$ being invertible, ensuring ${𝐟}_0\cdot {𝐟}_1\cdot \left({\overline{𝐦}}_0-{\overline{𝐦}}_1\right)\ne \overline{\mathrm{𝟎}}$, or otherwise the product with a non-invertible ring element $a$ may be 0. Given that ${𝐟}_1\cdot {\overline{𝐫}}_0-{𝐟}_0\cdot {\overline{𝐫}}_1\ne \overline{\mathrm{𝟎}}$, reducing to the SIS hardness of ${𝐀}_1\left({𝐟}_1\cdot {\overline{𝐫}}_0-{𝐟}_0\cdot {\overline{𝐫}}_1\right)$.

For [Ajt96], recall definition 4.8.4, write $𝐀=\left[{𝐀}_1\mid {𝐀}_2\right]$ as the commitment key, $𝐬={\left[{𝐫}^{𝖳}\mid {𝐦}^{𝖳}\right]}^{𝖳}$ as the message and randomness, and $𝐜\leftarrow \mathrm{𝐀𝐬}={𝐀}_1𝐫+{𝐀}_2𝐦$ as the Ajtai commitment. Deriving from the same Sigma-Protocol in [Lyu12], a relaxed opening proof $(𝐟,\overline{𝐦},\overline{𝐫})$ from extraction must satisfy

where the honest opening has $𝐟=\mathrm{𝟏}$.

If the same commitment is opened with ${𝐬}^{\prime }={\left[{𝐫}^{\prime 𝖳}\mid {𝐦}^{\prime 𝖳}\right]}^{𝖳}$, then for $𝐬={\left[{\overline{𝐫}}^{𝖳}\mid {\overline{𝐦}}^{𝖳}\right]}^{𝖳}$ with $𝐬\cdot {𝐟}^{-1}\ne {𝐬}^{\prime }$, we immediately reduce binding to SIS hardness assumption; or otherwise without invertibility the existence of an SIS solution when $𝐟\cdot {𝐬}^{\prime }-𝐬=\overline{\mathrm{𝟎}}$ is hard to reason (say an entry of $𝐬$ is 0 while the same entry in ${𝐬}^{\prime }$ is non-zero but annihilated). Again, the preservation of non-zeroness by invertible elements helps with the hardness reduction.

To sum up, the short invertible elements in the relaxed opening ensure the binding reduction, but do not directly give knowledge soundness.

For [BLS19], the relation to prove is $𝐀\widehat{𝐬}\equiv \bar{u}modq$, where each entry in $\widehat{𝐬}$ is within $\{0,1,2\}$. In the prior Commit-and-Open Sigma-Protocol attempt based on previous approximate arguments of knowledge, we lifted the role of the binding commitment from $𝐀$. My ill-contrived question is now: if $𝐀$ is not a strong Ajtai instance, can we still have zero knowledge for arbitrary $𝐀$, unlike in previous works such as [BBC+18a, BLN+20, BDL+18b]?

I started by considering an extreme case where $𝐀$ is an identity matrix. Then $\bar{u}=\widehat{𝐬}$, and the random masking $\bar{r}$ is sent in the clear. An honest-but-curious verifier can remove $\bar{r}$ from $\bar{z}$, which is the third move of the Sigma-Protocol proposed by modifying the original opening protocol in [BDL+18b] (ignoring the BDLOP commitment for now), and derive the witness $\widehat{𝐬}$.

On the other hand, such an accepting transcript is totally simulatable! Still ignoring the BDLOP part,

• •

  an accepting transcript contains the first message $𝐀\bar{r}$ of the masking through the $𝐀$ linear system, the second challenge $c$, which is uniformly random over ${\mathbb{Z}}_q$, and the third response $c\cdot \widehat{𝐬}+\bar{r}$;

• •

  a simulated transcript first samples the third response $\bar{z}$ uniformly at random and then samples the challenge $c^{\prime }\stackrel{\text{r}}{\leftarrow }{\mathbb{Z}}_q$; the first masking through $𝐀$ can be simulated by $𝐀\bar{z}-c^{\prime }\cdot \bar{u}$.

Both the second and third messages are uniformly distributed. The first masking $𝐀\bar{r}$ in a real accepting transcript is uniform over $\mathrm{im}(𝐀)$ (uniformly random over the whole codomain if $𝐀$ has full row rank), which is determined by the distribution of $\bar{r}$, while in the simulated transcript, the distribution of $𝐀\bar{z}-c^{\prime }\cdot \bar{u}$ is determined by $c^{\prime }$ and $\bar{z}$, which are both uniformly random, and $\bar{u}\in \mathrm{im}(𝐀)$ as HVZK is defined for a valid statement. Then $𝐀\bar{z}-c^{\prime }\cdot \bar{u}=𝐀\left(\bar{z}-c^{\prime }\cdot {\bar{s}}^{\prime }\right)$, where $𝐀{\bar{s}}^{\prime }\equiv \bar{u}modq$, so the first masking is also simulatable as part of the joint transcript distribution. Generalizing from $𝐀={𝐈}_n$, simulatability holds regardless of $𝐀$.

So what exactly does HVZK really say? Literally, HVZK says that an honestly generated accepting transcript, where the prover holds the witness and the statement is public, is computationally or statistically close to a simulated transcript generated using only the statement. Now let $T_{\mathrm{𝗋𝖾𝖺𝗅}}$ be the honestly generated accepting transcript, $T_{\mathrm{𝗌𝗂𝗆}}$ be the simulated transcript, $𝒜$ be an efficient algorithm attempting to recover the witness from the transcript, and

$R(x,𝒜(x,T))$ can be computed efficiently because membership in the NP relation $R$ can be checked efficiently and $𝒜$ is efficient. If HVZK is computational, then let $R(x,𝒜(x,\cdot ))$ be an efficient distinguisher, hence

If HVZK is statistical, then eq. 4.11 follows from the statistical distance being negligible. Let $ℬ$ be an algorithm that samples $T_{\mathrm{𝗌𝗂𝗆}}$ from the simulator and runs $𝒜(x,T_{\mathrm{𝗌𝗂𝗆}})$. Since the simulator is efficient, $ℬ$ is efficient. Then by eq. 4.11,

or equivalently

In this way, HVZK can be interpreted as, it does not give one more advantage in finding the witness for the statement, with or without an honestly generated accepting transcript. But ZK is irrelevant to $𝐀$ being a hard instance or not. If the problem is easy, then the problem is in P, and there is no witness to hide.

Thus, any efficient witness-recovery advantage obtained from the honest verifier’s view could already be obtained from the public statement alone. If the relation is hard, no such non-negligible advantage can exist, and the witness hiding against an honest verifier follows from HVZK and the hardness of the relation ²¹²¹21This is an honest-verifier analogue of the witness-hiding interpretation introduced by [FS90]. Their formal definition is distributional and applies to potentially malicious verifiers, whereas the present conclusion follows only for the honest verifier from HVZK.. See also [Dam10].

In our particular setting, if $(𝐀,\bar{u})$ is sampled from a hard ISIS instance distribution, then finding $\bar{r}$ from $𝐀\bar{r}$ in the transcript for short ${\widehat{𝐬}}^{\prime }$ is at least as hard as solving the ISIS instance; namely, efficient recovery of the masking value $\bar{r}$ would give an efficient solver for the ISIS relation.

Henceforth, we let the statement $(𝐀,\bar{u})$ be sampled from a hard ISIS instance distribution for witness privacy.

Recall the construction of the first Sigma-Protocol attempt without BDLOP:

• •

  The prover sends out $\bar{w}\leftarrow 𝐀\bar{r}$, where $\bar{r}$ is uniformly random.

• •

  The verifier challenges the prover by sending $c\stackrel{\text{r}}{\leftarrow }{\mathbb{Z}}_q$.

• •

  The prover replies with $c\cdot \widehat{𝐬}+\bar{r}$.

It is definitely flawed, a malicious prover who does not know $𝐬$ can send out the first masking ${\bar{w}}^{\prime }$ at random, and on verifier replies with $c\stackrel{\text{r}}{\leftarrow }{\mathbb{Z}}_q$, find an arbitrary image ${\bar{z}}^{\prime }$ such that $𝐀{\bar{z}}^{\prime }={\bar{w}}^{\prime }+c\cdot \bar{u}$, where $𝐀\widehat{𝐬}\equiv \bar{u}modq$ in statement.

Starting from the approximate argument similar to [BDL+18b, Lyu12]. For HVZK, namely the accepting transcript is simulatable, the first message for the masking randomness should be simulatable in the joint distribution of the transcript, or otherwise supposing the accepting transcript whose first message being raw masking randomness is efficiently simulatable, then such efficient simulator can be used to solve the statement, which is a hard ISIS instance, and it does not make sense. By contradiction, the first message to be sent out should be “hiding”.

On the other hand, one could have just sent over the raw masking randomness to the RO, and let the RO decide which challenge to send back. But due to the goal of reaching ZK, one has to use a (cryptographic) object in between the masking randomness and the RO. Intuitively, one should pin the masking randomness against the RO, such that the challenge is decided and fixed after the RO absorbs the first message, and the represented masking randomness.

Since the RO itself cannot guarantee what value the first message represents, we need the “binding” property, which says it is computationally/statistically hard to find different preimages that lead to the same message. With such property, an efficient knowledge extractor can extract (relaxed) knowledge of the witness from a pair of forked transcripts from the first message, or otherwise a malicious prover can provide “branch-dependent” decompositions, say $z_0=y_0+c_0\cdot s_0$ and $z_1=y_1+c_1\cdot s_1$, so rewinding does not give valid witness. Binding removes the possibility to equivocate, and makes it possible for extraction from rewinding.

With the property of binding and hiding, we introduce the notion of commitment.

In the vanilla approximate arguments such as [BDL+18b, Lyu12], stopping at the third move is sufficient. It has to be either breaking the SIS hardness assumption, with probability at most $\mathrm{𝗇𝖾𝗀𝗅}(\lambda )$, or the malicious prover prepares a forged commitment $\bar{t}$ to the masking randomness, and a forged response short $\bar{z}$, such that the challenge $c$ happens to satisfy $𝐀\bar{z}=\bar{t}+c\cdot \bar{u}$, with probability at most ${\left|𝒞\right|}^{-1}$. That sums up to be the knowledge soundness, and it suffices to stop at the third move as the binding property allows for rewinding for knowledge extraction.

For the current protocol [BLS19], the same argument no longer applies. The masking randomness is not pinned to the RO, even if $𝐀$ stands for an Ajtai commitment, it will not bind for a message with unbounded length. Moreover, on the third response, in the previous protocols [BDL+18b, Lyu12], it suffices to use binding of short messages to stop there, while in [BLS19], the norm is arbitrary, so we will resort to proving the linear relation $\bar{r}+c\cdot \widehat{𝐬}=\widehat{𝐳}$, let alone proving the shortness of $\widehat{𝐬}$.

Quickly recap what we have here, so after the first Sigma-Protocol, we transformed the problem into proving the linear relation $\widehat{𝐳}=c\cdot \widehat{𝐬}+\bar{r}$, where $\widehat{𝐳}$ is in the third move prover response, while $\bar{r}$ is the masking randomness, and $\widehat{𝐬}$ is the witness. Finally, we also need to prove the shortness of $\widehat{𝐬}$ in the statement.

Deriving from the protocol for linear relation in [BDL+18b], we consider an adaptation here in the $\mathrm{𝖱𝖲𝖨𝖲}$ and $\mathrm{𝖱𝖫𝖶𝖤}$ settings to prove the linear relation of the committed elements.

Let $𝐁\in R_q^{k\times (k+1)}$ be a BDLOP commitment public parameter, and $\overline{𝐦}\in R_q^{k-1}$ be the message, then

is the commitment to $\overline{𝐦}$, where $\overline{𝐫}\leftarrow {\chi }^{(k+1)n}$.

Let $f({𝐱}_1,\mathrm{\dots },{𝐱}_{k-1})$ be a linear function of ${\{{𝐱}_i\}}_{i\in [1,k-1]}$ whose total degree is at most 1, ${\overline{𝐛}}_i$ be the $i^{\mathrm{th}}$ row of $𝐁$, and ${\overline{𝐛}}_f=f({\overline{𝐛}}_2,\mathrm{\dots },{\overline{𝐛}}_k)$. Then ${\mathrm{\Pi }}_{\mathrm{𝗅𝗂𝗇}}$ is defined for statement

• •

  The prover samples ${\overline{𝐫}}^{\prime }\leftarrow D_{\sigma }^{(k+1)n}$, and sends over

  $$\overline{𝐰}=\left[\begin{array}{c}{\overline{𝐛}}_1^{𝖳}\\ {\overline{𝐛}}_f^{𝖳}\end{array}\right]{\overline{𝐫}}^{\prime }.$$

• •

  The verifier samples $𝐟\stackrel{\text{r}}{\leftarrow }𝒞$, where $𝒞$ is the short challenge set, and sends over $𝐟$.

• •

  The prover runs reject sampling, and outputs $\overline{𝐳}\leftarrow {\overline{𝐫}}^{\prime }+𝐟\cdot \overline{𝐫}$.

• •

  The verifier checks $\overline{𝐳}$ being short, and the following equality holds

  $$\overline{𝐰}+𝐟\cdot \left[\begin{array}{c}{𝐜}_1\\ f({𝐜}_2,\mathrm{\dots },{𝐜}_k)\end{array}\right]=\left[\begin{array}{c}{\overline{𝐛}}_1^{𝖳}\\ {\overline{𝐛}}_f^{𝖳}\end{array}\right]\overline{𝐳}+𝐟\cdot \left[\begin{array}{c}\mathrm{𝟎}\\ 𝐰\end{array}\right].$$

Moreover, the linear relation scheme ${\mathrm{\Pi }}_{\mathrm{𝗅𝗂𝗇}}$ can be extended to multiple linear functions.

We now piece ${\mathrm{\Pi }}_{\mathrm{𝗅𝗂𝗇}}$ and the first Sigma-Protocol attempt together for the construction of the argument system just to prove the reduced statement $\widehat{𝐳}=\bar{r}+c\cdot \widehat{𝐬}$ without the norm check.

Here we let $\widehat{𝐲}=\mathrm{𝖭𝖳𝖳}(𝐲)$ be the masking randomness, which used to be represented by $\bar{r}$. We use $𝐁\in R_q^{3\times 4}$ for the BDLOP commitment public parameter, such that we commit to $𝐬$ and $𝐲$.

• •

  The prover sends out $\bar{w}\leftarrow 𝐀\widehat{𝐲}$, where $\widehat{𝐲}$ is uniformly random. Moreover, the prover samples $\overline{𝐫}\leftarrow {\chi }^{4n}$, commits

  $$\overline{𝐜}\leftarrow 𝐁\overline{𝐫}+\left[\begin{array}{c}\mathrm{𝟎}\\ 𝐲\\ 𝐬\end{array}\right],$$

  and sends $\overline{𝐜}$ over to the verifier.

• •

  The verifier challenges the prover by sending $c\stackrel{\text{r}}{\leftarrow }{\mathbb{Z}}_q$.

• •

  The prover replies with $𝐳\leftarrow c\cdot 𝐬+𝐲$, and starts ${\mathrm{\Pi }}_{\mathrm{𝗅𝗂𝗇}}$ by:

  • –

    The prover samples ${\overline{𝐲}}^{\prime }\leftarrow D_{\sigma }^{4n}$, let $f(𝐲,𝐬)=c\cdot 𝐬+𝐲$, and sends over

    $${\overline{𝐰}}^{\prime }=\left[\begin{array}{c}{\overline{𝐛}}_1^{𝖳}\\ {\overline{𝐛}}_f^{𝖳}\end{array}\right]{\overline{𝐲}}^{\prime }.$$

  • –

    The verifier samples $𝐟\stackrel{\text{r}}{\leftarrow }𝒞$, where $𝒞$ is the short challenge set, and sends over $𝐟$.

  • –

    The prover runs reject sampling, and outputs ${\overline{𝐳}}^{\prime }\leftarrow {\overline{𝐲}}^{\prime }+𝐟\cdot \overline{𝐫}$.

• •

  The verifier checks that ${\Vert {\overline{𝐳}}^{\prime }\Vert }_2\le B$ and that the following equality holds:

  $${\overline{𝐰}}^{\prime }+𝐟\cdot \left[\begin{array}{c}{𝐜}_1\\ f({𝐜}_2,{𝐜}_3)\end{array}\right]=\left[\begin{array}{c}{\overline{𝐛}}_1^{𝖳}\\ {\overline{𝐛}}_f^{𝖳}\end{array}\right]{\overline{𝐳}}^{\prime }+𝐟\cdot \left[\begin{array}{c}\mathrm{𝟎}\\ 𝐳\end{array}\right],$$

  and $\bar{w}+c\cdot \bar{u}=𝐀\widehat{𝐳}$ holds.

To adapt the previous NTT shortness check in eq. 4.4 for $\widehat{𝐳}$, we have

To prove the degree-3 evaluation over $c$, the trivial way is to use ${\mathrm{\Pi }}_{\mathrm{𝗅𝗂𝗇}}$ to prove the commitments to ${𝐲}^3$, $3(𝐬-1){𝐲}^2$, and $(3{𝐬}^2-6𝐬+2)𝐲$ satisfy the linear relation over coefficients $1,c,c^2$, then the public parameter should be $R_q^{6\times 7}$.

One optimization in [BLS19] is to reuse the commitment to $𝐬$, such that the linear relation to be done is over $1,c$, while $c^2$ should be multiplying 0, and

Either way is fine, but this allows for committing to only 4 elements, and the public parameter is decreased to $R_q^{5\times 6}$.

We now present the final construction, and we use $𝐁\in R_q^{5\times 6}$ for the BDLOP public parameter, such that we commit to $𝐲$, $𝐬$, $𝐲(2𝐬-3)$, and ${𝐲}^2(𝐬-3)$.

• •

  The prover sends out $\bar{w}\leftarrow 𝐀\widehat{𝐲}$, where $\widehat{𝐲}$ is uniformly at random. Moreover, the prover samples $\overline{𝐫}\leftarrow {\chi }^{6n}$, commits

  $$\overline{𝐜}\leftarrow 𝐁\overline{𝐫}+\left[\begin{array}{c}\mathrm{𝟎}\\ 𝐲\\ 𝐬\\ 𝐲(2𝐬-3)\\ {𝐲}^2(𝐬-3)\end{array}\right],$$

  and sends $\overline{𝐜}$ over to the verifier.

• •

  The verifier challenges the prover by sending $c\stackrel{\text{r}}{\leftarrow }{\mathbb{Z}}_q$.

• •

  The prover replies with $𝐳\leftarrow c\cdot 𝐬+𝐲$, and starts ${\mathrm{\Pi }}_{\mathrm{𝗅𝗂𝗇}}$ by:

  • –

    The prover samples ${\overline{𝐲}}^{\prime }\leftarrow D_{\sigma }^{6n}$, let

    	$f_0(𝐲,𝐬,{𝐦}_4,{𝐦}_5)$	$=c\cdot 𝐬+𝐲,$
    	$f_1(𝐲,𝐬,{𝐦}_4,{𝐦}_5)$	$=(𝐳-2c)(𝐳-c)\cdot 𝐬-{𝐦}_4\cdot 𝐳+{𝐦}_5,$

    and sends over

    $${\overline{𝐰}}^{\prime }=\left[\begin{array}{c}{\overline{𝐛}}_1^{𝖳}\\ {\overline{𝐛}}_{f_0}^{𝖳}\\ {\overline{𝐛}}_{f_1}^{𝖳}\end{array}\right]{\overline{𝐲}}^{\prime }.$$

  • –

    The verifier samples $𝐟\stackrel{\text{r}}{\leftarrow }𝒞$, where $𝒞$ is the short challenge set, and sends over $𝐟$.

  • –

    The prover runs reject sampling, and outputs ${\overline{𝐳}}^{\prime }\leftarrow {\overline{𝐲}}^{\prime }+𝐟\cdot \overline{𝐫}$.

• •

  The verifier checks ${\overline{𝐳}}^{\prime }$ being short, the following equality holds

  $${\overline{𝐰}}^{\prime }+𝐟\cdot \left[\begin{array}{c}{𝐜}_1\\ f_0({𝐜}_2,\mathrm{\dots },{𝐜}_5)\\ f_1({𝐜}_2,\mathrm{\dots },{𝐜}_5)\end{array}\right]=\left[\begin{array}{c}{\overline{𝐛}}_1^{𝖳}\\ {\overline{𝐛}}_{f_0}^{𝖳}\\ {\overline{𝐛}}_{f_1}^{𝖳}\end{array}\right]{\overline{𝐳}}^{\prime }+𝐟\cdot \left[\begin{array}{c}\mathrm{𝟎}\\ 𝐳\\ \mathrm{𝟎}\end{array}\right],$$

  and $\bar{w}+c\cdot \bar{u}=𝐀\widehat{𝐳}$ holds.

We let $\epsilon$ be the convincing probability of the prover, so the prover generates an accepting transcript in expected $1/\epsilon$ steps. The knowledge extraction process is similar to that in [BLN+20], where one needs distinct challenges $c_1,c_2,c_3\in {\mathbb{Z}}_q$ because there is a degree-2 polynomial over $c$ in the shortness check, and the last step is an adaptation of the BDLOP proof of a linear relation, for each $c_i$, by [BDL+18b], we need 2 distinct ${𝐟}_{i,1},{𝐟}_{i,2}\in 𝒞$ for a relaxed opening, and therefore in total we need 6 accepting transcripts forked in 3 by 2.

We begin by bounding the expected runtime of the extractor, where the “heavy-row” argument [Dam10] is used in a similar way as [BBC+18a, BLN+20]. If the probability of convincing is $\epsilon$, consider all transcripts indexed by the first challenge $c\in {\mathbb{Z}}_q$ and the second challenge $𝐟\in 𝒞$, in a 0-1 matrix.

Start with the first pair of accepting transcripts decided by $c_1$. A “heavy row” indexed by challenge $c$ is a row with entries being 1 of fraction at least $\epsilon /2$, then by the “heavy-row” argument in [Dam10], the first accepting transcript is on a heavy row with probability at least $1/2$. Conditioned that the first accepting transcript is on a heavy row, the second accepting transcript is obtained with probability at least $\epsilon /2-{\left|𝒞\right|}^{-1}$, as ${𝐟}_{1,1}\ne {𝐟}_{1,2}$. Hence, the expected runtime for the first pair is

The second pair of accepting transcripts is similar: The first of them is obtained with probability at least $\epsilon -1/q$ as $c_2\ne c_1$, then let the heavy row with entries being 1 of fraction at least $\epsilon /2-1/(2q)$, then the first of them lands on a heavy row with probability at least $1/2$, and conditioned that, the second of them is obtained with probability at least $\epsilon /2-1/(2q)-{\left|𝒞\right|}^{-1}$. Hence, the expected runtime for the second pair is

Hence, conditioned on all three pairs being on heavy rows, occurring with probability at least $1/8$, the expected runtime is at most

and we cap the runtime of the extractor at $2T$. By Markov’s inequality, finding 3 pairs of accepting transcripts in $2T$ steps succeeds with probability at least $1/16$ (conditioned that all are on heavy rows, the probability is at least $1/2$ by Markov’s inequality, then $1/16$ is immediate). Restarting after failure thus gives expected runtime at most $32T$ ²²²²22[BLS19] states $16T$, apparently omitting the factor $2$ from the timeout..

For $i\in [1,3]$, let ${𝐟}_i^{\prime }={𝐟}_{i,1}-{𝐟}_{i,2}$, and ${\overline{𝐳}}_i^{\prime \prime }={\overline{𝐳}}_{i,1}^{\prime }-{\overline{𝐳}}_{i,2}^{\prime }$ be the relaxed-opening randomness obtained by taking the difference of the two masked responses. The difference ${𝐟}_i^{\prime }$ is invertible over $R_q$ by $\overline{𝒞}$, as ${𝐟}_{i,1},{𝐟}_{i,2}\in 𝒞$ are distinct. The two transcripts have the same $c_i$, ${𝐳}_i$, and three masking terms. Subtracting their three verification equations cancels the common masking terms and gives a branch-specific pair of linear functions. Namely, let

with the corresponding rows

The subtraction is then written in the same matrix form as the masked BDLOP opening:

Define the extracted messages by

The first row of this equation and these definitions give the relaxed opening

If two outer branches yield different messages, the two relaxed openings break binding and give an ${\mathrm{𝖱𝖲𝖨𝖲}}_{5,8B}$ solution. Otherwise, all three branches open to fixed messages ${𝐲}^{\ast },{𝐬}^{\ast },{𝐦}_4^{\ast },{𝐦}_5^{\ast }$ that are independent of $c_i$.

The second row of the matrix equation then gives

while the third row gives

Substituting eq. 4.12 into the definition of $g_i$ gives

substituting this expression for $g_i$, together with the expression for ${𝐳}_i$ in eq. 4.12, into the third-row equation yields a degree-2 polynomial in $c_i$ whose leading coefficient is

The polynomial vanishes at the three distinct points $c_1,c_2,c_3$. The corresponding Vandermonde matrix is invertible over ${\mathbb{Z}}_q$, hence also over $R_q$, and therefore

Applying the NTT shows that ${\widehat{𝐬}}^{\ast }\in {\{0,1,2\}}^n$.

Finally, subtracting the outer verification equations for two distinct challenges gives

By eq. 4.12, ${\widehat{𝐳}}_1-{\widehat{𝐳}}_2=(c_1-c_2){\widehat{𝐬}}^{\ast }$. Since $c_1-c_2$ is invertible in ${\mathbb{Z}}_q$, we conclude that

Therefore, the extractor outputs an exact witness ${\widehat{𝐬}}^{\ast }\in {\{0,1,2\}}^n$, or it produces an ${\mathrm{𝖱𝖲𝖨𝖲}}_{5,8B}$ solution.

Following [BG93, Dam10], the knowledge error $\kappa$ can be viewed as an upper bound on the acceptance probability that does not yet force extractable knowledge. Informally, it is the best convincing probability that the analysis permits for a prover that does not know a correct witness. If the prover goes beyond this threshold, the extractor can take a witness out of its behavior. This interpretation does not assert that a prover without a witness can actually attain $\kappa$: the bound need not be tight, and a particular prover may do strictly worse.

For comparison, in a flat protocol with a uniform challenge set of size $N$, if any $r$ distinct accepting branches from the same prefix suffice for extraction, then at most $r-1$ branches may remain non-extractable, giving $\kappa =(r-1)/N$. Thus two-branch extraction gives $1/N$, while three-branch extraction gives $2/N$. This is only the flat intuition: the extractor above requires a nested $3$-by-$2$ challenge tree.

For the current protocol, let

When obtaining the third pair of transcripts, excluding the two previously used outer challenges loses at most $2/q$ of the acceptance probability. On a heavy row, the acceptance probability for the second challenge is therefore at least one half of $\epsilon -2/q$. Excluding the previously used second challenge then leaves probability at least

for obtaining the required inner fork. Hence $\epsilon >\kappa$ makes every denominator in the extraction above positive, and the heavy-row argument of [Dam10] finds the nested challenge tree in expected time $\mathrm{𝗉𝗈𝗅𝗒}(\lambda )/(\epsilon -\kappa )$.