Recursive inner product argument

$$This article is a summary of [BCCGP16].

Consider a situation prover wants to prove he knows two vectors (in ${\mathbb{F}}_p^n$) such that the inner product is given $z\in {\mathbb{F}}_p$. The simplest way to prove this is to send each vector to a verifier, but this is too long proof and also not zero-knowledge. In the paper, the protocol recursively reduces the length of witness to obtain $O(\log n)$ proof.

Let's describe the situation formally. Information only the prover knows is red.

$\mathbb{G}$ : additive cyclic group of order prime $p$ with DLP security.

$g_i,h_i\in \mathbb{G}$ : fixed generators for $1\le i\le n$.

$a_i,b_i$ $\in {\mathbb{F}}_p$ : witness for $1\le i\le n$.

The prover commits the witness using $A,B\in \mathbb{G}$ and $z\in {\mathbb{F}}_p$ such that

$$A=\sum _{i=1}^n{a}_i{g}_i,B=\sum _{i=1}^n{b}_i{h}_i,z=\sum _{i=1}^n{a}_i{b}_i.$$

and wants to prove this.

Protocol

Now, the length of the witness is $2n$. We want to reduce this size to $\frac{2n}{m}$ in the first round, and to $\frac{2n}{m^2}$ next round, and so on.

For the first round choose $m$ which divides $n$, and partite $g_i$ and $a_i$ into $m$ blocks. Namely,

$$\begin{array}{rl}{\mathbf{g}}_1& =(g_1,g_2,\dots ,g_{\frac{n}{m}})\\ {\mathbf{g}}_2& =(g_{\frac{n}{m}+1},g_{\frac{n}{m}+2},\dots ,g_{\frac{2n}{m}})\\ ⋮\\ {\mathbf{g}}_m& =(g_{\frac{(m-1)n}{m}+1},g_{\frac{(m-1)n}{m}+2},\dots ,g_n)\end{array}$$

Similarly, define ${\mathbf{a}}_i$ for $1\le i\le m$. The prover then commits new elements

$$A_k=\sum {\mathbf{a}}_{i+k}{\mathbf{g}}_i$$

for $1-m\le k\le m-1$. Here, the vector multiplication is like inner product, for example, ${\mathbf{a}}_1{\mathbf{g}}_1=a_1{g}_1+a_2{g}_2+\cdots +a_{\frac{2n}{m}}{g}_{\frac{2n}{m}}$. I omitted the start and end of the sum, which is as many indices as possible. Similarly, define ${\mathbf{h}}_i,{\mathbf{b}}_i$ and commit $B_k$ and $z_k$, where $z_k$ is defined by

$$z_k=\sum {\mathbf{a}}_i\cdot {\mathbf{b}}_{i+k}$$

Next, the verifier makes a random challenge $x\in {\mathbb{F}}_p^{\times }$. Both prover and verifier compute a reduced statement for the next round using committed $A_k,B_k,z_k$

$$\begin{array}{rl}(g_1^{\prime },g_2^{\prime },\dots ,g_{\frac{n}{m}}^{\prime })& =\sum _{i=1}^m{x}^i{\mathbf{g}}_i\\ (h_1^{\prime },h_2^{\prime },\dots ,h_{\frac{n}{m}}^{\prime })& =\sum _{i=1}^m{x}^i{\mathbf{h}}_i\\ A^{\prime }& =\sum _{k=1-m}^{m-1}{x}^k{A}_k\\ B^{\prime }& =\sum _{k=1-m}^{m-1}{x}^{-k}{B}_k\\ z^{\prime }& =\sum _{k=1-m}^{m-1}{z}_k{x}^{-k}\end{array}$$

And, the prover computes new witness

$$\begin{array}{rl}(a_1^{\prime },a_2^{\prime },\dots ,a_{\frac{n}{m}}^{\prime })& =\sum _{i=1}^m{x}^i{\mathbf{a}}_i\\ (b_1^{\prime },b_2^{\prime },\dots ,b_{\frac{n}{m}}^{\prime })& =\sum _{i=1}^m{x}^i{\mathbf{b}}_i\end{array}$$

Direct computation shows that the original proof implies

$$A^{\prime }=\sum _{i=1}^n{a}_i^{\prime }{g}_i^{\prime },B^{\prime }=\sum _{i=1}^n{b}_i^{\prime }{h}_i^{\prime },z^{\prime }=\sum _{i=1}^n{a}_i^{\prime }{b}_i^{\prime }.$$

and the length of witness reduces to $2\frac{n}{m}$.

By choosing proper $m$ and random challenge each round, we repeat this process until the length becomes sufficiently small.

Efficiency

Suppose $n$ is a power of $2$ and we choose the same $m$ for each round. For the prover, the main cost is from computing $A_k$, $B_k$, and $z_k$, which requires at most $\frac{6n{m}^2}{(m-1)\log m}$ group exponentiation and $\frac{n{m}^2}{m+1}$ field multiplication. The verifier needs to compute new statements each round, which requires at most $\frac{2nm}{(m-1)\log m}$ group exponentiation.