$\newcommand{\Z}{\mathbb{Z}} \newcommand{\N}{\mathbb{N}} \newcommand{\F}{\mathbb{F}} \newcommand{\G}{\mathbb{G}} \newcommand{\g}{\mathbf{g}} \newcommand{\h}{\mathbf{h}} \newcommand{\a}{\mathbf{a}} \newcommand{\b}{\mathbf{b}}$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 \G$ : fixed generators for $1 \leq i \leq n$.
${\color{red}a_i, b_i}$ $\in \F_p$ : witness for $1 \leq i \leq n$.
The prover commits the witness using $A, B \in \G$ and $z \in \F_p$ such that
$$A = \sum_{i=1}^n {\color{red}a_i} g_i, \ \ \ \ B = \sum_{i=1}^n {\color{red}b_i} h_i, \ \ \ \ z = \sum_{i=1}^n {\color{red}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{aligned} \g_1 &= (g_1, g_2, \ldots, g_{\frac{n}{m}}) \\ \g_2 &= (g_{\frac{n}{m}+1}, g_{\frac{n}{m}+2}, \ldots, g_{\frac{2n}{m}}) \\ \vdots \\ \g_m &= (g_{\frac{(m-1)n}{m} +1}, g_{\frac{(m-1)n}{m} +2}, \ldots, g_n) \end{aligned}$$
Similarly, define $\a_i$ for $1 \leq i \leq m$. The prover then commits new elements
$$A_k = \sum {\color{red}\a_{i+k}} \ \g_i$$
for $1-m \leq k \leq m-1$. Here, the vector multiplication is like inner product, for example, ${\color{red}\a_1} \g_1 = {\color{red}a_1} g_1 + {\color{red}a_2} g_2 + \cdots + {\color{red}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 $\h_i, {\color{red}\b_i}$ and commit $B_k$ and $z_k$, where $z_k$ is defined by
$$z_k = \sum {\color{red}\a_{i}} \cdot {\color{red}\b_{i+k}}$$
Next, the verifier makes a random challenge $x \in \F_p^\times$. Both prover and verifier compute a reduced statement for the next round using committed $A_k, B_k, z_k$
$$\begin{aligned} (g'_1, g'_2, \ldots, g'_{\frac{n}{m}}) &= \sum_{i=1}^m x^i \g_i \\ (h'_1, h'_2, \ldots, h'_{\frac{n}{m}}) &= \sum_{i=1}^m x^i \h_i \\ A' &= \sum_{k = 1-m}^{m-1} x^k A_k \\ B' &= \sum_{k = 1-m}^{m-1} x^{-k} B_k \\ z' &= \sum_{k = 1-m}^{m-1} z_k x^{-k} \end{aligned}$$
And, the prover computes new witness
$$\begin{aligned} {\color{red}(a'_1, a'_2, \ldots, a'_{\frac{n}{m}})} &= \sum_{i=1}^m x^i {\color{red}\a_i} \\ {\color{red}(b'_1, b'_2, \ldots, b'_{\frac{n}{m}})} &= \sum_{i=1}^m x^i {\color{red}\b_i} \end{aligned}$$
Direct computation shows that the original proof implies
$$A' = \sum_{i=1}^n {\color{red}a'_i} g'_i, \ \ \ \ B' = \sum_{i=1}^n {\color{red}b'_i} h'_i, \ \ \ \ z' = \sum_{i=1}^n {\color{red}a'_i b'_i}.$$
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{6 nm^2}{(m-1)\log m}$ group exponentiation and $\frac{nm^2}{m+1}$ field multiplication. The verifier needs to compute new statements each round, which requires at most $\frac{2 nm}{(m-1)\log m}$ group exponentiation.
댓글
댓글 쓰기