As a preliminary for the next few posts which will cover Liam Eagen's inner product protocol, I will introduce some algebraic geometry about elliptic curves. Let $\mathbb{F}$ be an algebraic closure of a finite field $\mathbb{F}_q$. Let $E$ be an elliptic curve which is defined by the Weierstrass equation $y^2z = x^3 + Axz^2 + Bz^3$ over $\mathbb{F}_q$. The elliptic curve is defined by a closed subvariety of the projective space
$$\mathbb{P}^2 = \{ (x:y:z) \in \mathbb{F}^3 \backslash\{(0:0:0)\} \} / \sim$$
where $(x:y:z) \sim (cx:cy:cz)$ for $c \neq 0 \in \mathbb{F}$. But, you can dehomogenize the equation with $z = 1$. So, the points of an elliptic curve $E(\mathbb{F})$ is the union of a subvariety defined by $y^2 = x^3 + Ax + B$ in $\mathbb{F}^2$ and a point $(0:1:0)$. We will call the point $O = (0:1:0)$ the point at infinity.
$$E(\mathbb{F}) = \{ (x,y) \in \mathbb{F}^2 \mid y^2 = x^3 + Ax + B \} \sqcup \{O\}.$$
And, the rational points of $E$ is
$$E(\mathbb{F}_q) = \{ (x,y) \in \mathbb{F}_q^2 \mid y^2 = x^3 + Ax + B \} \sqcup \{O\}.$$
Divisor group
Now, the divisor group of an elliptic curve is defined by the formal finite sum of points in elliptic curves. That is,
$$\mathrm{Div}(E) = \{ \sum_{P \in E(\mathbb{F})} v_P [P] \mid v_p \in \mathbb{Z}, v_p = 0 \text{ for all but finitely many} \}.$$
Let's denote as $[P]$ to emphasize it's different from the elliptic curve point. $\mathrm{Div} (E)$ has a natural abelian group structure. Then,
$$\mathrm{Div}_0(E) = \{ \sum_{P \in E(\mathbb{F})} v_P [P] \mid \sum v_P = 0 \}$$
is a subgroup. This natural object can explain why we define addition on elliptic curves in such a ridiculous way.
Rational functions
The polynomial ring $\mathbb{F}[x, y]$ is a ring of "regular" functions from $\mathbb{F}^2$ to $\mathbb{F}$. Likely, we can consider the ring of polynomial functions from an elliptic curve to $\mathbb{F}$, which is called the coordinate ring. For simplicity, I will restrict the elliptic curves out of the point at infinity. Since we identify two polynomials which have the same values on each point in elliptic curves, the coordinate ring is isomorphic to the quotient ring,
$$\mathbb{F}[E] \cong \mathbb{F}[x,y]/(y^2-x^3-Ax-B).$$
The quotient field of $\mathbb{F}[x,y]$ is a function field $\mathbb{F}(x,y)$, which consists of all rational functions with indeterminates $x,y$. We may consider the function field $\mathbb{F}$ as a field of "rational" functions from $\mathbb{F}^2$ to $\mathbb{F} \sqcup \{\infty\}$. Similarly, we can define the field of rational functions from an elliptic curve to $\mathbb{F} \sqcup \{\infty\}$, which is isomorphic to the quotient field of the coordinate ring.
$$\mathbb{F}(E) \cong \mathrm{Frac}( \mathbb{F}[x,y]/(y^2-x^3-Ax-B))$$
How do the elements in $\mathbb{F}(E)$ look like? Every element in $\mathbb{F}(E)$ is of the form $\frac{g(x,y)}{h(x,y)}$ for some $g, h \in \mathbb{F}[E]$. Since $y^2 = x^3 + Ax + B$ in $\mathbb{F}[E]$, we have $h_1, h_2 \in \mathbb{F}[x]$ such that
$$h(x,y) =h_1(x) + y h_2(x) \in \mathbb{F}[E].$$
Then,
$$\frac{g}{h} = \frac{g}{h_1 + y h_2} = \frac{g(h_1 - y h_2)}{(h_1 + y h_2)(h_1 - y h_2)} = \frac{g(h_1 - y h_2)}{h_1^2 -(x^2+Ax+B)h_2^2}.$$
So, we have $a(x), b(x) \in \mathbb{F}(x)$ such that $\frac{g}{h} = a(x) - y b(x) \in \mathbb{F}(E)$.
Picard group and elliptic curve addition
For any nonzero rational function $f \in \mathbb{F}(E)$, we can find its zeros and poles of $f$. For any $P \in E(\mathbb{F}) \backslash \{O\}$, define
$$v_P(f) = \left\{ \begin{array}{ll} \text{(order of zero)} & \text{if } f(P) = 0, \\ -\text{(order of pole)} & \text{if } f(P) = \infty, \\ 0 & \text{otherwise.} \end{array} \right.$$
and define $v_O(f) = -\sum_{P \in E(\mathbb{F}) \backslash \{O\}} v_P(f)$. It's always true that $v_P \in \mathbb{Z}$ are finite. Then, you can see that $v_P(f_1 f_2^{-1}) = v_P(f_1) - v_P(f_2)$. So,
$$\mathrm{div} :\mathbb{F}(E)^\times \to \mathrm{Div}_0(E)$$
defines a homomorphism. Now, define the Picard group of an elliptic curve by
$$\mathrm{Pic}(E) = \mathrm{Div}_0(E) / \mathrm{div}(\mathbb{F}(E)^\times).$$
Algebraic geometers show that the Picard group is bijective to $E(\mathbb{F})$ via
$$E(\mathbb{F}) \to \mathrm{Pic}(E), \text{ by } P \mapsto [P] - [O]$$
Now, we can define an addition on $E(\mathbb{F})$ using the natural addition of $\mathrm{Div}_0(E)$. Then, what is $P +Q \in E(\mathbb{F})$? Let $l \in \mathbb{F}(E)$ be a line through $P$ and $Q$. Bezout's theorem says $l$ has three zeros at $P, Q$, and another $R$ (here, just ignore the multiplicity or the point at infinity). Then,
$$\mathrm{div}(l) = [P]+[Q]+[R] -3[O] = ([P]-[O]) +([Q]-[O]) + ([R]-[O]) = 0 \in \mathrm{Pic}(E)$$
Let $R'$ be the $y$-inversion of $R$, and $l'$ be the line through $R$ and $R'$. Then,
$$\mathrm{div}(l') = [R] + [R'] -2[O] =([R]-[O]) +([R']-[O]) \in \mathrm{Pic}(E)$$
Therefore,
$$([P]-[O]) + ([Q]-[O]) = ([R']-[O]) \in \mathrm{Pic}(E) \text{ and } P+Q = R' \in E(\mathbb{F}).$$
Weil reciprocity
Next, we want to introduce a theorem that is critically used in Eagen's protocol. For any $f, g \in \mathbb{F}(E)$, we define a local symbol for $P \in E(\mathbb{F})$,
$$\langle f, g \rangle_P = (-1)^{v_P(\mathrm{div}(f)) v_P(\mathrm{div}(g))} \frac{f(P)^{v_P(\mathrm{div}(g))}}{g(P)^{v_P(\mathrm{div}(f))}}$$
For $P = O$, $f(O)$ depends on $d = v_O(\mathrm{div}(f))$. If $d > 0$ then $f(O) = \infty$ of order $d$. If $d < 0$ then $f(O) = 0$ of order $-d$. If $d = 0$ then $f$ is a constant function. The Weil reciprocity says that after multiplying all local symbols, it will be one.
$$\prod_{P \in E(\mathbb{F})} \langle f, g \rangle_P = 1$$
Note that the product is finite since $v_O(\mathrm{div}(f))$ and $v_O(\mathrm{div}(g))$ are zero for all $P$ but finitely many. I'd like to emphasize that some local symbols can be zero or infinity, but we can remove singularities after multiplying.
댓글
댓글 쓰기