4 Various Papers 4.7 Bulletproof 4.9 A Non-PCP Approach to Succinct Quantum-Safe ZK

4.8 Sublinear Lattice ZKP for Arithmetic Circuits

The work [BBC+18a] achieves sublinear communication complexity in the lattice based ZK argument system for linear relations. More specifically, they can prove knowledge of short pre-images $\{\mathbf{s}_{i}\}_{i\in[1,\ell]}$ over $\mathbb{Z}_{q}^{v}$ for a linear relation

\mathbf{A}\mathbf{S}\equiv\mathbf{T}\mod q,

where $A\in\mathbb{Z}_{q}^{r\times v}$ and $\mathbf{T}\in\mathbb{Z}_{q}^{r\times\ell}$ are public, and $\mathbf{S}=\left[\mathbf{s}_{1}\mid\ldots\mid\mathbf{s}_{\ell}\right]$ . The trick is to use a challenge matrix $\mathbf{C}\stackrel{{\scriptstyle\textsc{r}}}{{\leftarrow}}\{0,1\}^{\ell\times% (\lambda+2)}$ , such that $\mathbf{S}\mathbf{C}$ is still full of short coefficients, but the number of relations shrink from $\ell$ to $\lambda+2$ . Applying the same technique in [Lyu09, Lyu12], we achieve zero knowledge.

Ring notation and norms.

Let $d=d(\lambda)$ be a power of two, and let $R=\mathbb{Z}[X]/(X^{d}+1)$ , $R_{q}=R/qR$ , and $R_{p}=R/pR$ . For $f\in R_{q}$ , we always take the centered coefficient representative before measuring its size. If this representative is $f=\sum_{i=0}^{d-1}f_{i}X^{i}$ , then $f_{i}$ denotes the coefficient of $X^{i}$ . Define

\left\|f\right\|_{\infty}=\max_{i\in[0,d-1]}\left|f_{i}\right|,\qquad\left\|f% \right\|_{2}=\left(\sum_{i=0}^{d-1}f_{i}^{2}\right)^{1/2}.

For $\mathbf{z}=(z_{1},\ldots,z_{m})\in R^{m}$ , define

\left\|\mathbf{z}\right\|_{\infty}=\max_{j\in[m]}\left\|z_{j}\right\|_{\infty}% ,\qquad\left\|\mathbf{z}\right\|_{2}=\left(\sum_{j=1}^{m}\left\|z_{j}\right\|_% {2}^{2}\right)^{1/2}.

Commitment Scheme.

For a commitment scheme $\Pi_{\mathsf{Com}}=({\mathsf{Setup}},\allowbreak\mathsf{Com})$ , let $\mathcal{M}_{\mathsf{Com}}$ denote the message space, and $\mathcal{R}_{\mathsf{Com}}$ denote the randomness space. The setup algorithm outputs a commitment key $\mathsf{ck}\leftarrow{\mathsf{Setup}}(1^{\lambda},1^{\ell})$ , and the commitment algorithm takes $\mathbf{m}\in\mathcal{M}_{\mathsf{Com}}$ and $\mathbf{r}\in\mathcal{R}_{\mathsf{Com}}$ as inputs, and outputs $\mathbf{c}\leftarrow\mathsf{Com}_{\mathsf{ck}}(\mathbf{m};\mathbf{r})$ . An opening of $\mathbf{c}$ is a pair $(\mathbf{m},\mathbf{r})$ , and verification recomputes $\mathsf{Com}_{\mathsf{ck}}(\mathbf{m};\mathbf{r})$ .

Definition 4.8.1 (Binding).

$\Pi_{\mathsf{Com}}=({\mathsf{Setup}},\allowbreak\mathsf{Com})$ is computationally binding if for every efficient adversary $\mathcal{A}$ ,

\Pr\left[\mathsf{Com}_{\mathsf{ck}}(\mathbf{m}_{0};\mathbf{r}_{0})=\mathsf{Com% }_{\mathsf{ck}}(\mathbf{m}_{1};\mathbf{r}_{1})\wedge\mathbf{m}_{0}\neq\mathbf{% m}_{1}~{}\middle|~{}\begin{aligned} \mathsf{ck}&\leftarrow{\mathsf{Setup}}(1^{% \lambda},1^{\ell}),\\ (\mathbf{m}_{0},\mathbf{r}_{0},\mathbf{m}_{1},\mathbf{r}_{1})&\leftarrow% \mathcal{A}(1^{\lambda},\mathsf{ck})\end{aligned}\right]\leq\mathsf{negl}(% \lambda),

If the same condition holds for unbounded adversaries, then $\Pi_{\mathsf{Com}}=({\mathsf{Setup}},\allowbreak\mathsf{Com})$ is statistically binding.

Definition 4.8.2 (Hiding).

$\Pi_{\mathsf{Com}}=({\mathsf{Setup}},\allowbreak\mathsf{Com})$ is computationally hiding if for every efficient adversary $(\mathcal{A}_{0},\mathcal{A}_{1})$ ,

\left|\Pr\left[b=b^{\prime}~{}\middle|~{}\begin{aligned} \mathsf{ck}&% \leftarrow{\mathsf{Setup}}(1^{\lambda},1^{\ell}),\\ (\mathbf{m}_{0},\mathbf{m}_{1},\mathsf{st})&\leftarrow\mathcal{A}_{0}(1^{% \lambda},\mathsf{ck}),\\ b&\stackrel{{\scriptstyle\textsc{r}}}{{\leftarrow}}\{0,1\},\\ \mathbf{r}&\leftarrow\mathcal{R}_{\mathsf{Com}},\\ \mathbf{c}_{b}&\leftarrow\mathsf{Com}_{\mathsf{ck}}(\mathbf{m}_{b};\mathbf{r})% ,\\ b^{\prime}&\leftarrow\mathcal{A}_{1}(\mathsf{st},\mathbf{c}_{b})\end{aligned}% \right]-\frac{1}{2}\right|\leq\mathsf{negl}(\lambda).

If the same condition holds for unbounded adversaries, then $\Pi_{\mathsf{Com}}=({\mathsf{Setup}},\allowbreak\mathsf{Com})$ is statistically hiding.

Module-SIS.

The binding property of Ajtai commitments is from the hardness of module-SIS assumption.

Definition 4.8.3 (Module-SIS [LS15]).

Let $q=q(\lambda),m=m(\lambda),n=n(\lambda),\beta=\beta(\lambda)$ , and $d=d(\lambda)$ . We say ${\mathsf{MSIS}}_{n,m,d,q,\beta}$ holds if for any efficient adversary $\mathcal{A}$ outputting $\mathbf{z}\in R^{m}$ , the following holds

\Pr\left[\mathbf{A}\mathbf{z}\equiv\boldsymbol{0}\mod q\wedge 0<\left\|\mathbf% {z}\right\|_{\infty}\leq\beta\mid\mathbf{A}\stackrel{{\scriptstyle\textsc{r}}}% {{\leftarrow}}R_{q}^{n\times m},\mathbf{z}\leftarrow\mathcal{A}(\mathbf{A})% \right]\leq\mathsf{negl}(\lambda).

When $n=1$ , the assumption specializes to the Ring-SIS assumption [PR06, LM06].

Ajtai Commitment.

We now recall the Ajtai commitment instantiated from module-SIS assumption.

Definition 4.8.4 (Ajtai Commitment [Ajt96]).

Over the above ring, we define the following parameters:

•

$\ell$ : the message dimension,
•

$k$ : the number of output ring elements.
•

$\mathcal{M}_{{\mathsf{Ajtai}}}$ : the message space $R_{p}^{\ell}$ , where elements of $R_{p}$ are lifted to $R_{q}$ by their centered coefficient representatives.
•

$\mathcal{R}_{{\mathsf{Ajtai}}}$ : the randomness space $R_{q}^{2k\log_{p}q}$ .
•

$\mathcal{D}_{{\mathsf{Ajtai}}}$ : the subgaussian distribution $\mathcal{D}_{\sigma}^{2k\log_{p}q}$ over the randomness space.
•

$B_{{\mathsf{Ajtai}}}$ : the binding space defined as follows,

$B_{{\mathsf{Ajtai}}}=\left\{\mathbf{s}=\left[\mathbf{r}^{\mathsf{T}}\mid% \mathbf{m}^{\mathsf{T}}\right]^{\mathsf{T}}\in R^{\ell+2k\log_{p}q}~{}:~{}% \left\|\mathbf{s}\right\|_{\infty}\leq B\right\}.$

We construct $\Pi_{{\mathsf{Ajtai}}}=({\mathsf{Setup}},\allowbreak\mathsf{Com})$ over $R_{p}$ as follows:

•

${\mathsf{Setup}}(1^{\lambda},1^{\ell}):$ Sample $\mathbf{A}_{1}\stackrel{{\scriptstyle\textsc{r}}}{{\leftarrow}}R_{q}^{k\times 2% k\log_{p}q}$ and $\mathbf{A}_{2}\stackrel{{\scriptstyle\textsc{r}}}{{\leftarrow}}R_{q}^{k\times\ell}$ , and output $\mathsf{ck}=\mathbf{A}=\left[\mathbf{A}_{1}\mid\mathbf{A}_{2}\right]$ .
•

$\mathsf{Com}_{\mathsf{ck}}(\mathbf{m};\mathbf{r}):$ On input the message $\mathbf{m}\in R_{p}^{\ell}$ and $\mathbf{r}\in R_{q}^{2k\log_{p}q}$ , output $\mathbf{c}=\mathbf{A}_{1}\mathbf{r}+\mathbf{A}_{2}\mathbf{m}\in R_{q}^{k}$ .

An opening is $(\mathbf{m},\mathbf{r})$ , and verification recomputes the commitment.

Lemma 4.8.5.

Ajtai commitment is computationally binding and statistically hiding.

Proof.

Hiding follows from the Leftover Hash Lemma: $(\mathbf{A}_{1},\mathbf{A}_{1}\mathbf{r})$ is statistically close to uniformly random, and hence the commitment scheme is statistically hiding. Let $n^{\prime}=k,m^{\prime}=\ell+2k\log_{p}q$ , and $2B\leq\beta$ , so long as ${\mathsf{MSIS}}_{n^{\prime},m^{\prime},d,q,\beta}$ is hard, the commitment scheme is computationally binding. ∎

Amortized Linear Relation Proof.

We now describe the amortized proof for many linear relations over $R_{q}$ . The public statement consists of matrices $\mathbf{A}\in R_{q}^{r\times v}$ and $\mathbf{T}\in R_{q}^{r\times\ell}$ , and the witness is $\mathbf{S}=\left[\mathbf{s}_{1}\mid\cdots\mid\mathbf{s}_{\ell}\right]\in R^{v% \times\ell}$ , where each $\mathbf{s}_{i}$ has $\ell_{\infty}$ -norm upper bounded by a bound $B_{\mathsf{lin}}$ , satisfying $\mathbf{A}\mathbf{S}\equiv\mathbf{T}\mod q$ .

By linearity of the Ajtai commitment definition 4.8.4, the commitments to the compressed columns $\mathbf{S}\mathbf{C}$ can be obtained by applying the same linear combinations to the commitments of the columns of $\mathbf{S}$ .

We begin by describing the “compression lemma” that help establish amortized proof.

Lemma 4.8.6.

Let $\mathbb{G}$ be an abelian group, and $\mathbf{x}=[x_{1},\ldots,x_{\ell}]^{\mathsf{T}}\in\mathbb{G}^{\ell}$ be nonzero. For $\mathbf{c}\stackrel{{\scriptstyle\textsc{r}}}{{\leftarrow}}\{0,1\}^{\ell}$ , $\Pr\left[\langle\mathbf{c},\mathbf{x}\rangle=0\right]\leq 1/2$ . Consequently, for $\mathbf{C}\stackrel{{\scriptstyle\textsc{r}}}{{\leftarrow}}\{0,1\}^{\ell\times t}$ , $\Pr\left[\mathbf{x}^{\mathsf{T}}\mathbf{C}=\boldsymbol{0}^{\mathsf{T}}\right]% \leq 2^{-t}$ .

Proof.

Pick $i$ with $x_{i}\neq 0$ , and fix all $c_{j}$ for $j\neq i$ . The two possible sums differ by $x_{i}$ , so at most one of them is zero. The conditional probability is at most $1/2$ , and averaging over the fixed bits gives the claim. ∎

Immediate by lemma 4.8.6, if $\mathbf{A}\mathbf{S}^{\prime}\not\equiv\mathbf{T}\mod q$ , for $\mathbf{C}\stackrel{{\scriptstyle\textsc{r}}}{{\leftarrow}}\{0,1\}^{\ell\times t}$ , $\Pr\left[\mathbf{A}\mathbf{S}^{\prime}\mathbf{C}\equiv\mathbf{T}\mathbf{C}\mod q% \right]\leq 2^{-t}$ .

Protocol Construction.

The prover commits to each $\mathbf{s}_{i}$ using the Ajtai commitment definition 4.8.4.

Let $\mathcal{C}$ be the challenge set, that is $\{0,1\}$ when $R=\mathbb{Z}$ , otherwise $\{0\}\cup\{\pm X^{j}\}_{j<d}$ when $R=\mathbb{Z}[X]/(X^{d}+1)$ .

Commit.

For $i\in[1,\ell]$ , the prover samples $\mathbf{r}_{i}\leftarrow\mathcal{D}_{{\mathsf{Ajtai}}}$ and sends $\mathbf{c}_{i}=\mathsf{Com}_{\mathsf{ck}}(\mathbf{s}_{i};\mathbf{r}_{i})$ . Let $\mathbf{C}_{\rm com}=[\mathbf{c}_{1}\mid\ldots\mid\mathbf{c}_{\ell}]$ .
Challenge.

The verifier samples $\mathbf{C}\stackrel{{\scriptstyle\textsc{r}}}{{\leftarrow}}\mathcal{C}^{\ell% \times(\lambda+2)}$ .
Response.

The prover computes $\mathbf{Y}\leftarrow\mathbf{S}\mathbf{C}$ and the compressed randomness $\mathbf{R}=[\mathbf{r}_{1}\mid\ldots\mid\mathbf{r}_{\ell}]\mathbf{C}$ , and sends over $(\mathbf{Y},\mathbf{R})$ .
Verification.

The verifier checks $(\mathbf{Y},\mathbf{R})$ are consistent with the compressed commitments by $\mathbf{C}_{\mathsf{Com}}\mathbf{C}=\mathsf{Com}_{\mathsf{ck}}(\mathbf{Y};% \mathbf{R})$ .

Completeness is immediate.

Special Knowledge Soundness.

We now show the (special) knowledge soundness of an accepting prover.

Here, $v$ is the witness dimension for each relation, $t=\lambda+2$ , and $\ell$ is the number of relations being batched. Fix a statement $(\mathbf{A},\mathbf{T})$ and a first message $\mathbf{C}_{\mathsf{Com}}$ .

Theorem 4.8.7.

If $\mathcal{P}^{*}$ responds to a random challenge $\mathbf{C}\stackrel{{\scriptstyle\textsc{r}}}{{\leftarrow}}\mathcal{C}^{\ell% \times t}$ , and convinces the verifier with probability $\varepsilon\geq 2^{-\lambda}$ , then the extractor should recover a matrix $\mathbf{S}\in R^{v\times\ell}$ such that $\mathbf{A}\mathbf{S}\equiv c\mathbf{T}\mod q$ ²⁰²⁰20 When $R=\mathbb{Z}$ , $c=1$ ; otherwise when $R$ is a polynomial ring, $c=2$ . , together with extracted randomness, open the commitments in $\mathbf{C}_{\mathsf{Com}}$ , and the extracted columns are short. The extractor runs in expected time $\mathsf{poly}(\lambda,1/\varepsilon)$ .

We start by describing how to extract a column of the witness $(\mathbf{s}_{i},\mathbf{r}_{i})$ , which can be generalized to all columns. For an extractor $\mathcal{E}^{\mathcal{P}^{*}}$ , it rewinds the prover to its first message $\mathbf{C}_{\mathsf{Com}}$ (so as to pin down the prover randomness), together with all rows of the challenge $\mathbf{C}\in\mathcal{C}^{\ell\times t}$ . It then resamples only the $i^{\mathrm{th}}$ row of $\mathbf{C}$ , yielding $\mathbf{C}^{\prime}$ .

We now introduce a helpful lemma via probabilistic method related to the extraction process.

Lemma 4.8.8 (Heavy Row Lemma [Dam10]).

Let $\mathbf{H}\in\{0,1\}^{n\times m}$ has density at least $\varepsilon$ , namely at least $\varepsilon nm$ entries are 1. We say that a row $a\in[1,n]$ is heavy, if there are more than $\varepsilon m/2$ entries are 1, namely the density in this row is at least $\varepsilon/2$ . Then a uniformly random $1$ -entry of $\mathbf{H}$ lies in a heavy row with probability at least $1/2$ .

Proof.

The total number of $1$ -entries in $\mathbf{H}$ is at least $\varepsilon mn$ , while the number of $1$ -entries in non-heavy rows is at most $\varepsilon mn/2$ . Hence, the probability of an 1-entry lying in a light row is at most $1/2$ , and an 1-entry lying in a heavy row is at least $1/2$ . ∎

Therefore, consider building up a matrix $\mathbf{H}$ over $\{0,1\}$ as follows. The rows are indexed by the prover randomness and by all challenge rows except the $i^{\mathrm{th}}$ row. The columns are indexed by the possible $i^{\mathrm{th}}$ row challenges $\boldsymbol{\alpha}_{i}\in\mathcal{C}^{t}$ . The entry is $1$ if $\mathcal{P}^{*}$ gives an accepting response on the corresponding full challenge matrix, and $0$ otherwise.

The density of $\mathbf{H}$ is at least $\varepsilon$ as the prover convinces the verifier with probability at least $\varepsilon$ . Hence, by lemma 4.8.8, conditioned on a random challenge is accepting, with probability at least $1/2$ the corresponding row of $\mathbf{H}$ is heavy. Thus, after the extractor finds one accepting transcript in a heavy row, resampling only the $i^{\mathrm{th}}$ row in $\mathbf{C}$ gives another accepting transcript with probability at least $\varepsilon/2$ .

Immediately, this gives a randomized algorithm for the extractor to extract a column of witness $(\mathbf{s}_{i},\mathbf{r}_{i})$ in expected polynomial time. First, the extractor samples accepting $(\mathbf{C},\mathbf{Y},\mathbf{R})$ on the first $\mathbf{C}_{\mathsf{Com}}$ . Then, fix the prover randomness and $\mathbf{C}$ except the $i^{\mathrm{th}}$ row. Resample the $i^{\mathrm{th}}$ row independently up to $N=O(\lambda/\varepsilon)$ times. If one obtains an accepting $(\mathbf{C}^{\prime},\mathbf{Y}^{\prime},\mathbf{R}^{\prime})$ whose $i^{\mathrm{th}}$ row differs from that of $\mathbf{C}$ , continue with the extraction below. Otherwise, abort and restart.

The runtime analysis is similar to the expectation of a geometrically distributed random variable. Similar to the relaxation in lemma 1.5.36, we have

	$\displaystyle\Pr\left[\text{abort}\right]$	$\displaystyle=\Pr\left[\text{abort}\mid i^{\mathrm{th}}\text{ row of }\mathbf{% C}\text{ is heavy for }\mathbf{H}\right]\cdot\Pr\left[i^{\mathrm{th}}\text{ % row of }\mathbf{C}\text{ is heavy for }\mathbf{H}\right]$
		$\displaystyle+\Pr\left[\text{abort}\mid i^{\mathrm{th}}\text{ row of }\mathbf{% C}\text{ is light for }\mathbf{H}\right]\cdot\Pr\left[i^{\mathrm{th}}\text{ % row of }\mathbf{C}\text{ is light for }\mathbf{H}\right]$
		$\displaystyle\leq\Pr\left[\text{abort}\mid i^{\mathrm{th}}\text{ row of }% \mathbf{C}\text{ is heavy for }\mathbf{H}\right]+\Pr\left[i^{\mathrm{th}}\text% { row of }\mathbf{C}\text{ is light for }\mathbf{H}\right].$

The second term is at most $1/2$ by the lemma 4.8.8. The first term is upper bounded as follows. Since the $i^{\mathrm{th}}$ row of $\mathbf{C}$ is heavy on $\mathbf{H}$ , the probability of choosing a rejecting challenge is at most $1-\varepsilon/2$ , also excluding the first accepting $\mathbf{C}$ , then the rejecting probability is at most $1-\varepsilon/2+\left|\mathcal{C}\right|^{-t}$ . Repeating $N$ times, the first term is at most $(1-\varepsilon/2+\left|\mathcal{C}\right|^{-t})^{N}$ . Thus, the aborting probability is at most

\frac{1}{2}+\left(1-\frac{\varepsilon}{2}+\frac{1}{\left|\mathcal{C}\right|^{t% }}\right)^{N}.

If $\varepsilon>2^{-\lambda}$ , then $1-\varepsilon/2+\left|\mathcal{C}\right|^{-t}>1-\varepsilon/4>\exp(-% \varepsilon/4)$ , which leads to the final upper bound being $1/2+2^{-\lambda}$ . Since each run takes $O(N)$ time, then extractor runs in expected $\mathsf{poly}(\lambda,1/\varepsilon)$ .

Suppose the extractor obtains two accepting transcripts $(\mathbf{C},\mathbf{Y},\mathbf{R})$ and $(\mathbf{C}^{\prime},\mathbf{Y}^{\prime},\mathbf{R}^{\prime})$ whose challenges differ only on the $i^{\mathrm{th}}$ row, and differ nontrivially in that row. Write $\boldsymbol{\alpha}_{i},\boldsymbol{\alpha}_{i}^{\prime}\in\mathcal{C}^{t}$ for the two $i^{\mathrm{th}}$ rows and let

\Delta\mathbf{C}=\mathbf{C}-\mathbf{C}^{\prime},\qquad\Delta\mathbf{Y}=\mathbf% {Y}-\mathbf{Y}^{\prime},\qquad\Delta\mathbf{R}=\mathbf{R}-\mathbf{R}^{\prime},

then the commitment openings satisfy

\mathbf{C}_{\mathsf{Com}}\cdot\Delta\mathbf{C}=\mathsf{Com}_{\mathsf{ck}}(% \Delta\mathbf{Y};\Delta\mathbf{R}).

Choose a coordinate $j$ such that $\alpha=(\boldsymbol{\alpha}_{i}-\boldsymbol{\alpha}_{i}^{\prime})_{j}\in% \mathcal{C}-\mathcal{C}$ , then the $j^{\mathrm{th}}$ column of the first equation gives

\mathsf{Com}_{\mathsf{ck}}(\Delta\mathbf{y}_{j};\Delta\mathbf{r}_{j})\equiv% \mathbf{A}_{1}\cdot\Delta\mathbf{r}_{j}+\mathbf{A}_{2}\cdot\Delta\mathbf{y}_{j% }\equiv\alpha\mathbf{c}_{i}\mod q,

so $(\Delta\mathbf{y}_{j},\Delta\mathbf{r}_{j})$ is an opening of the scaled commitment $\alpha\mathbf{c}_{i}$ .

By the challenge-set property, there exists a short $g\in R$ such that $g\alpha=c$ . Hence

\mathsf{Com}_{\mathsf{ck}}(g\cdot\Delta\mathbf{y}_{j};g\cdot\Delta\mathbf{r}_{% j})\equiv c\mathbf{c}_{i}\mod q.

The extractor therefore obtains the $i^{\mathrm{th}}$ scaled opening, and repeating the same row-local procedure for every $i\in[1,\ell]$ yields openings of all columns of $c\mathbf{C}_{\mathsf{Com}}$ . Shortness follows from the response norm checks in accepting transcripts; the exact checks and constants are accounted for in the norm-growth analysis.