1\documentclass{article}
  2\usepackage[utf8]{inputenc}
  3\usepackage{amsfonts}
  4\usepackage{amsthm}
  5\usepackage{amsmath}
  6\usepackage{amssymb}
  7\usepackage{mathtools}
  8\usepackage{enumerate}
  9\usepackage{hyperref}
 10\hypersetup{
 11    colorlinks,
 12    citecolor=black,
 13    filecolor=black,
 14    linkcolor=black,
 15    urlcolor=blue
 16}
 17% \usepackage{xcolor}
 18
 19% prevent warnings of underfull \hbox:
 20% \usepackage{etoolbox}
 21% \apptocmd{\sloppy}{\hbadness 4000\relax}{}{}
 22
 23\theoremstyle{definition}
 24\newtheorem{definition}{Def}[section]
 25\newtheorem{theorem}[definition]{Thm}
 26\newtheorem{innersolution}{}
 27\newenvironment{solution}[1]
 28{\renewcommand\theinnersolution{#1}\innersolution}
 29{\endinnersolution}
 30
 31
 32\title{Weil Pairing - study}
 33\author{arnaucube}
 34\date{August 2022}
 35
 36\begin{document}
 37\maketitle
 38
 39\begin{abstract}
 40  Notes taken from \href{https://sites.google.com/site/matanprasma/artifact}{Matan Prasma} math seminars and also while reading about Bilinear Pairings. Usually while reading papers and books I take handwritten notes, this document contains some of them re-written to $LaTeX$.
 41
 42	The notes are not complete, don't include all the steps neither all the proofs. I use these notes to revisit the concepts after some time of reading the topic.
 43\end{abstract}
 44
 45\tableofcontents
 46
 47\section{Rational functions}
 48
 49Let $E/\Bbbk$ be an elliptic curve defined by: $y^2 = x^3 + Ax + B$.
 50
 51\paragraph{set of polynomials over $E$:}
 52$\Bbbk[E] := \Bbbk[x,y] / (y^2 - x^3 - Ax - B =0)$
 53
 54we can replace $y^2$ in the polynomial $f \in \Bbbk[E]$ with $x^3 + Ax + B$
 55
 56\paragraph{canonical form:} $f(x,y) = v(x)+y w(x)$ for $v, w \in \Bbbk[x]$
 57\paragraph{conjugate:} $\overline{f} = v(x) - y w(x)$
 58\paragraph{norm:} $N_f = f \cdot \overline{f} = v(x)^2 - y^2 w(x)^2 = v(x)^2 - (x^3 + Ax + B) w(x)^2 \in \Bbbk[x] \subset \Bbbk[E]$
 59
 60we can see that $N_{fg} = N_f \cdot N_g$
 61
 62\paragraph{set of rational functions over $E$:}
 63$\Bbbk(E) := \Bbbk[E] \times \Bbbk[E]/ \thicksim$
 64
 65For $r\in \Bbbk(E)$ and a finite point $P \in E(\Bbbk)$, $r$ is \emph{finite} at $P$ iff
 66$$\exists~ r=\frac{f}{g} ~\text{with}~ f,g \in \Bbbk[E],~ s.t.~ g(P) \neq 0$$
 67We define $r(P)=\frac{f(P)}{g(P)}$. Otherwise, $r(P)=\infty$.
 68
 69Remark: $r=\frac{f}{g} \in \Bbbk(E)$, $r=\frac{f}{g}=\frac{f \cdot \overline{g}}{g \cdot \overline{g}} = \frac{f \overline{g}}{N_g}$, thus
 70$$r(x,y)=\frac{ (f \overline{g})(x,y)}{N_g(x,y)} = \underbrace{ \frac{v(x)}{N_g(x)} + y \frac{w(x)}{N_g(x)} }_\text{canonical form of $r(x,y)$}$$
 71
 72\paragraph{degree of $f$:} Let $f\in \Bbbk[E]$, in canonical form: $f(x,y) = v(x) + y w(x)$,
 73$$deg(f) := max\{ 2 \cdot deg_x(v), 3+2 \cdot deg_x(w) \}$$
 74
 75For $f,g \in \Bbbk[E]$:
 76\begin{enumerate}[i.]
 77  \item $deg(f) = deg_x(N_f)$
 78  \item $deg(f \cdot g) = deg(f) + deg(g)$
 79\end{enumerate}
 80
 81\begin{definition}
 82  Let $r=\frac{f}{g} \in \Bbbk(E)$
 83  \begin{enumerate}[i.]
 84    \item if $deg(f) < deg(g):~ r(0)=0$
 85    \item if $deg(f) > deg(g):~ r ~\text{is not finite at}~ 0$
 86    \item if $deg(f) = deg(g)$ with $deg(f)$ even:\\
 87      $f$'s canonical form leading terms $ax^d$\\
 88      $g$'s canonical form leading terms $bx^d$\\
 89      $a,b \in \Bbbk^\times,~ d=\frac{deg(f)}{2}$, set $r(0)=\frac{a}{b}$
 90    \item if $deg(f) = deg(g)$ with $deg(f)$ odd\\
 91      $f$'s canonical form leading terms $ax^d$\\
 92      $g$'s canonical form leading terms $bx^d$\\
 93      $a,b \in \Bbbk^\times,~ deg(f)=deg(g)=3+2d$, set $r(0)=\frac{a}{b}$
 94  \end{enumerate}
 95\end{definition}
 96
 97\subsection{Zeros, poles, uniformizers and multiplicities}
 98
 99$r \in \Bbbk(E)$ has a \emph{zero} in $P\in E$ if $r(P)=0$\\
100$r \in \Bbbk(E)$ has a \emph{pole} in $P\in E$ if $r(P)$ is not finite.
101
102\paragraph{uniformizer:} Let $P\in E$,
103uniformizer: rational function $u \in \Bbbk(E)$ with $u(P)=0$ if
104$\forall r\in \Bbbk(E) \setminus \{0\},~ \exists d \in \mathbb{Z},~ s\in \Bbbk(E)$ finite at $P$ with $s(P) \neq 0$ s.t.
105$$r=u^d \cdot s$$
106
107\paragraph{order:} Let $P \in E(\Bbbk)$, let $u \in \Bbbk(E)$ be a uniformizer at $P$.
108For $r \in \Bbbk(E) \setminus \{0\}$ being a rational function with $r=u^d \cdot s$ with $s(P)\neq 0, \infty$, we say that $r$ has \emph{order} $d$ at $P$ ($ord_P(r)=d$).
109
110\paragraph{multiplicity:} \emph{multiplicity of a zero} of $r$ is the order of $r$ at that point, \emph{multiplicity of a pole} of $r$ is the order of $r$ at that point.
111
112if $P \in E(\Bbbk)$ is neither a zero or pole of $r$, then $ord_P(r)=0$ ($=d,~ r=u^0s$).
113
114\vspace{0.5cm}
115\begin{minipage}{4.3 in}
116    \paragraph{Multiplicities, from the book "Elliptic Tales"} (p.69), to provide intuition
117
118    Factorization into \emph{linear factors}: $p(x)=c\cdot (x-a_1) \cdots (x-a_d)$\\
119    $d$: degree of $p(x)$, $a_i \in \Bbbk$\\
120    Solutions to $p(x)=0$ are $x=a_1, \ldots, a_d$ (some $a_i$ can be repeated)\\
121    eg.: $p(x)=(x-1)(x-1)(x-3)$, solutions to $p(x)=0:~ 1, 1, 3$\\
122    $x=1$ is a solution to $p(x)=0$ of \emph{multiplicity} 2.
123
124    The total number of solutions (counted with multiplicity) is $d$, the degree of the polynomial whose roots we are finding.
125\end{minipage}
126
127
128\section{Divisors}
129
130\begin{definition}{Divisor}
131  $$D= \sum_{P \in E(\Bbbk)} n_p \cdot [P]$$
132\end{definition}
133
134\begin{definition}{Degree \& Sum}
135  $$deg(D)= \sum_{P \in E(\Bbbk)} n_p$$
136  $$sum(D)= \sum_{P \in E(\Bbbk)} n_p \cdot P$$
137\end{definition}
138
139
140The set of all divisors on $E$ forms a group: for $D = \sum_{P\in E(\Bbbk)} n_P[P]$ and $D' = \sum_{P\in E(\Bbbk)} m_P[P]$,
141$$D+D' = \sum_{P\in E(\Bbbk)} (n_P + m_P)[P]$$
142
143\begin{definition}{Associated divisor}
144  $$div(r) = \sum_{P \in E(\Bbbk)} ord_P(r)[P]$$
145\end{definition}
146
147Observe that
148\begin{enumerate}
149  \item[] $div(rs) = div(r)+div(s)$
150  \item[] $div(\frac{r}{s}) = div(r)-div(s)$
151\end{enumerate}
152
153Observe that
154$$\sum_{P \in E(\Bbbk)} ord_P(r) \cdot P = 0$$
155
156\begin{definition}{Support of a divisor}
157  $$\sum_P n_P[P], ~\forall P \in E(\Bbbk) ~\text{s.t.}~ n_P \neq 0$$
158\end{definition}
159
160\begin{definition}{Principal divisor}
161  iff
162  $$deg(D)=0$$
163  $$sum(D)=0$$
164\end{definition}
165$D \sim D'$ iff $D - D'$ is principal.
166
167
168\begin{definition}{Evaluation of a rational function} (function $r$ evaluated at $D$)
169  $$r(D)= \prod r(P)^{n_p}$$
170\end{definition}
171
172\section{Weil reciprocity}
173\begin{theorem}{(Weil reciprocity)}
174  Let $E/ \Bbbk$ be an e.c. over an algebraically closed field. If $r,~s \in \Bbbk\setminus \{0\}$ are rational functions whose divisors have disjoint support, then
175$$r(div(s)) = s(div(r))$$
176\end{theorem}
177Proof. (todo)
178
179\paragraph{Example}
180\begin{align*}
181  p(x)=x^2 - 1,&~ q(x)=\frac{x}{x-2}\\
182  div(p)&= 1 \cdot [1] + 1 \cdot [-1] - 2 \cdot [\infty]\\
183  div(q)&= 1 \cdot [0] - 1 \cdot [2]\\
184	&\text{(they have disjoint support)}\\
185  p(div(q)) &= p(0)^1 \cdot p(2)^{-1}= (0^2 - 1)^1 \cdot (2^2 - 1)^{-1} = \frac{-1}{3}\\
186  q(div(p)) &= q(1)^1 \cdot q(-1)^1 - q(\infty)^2\\
187	    &= (\frac{1}{1-2})^1 \cdot (\frac{-1}{-1-2})^1 \cdot (\frac{\infty}{\infty - 2})^2 = \frac{-1}{3}
188\end{align*}
189
190so, $p(div(q))=q(div(p))$.
191
192\section{Generic Weil Pairing}
193Let $E(\Bbbk)$, with $\Bbbk$ of char $p$, $n$ s.t. $p \nmid n$.
194
195$\Bbbk$ large enough: $E(\Bbbk)[n] = E(\overline{\Bbbk}) = \mathbb{Z}_n \oplus \mathbb{Z}_n$ (with $n^2$ elements).
196
197For $P, Q \in E[n]$,
198\begin{align*}
199  D_P &\sim [P] - [0]\\
200  D_Q &\sim [Q] - [0]
201\end{align*}
202
203We need them to have disjoint support:
204\begin{align*}
205  D_P &\sim [P] - [0]\\
206  D_Q' &\sim [Q+T] - [T]
207\end{align*}
208
209$$\Delta D = D_Q - D_Q' = [Q] - [0] - [Q+T] + [T]$$
210
211
212Note that $n D_P$ and $n D_Q$ are principal. Proof:
213\begin{align*}
214  n D_P &= n [P] - n [O]\\
215  deg(n D_P) &= n - n = 0\\
216  sum(n D_P) &= nP - nO = 0
217\end{align*}
218($nP = 0$ bcs. $P$ is n-torsion)
219
220Since $n D_P,~ n D_Q$ are principal, we know that $f_P,~ f_Q$ exist.
221
222Take
223\begin{align*}
224  f_P &: div(f_P) = n D_P\\
225  f_Q &: div(f_Q) = n D_Q
226\end{align*}
227
228We define
229$$
230e_n(P, Q) = \frac{f_P(D_Q)}{f_Q(D_P)}
231$$
232
233Remind: evaluation of a rational function over a divisor $D$:
234\begin{align*}
235  D &= \sum n_P [P]\\
236  r(D) &= \prod r(P)^{n_P}
237\end{align*}
238
239If $D_P = [P+S] - [S],~~ D_Q=[Q-T]-[T]$ what is $e_n(P, Q)$?
240
241\begin{align*}
242  f_P(D_Q) &= f_P(Q+T)^1 \cdot f_P(T)^{-1}\\
243  f_Q(D_P) &= f_Q(P+S)^1 \cdot f_Q(S)^{-1}
244\end{align*}
245
246$$
247e_n(P, Q) = \frac{f_P(Q+T)}{f_P(T)} / \frac{f_Q(P+S)}{f_Q(S)}
248$$
249
250with $S \neq \{O, P, -Q, P-Q \}$.
251
252
253\section{Properties}
254\begin{enumerate}[i.]
255  \item $e_n(P, Q)^n = 1 ~\forall P,Q \in E[n]$\\
256    ($\Rightarrow~ e_n(P,Q)$ is a $n^{th}$ root of unity)
257  \item Bilinearity
258    $$e_n(P_1+P_2, Q) = e_n(P_1, Q) \cdot e_n(P_2, Q)$$
259    $$e_n(P, Q_1+Q_2) = e_n(P, Q_1) \cdot e_n(P, Q_2)$$
260    \emph{proof:}
261    recall that $e_n(P,Q)=\frac{g(S+P)}{g(S)}$, then,
262    \begin{align*}
263      e_n(P_1, Q) &\cdot e_n(P_2, Q) = \frac{g(P_1 + S)}{g(S)} \cdot \frac{g(P_2 + P_1 + S)}{g(P_1 + S)}\\
264				    &\text{(replace $S$ by $S+P_1$)}\\
265				    &= \frac{g(P_2 + P_1 + S)}{g(S)} = e_n(P_1+P_2, Q)
266    \end{align*}
267  \item Alternating
268    $$e_n(P, P)=1 ~\forall P\in E[n]$$
269  \item Nondegenerate
270    $$\text{if}~ e_n(P,Q)=1 ~\forall Q\in E[n],~ \text{then}~ P=0$$
271\end{enumerate}
272
273
274\section{Exercises}
275\emph{An Introduction to Mathematical Cryptography, 2nd Edition} - Section 6.8. Bilinear pairings on elliptic curves
276
277\begin{solution}{6.29}
278  $div(R(x) \cdot S(x)) = div( R(x)) + div( S(x))$, where $R(x), S(x)$ are rational functions.
279  \\proof:\\
280  \emph{Norm} of $f$: $N_f = f \cdot \overline{f}$, and we know that $N_{fg} = N_f \cdot N_g~\forall~\Bbbk[E]$,\\
281  then $$deg(f) = deg_x(N_f)$$\\
282  and $$deg(f \cdot g) = deg(f) + deg(g)$$
283
284  Proof:
285  $$deg(f \cdot g) = deg_x(N_{fg}) = deg_x(N_f \cdot N_g)$$
286  $$= deg_x(N_f) + deg_x(N_g) = deg(f) + deg(g)$$
287
288  So, $\forall P \in E(\Bbbk),~ ord_P(rs) = ord_P(r) + ord_P(s)$.\\
289  As $div(r) = \sum_{P\in E(\Bbbk)} ord_P(r)[P]$, $div(s) = \sum ord_P(s)[P]$.
290
291  So,
292  $$div(rs) = \sum ord_P(rs)[P]$$
293  $$= \sum ord_P(r)[P] + \sum ord_P(s)[P] = div(r) + div(s)$$
294\end{solution}
295
296\vspace{0.5cm}
297
298\begin{solution}{6.31}
299  $$e_m(P, Q) = e_m(Q, P)^{-1} \forall P, Q \in E[m]$$
300  Proof:
301  We know that $e_m(P, P) = 1$, so:
302  $$1 = e_m(P+Q, P+Q) = e_m(P, P) \cdot e_m(P, Q) \cdot e_m(Q, P) \cdot e_m(Q, Q)$$
303
304  and we know that $e_m(P, P) = 1$, then we have:
305  $$1 = e_m(P, Q) \cdot e_m(Q, P)$$
306  $$\Longrightarrow e_m(P, Q) = e_m(Q, P)^{-1}$$
307\end{solution}
308
309
310
311
312\end{document}