This is a summary of [Ea22]. I will follow the notations from the previous post. Let's think about the prover has elliptic curve points $P_i \in E(\mathbb{F})$, and wants to prove that $\sum_{i=0}^n P_i = O$. To achieve effectiveness, the paper uses the function field and the Weil reciprocity.
First, the prover prepares a divisor witness $f \in \mathbb{F}$ such that
$$\mathrm{div}(f) = \sum_{i=0}^{n-1} [P_i] - n[O] \in \mathrm{Div}(E).$$
Such $f$ exists because $\sum P_i = O$ as mentioned in the previous post. Such $f$ can be constructed efficiently by Euclidean algorithm or other methods. The output will be $f = a(x) - y b(x)$ for polynomials $a,b$ whose degrees are less than $n/2$. I will explain this later. Now, the prover commits $f$ and $P_i$. Then, the verifier chooses a random line
$$l = y-\lambda x - \mu \in \mathbb{F}(E)$$
in the function field whose intersection with $E$ is contained in rational points $E(\mathbb{F}_q)$, and assume this line does not have zero at the point of infinity $O$. Alternatively, this can be done by choosing two points $A_0, A_1 \in E(\mathbb{F}_q)$ such that $A_0 \neq \pm A_1$. Then, the line through $A_0$ and $A_1$ will be the random challenge. The line intersects with another point $A_2 \in E(\mathbb{F})$ and it is automatically a rational point.
By the Weil reciprocity for $f$ and $l$,
$$D(A_0) D(A_1) D(A_2) = \prod_{i=0}^{n-1} l(P_i)$$
With some technical condition, log derivative with respect to$\mu$ yields
$$\sum_{i=0}^2 \frac{f'(A_i)}{f(A_i)} \frac{dx(A_i)}{d\mu} = \sum_{i=0}^{n-1} \frac{1}{l(P_i)}$$
where $f' = \frac{d}{dx} f$ and $x(A_i)$ is a polynomial which maps $(\lambda, \mu)$ to $x$-coordinate of $A_i$. The prover can make an arithmetic circuit with this equation instead of $\sum P_i = O$.
Higher multiplicity challenge
Instead of choosing distinct $A_0, A_1, A_2$ as a challenge, the verifier can choose $A_0 = A_1 \neq A_2$. That is, $l$ is the tangent line at $A_0$. Similarly, log derivative of the Weil reciprocity induces
$$-(c+2\lambda) \frac{f'(A_0)}{f(A_0)} + c \frac{f'(A_2)}{f(A_2)} = \sum_{i=0}^{n-1} \frac{x(A_0)- x(P_i)}{l(P_i)}$$
where
$$c = \frac{2y(A_2)(x(A_0)-x(A_2))}{3x(A_2)^2 + A_0 - 2 \lambda y(A_2)}$$
and $x(P)$ and $y(P)$ are $x$ and $y$-coordinate of elliptic curve points. This higher multiplicity challenge will reduce the number of multiplications in an arithmetic circuit and the length of the challenge.
To prove $\sum P_i = O$ by sending all the points, the arithmetic circuit needs to implement $n-1$ elliptic curve additions, which requires $14(n-1)$ field multiplications in general. But for higher multiplicity challenges, the circuit requires only $n+1$ multiplications while it needs more commitments.
Inner product version
Now, let's reduce more if there is a lot of repetition of points. That is, the prover wants to show
$$\sum_{i=0}^{n-1} e_i P_i = Q.$$
First, calculate $(-3)$-adic representation of $e_i$. We have unique $d_{ij} \in \{-1, 0, 1\}$ such that
$$e_i = \sum_{j=0}^l d_{ij} (-3)^j$$
and divide $e_i$ into $a_i$ and $b_i$ such that $e_i = a_i - b_i$, namely,
$$a_i = \sum_{j=0}^l \frac{|d_{ij}|+d_{ij}}{2} (-3)^j, \ \ \ b_i = \sum_{j=0}^l \frac{|d_{ij}|-d_{ij}}{2} (-3)^j$$
From here, all the summations without range run over $0 \leq i \leq n-1$. Define
$$\begin{align*} Q_{l-1} &= \sum d_{i, l-1} P_i \\ Q_{l-2} &= \sum (d_{i,l-1} (-3) + d_{i,l-2}) P_i \\ Q_{l-3} &= \sum (d_{i,l-1} (-3)^2 + d_{i,l-2} (-3) + d_{i,l-3} ) P_i \\ \vdots \\ Q_1 &= \sum (d_{i,l-1} (-3)^{l-2} + \cdots + d_{i,1}) P_i \\ Q_0 & = \sum e_i P_i = Q\end{align*} $$
Then, choose $f_j \in \mathbb{F}(E)$ such that
$$\begin{align*} \mathrm{div}(f_{l-1}) &= \sum [d_{i,l-1} P_i] + [-Q_{l-1}] - N_{l-1} [O] \\ \mathrm{div}(f_{l-2}) &= \sum [d_{i,l-2} P_i] + [-Q_{l-2}] + 3[-Q_{l-1}] - N_{l-2} [O] \\ \mathrm{div}(f_{l-3}) &= \sum [d_{i,l-3} P_i] + [-Q_{l-3}] + 3[-Q_{l-2}] - N_{l-3} [O] \\ \vdots \\ \mathrm{div}(f_1) &= \sum [d_{i,1} P_i] + [-Q_1] + 3[-Q_2] - N_1 [O] \\ \mathrm{div}(f_0) &= \sum [d_{i,0} P_i] + [-Q] + 3[-Q_1] - N_0 [O] \end{align*}$$
for some $N_j \in \mathbb{N}$ which makes $\mathrm{div}\in \mathrm{Div}_0(E)$. Then, we have
$$\mathrm{div}( f_0 f_1^{(-3)} \cdots f_{l-1}^{(-3)^{l-1}}) = [-Q] + \sum a_i [P_i] + b_i[-P_i] - N [O]$$
By the previous log derivations on the Weil reciprocity for $f_0 f_1^{(-3)} \cdots f_{l-1}^{(-3)^{l-1}}$, we have
$$\sum_{j=0}^{l-1} (-3)^j \sum_{i=0}^2 \frac{f_j'(A_i)}{f_j(A_i)} \frac{dx(A_i)}{d\mu} = T(-Q) + \sum_{i=0}^{n-1} a_i T(P_i) + b_i T(-P_i)$$
where
$$T(P) = \frac{1}{l(P)} \left\{ \begin{array} \ 1 \ & \text{if } A_0 \neq A_1 \\ x(A_0)-x(P) & \text{if } A_0 = A_1 \end{array} \right.$$
댓글
댓글 쓰기