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
 41  \href{https://sites.google.com/view/matanprasmashomepage/publications}{Matan
 42  Prasma} math seminars and while reading about Bilinear Pairings, Matan's
 43  course seminars are available at the following youtube playlist:\\
 44  \href{https://www.youtube.com/watch?v=JYSQYaAhJYc&list=PLV91V4b0yVqQ_inAjuIB5SwBNyYmA9S6M}{https://www.youtube.com/watch?v=JYSQYaAhJYc&list=PLV91V4b0yVqQ_inAjuIB5SwBNyYmA9S6M}
 45  and in his website there are the full notes on that course, named
 46  \emph{Elliptic curves over finite fields and their pairings, an elementary and rigorous account}\\
 47  \href{https://sites.google.com/view/matanprasmashomepage/publications}{https://sites.google.com/view/matanprasmashomepage/publications};
 48  highly recommended!
 49
 50  Usually while learning I take handwritten notes, this document contains some of them re-written to $LaTeX$.
 51  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.
 52\end{abstract}
 53
 54\tableofcontents
 55
 56\section{Rational functions}
 57
 58Let $E/\Bbbk$ be an elliptic curve defined by: $y^2 = x^3 + Ax + B$.
 59
 60\paragraph{set of polynomials over $E$:}
 61$\Bbbk[E] := \Bbbk[x,y] / (y^2 - x^3 - Ax - B =0)$
 62
 63we can replace $y^2$ in the polynomial $f \in \Bbbk[E]$ with $x^3 + Ax + B$
 64
 65\paragraph{canonical form:} $f(x,y) = v(x)+y w(x)$ for $v, w \in \Bbbk[x]$
 66\paragraph{conjugate:} $\overline{f} = v(x) - y w(x)$
 67\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]$
 68
 69we can see that $N_{fg} = N_f \cdot N_g$
 70
 71\paragraph{set of rational functions over $E$:}
 72$\Bbbk(E) := \Bbbk[E] \times \Bbbk[E]/ \thicksim$
 73
 74For $r\in \Bbbk(E)$ and a finite point $P \in E(\Bbbk)$, $r$ is \emph{finite} at $P$ iff
 75$$\exists~ r=\frac{f}{g} ~\text{with}~ f,g \in \Bbbk[E],~ s.t.~ g(P) \neq 0$$
 76We define $r(P)=\frac{f(P)}{g(P)}$. Otherwise, $r(P)=\infty$.
 77
 78Remark: $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
 79$$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)$}$$
 80
 81\paragraph{degree of $f$:} Let $f\in \Bbbk[E]$, in canonical form: $f(x,y) = v(x) + y w(x)$,
 82$$deg(f) := max\{ 2 \cdot deg_x(v), 3+2 \cdot deg_x(w) \}$$
 83
 84For $f,g \in \Bbbk[E]$:
 85\begin{enumerate}[i.]
 86  \item $deg(f) = deg_x(N_f)$
 87  \item $deg(f \cdot g) = deg(f) + deg(g)$
 88\end{enumerate}
 89
 90\begin{definition}
 91  Let $r=\frac{f}{g} \in \Bbbk(E)$
 92  \begin{enumerate}[i.]
 93    \item if $deg(f) < deg(g):~ r(0)=0$
 94    \item if $deg(f) > deg(g):~ r ~\text{is not finite at}~ 0$
 95    \item if $deg(f) = deg(g)$ with $deg(f)$ even:\\
 96      $f$'s canonical form leading terms $ax^d$\\
 97      $g$'s canonical form leading terms $bx^d$\\
 98      $a,b \in \Bbbk^\times,~ d=\frac{deg(f)}{2}$, set $r(0)=\frac{a}{b}$
 99    \item if $deg(f) = deg(g)$ with $deg(f)$ odd\\
100      $f$'s canonical form leading terms $ax^d$\\
101      $g$'s canonical form leading terms $bx^d$\\
102      $a,b \in \Bbbk^\times,~ deg(f)=deg(g)=3+2d$, set $r(0)=\frac{a}{b}$
103  \end{enumerate}
104\end{definition}
105
106\subsection{Zeros, poles, uniformizers and multiplicities}
107
108$r \in \Bbbk(E)$ has a \emph{zero} in $P\in E$ if $r(P)=0$\\
109$r \in \Bbbk(E)$ has a \emph{pole} in $P\in E$ if $r(P)$ is not finite.
110
111\paragraph{uniformizer:} Let $P\in E$,
112uniformizer: rational function $u \in \Bbbk(E)$ with $u(P)=0$ if
113$\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.
114$$r=u^d \cdot s$$
115
116\paragraph{order:} Let $P \in E(\Bbbk)$, let $u \in \Bbbk(E)$ be a uniformizer at $P$.
117For $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$).
118
119\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.
120
121if $P \in E(\Bbbk)$ is neither a zero or pole of $r$, then $ord_P(r)=0$ ($=d,~ r=u^0s$).
122
123\vspace{0.5cm}
124\begin{minipage}{4.3 in}
125    \paragraph{Multiplicities, from the book "Elliptic Tales"} (p.69), to provide intuition
126
127    Factorization into \emph{linear factors}: $p(x)=c\cdot (x-a_1) \cdots (x-a_d)$\\
128    $d$: degree of $p(x)$, $a_i \in \Bbbk$\\
129    Solutions to $p(x)=0$ are $x=a_1, \ldots, a_d$ (some $a_i$ can be repeated)\\
130    eg.: $p(x)=(x-1)(x-1)(x-3)$, solutions to $p(x)=0:~ 1, 1, 3$\\
131    $x=1$ is a solution to $p(x)=0$ of \emph{multiplicity} 2.
132
133    The total number of solutions (counted with multiplicity) is $d$, the degree of the polynomial whose roots we are finding.
134\end{minipage}
135
136
137\section{Divisors}
138
139\begin{definition}{Divisor}
140  $$D= \sum_{P \in E(\Bbbk)} n_p \cdot [P]$$
141\end{definition}
142
143\begin{definition}{Degree \& Sum}
144  $$deg(D)= \sum_{P \in E(\Bbbk)} n_p$$
145  $$sum(D)= \sum_{P \in E(\Bbbk)} n_p \cdot P$$
146\end{definition}
147
148
149The 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]$,
150$$D+D' = \sum_{P\in E(\Bbbk)} (n_P + m_P)[P]$$
151
152\begin{definition}{Associated divisor}
153  $$div(r) = \sum_{P \in E(\Bbbk)} ord_P(r)[P]$$
154\end{definition}
155
156Observe that
157\begin{enumerate}
158  \item[] $div(rs) = div(r)+div(s)$
159  \item[] $div(\frac{r}{s}) = div(r)-div(s)$
160\end{enumerate}
161
162Observe that
163$$\sum_{P \in E(\Bbbk)} ord_P(r) \cdot P = 0$$
164
165\begin{definition}{Support of a divisor}
166  $$\sum_P n_P[P], ~\forall P \in E(\Bbbk) ~\text{s.t.}~ n_P \neq 0$$
167\end{definition}
168
169\begin{definition}{Principal divisor}
170  iff
171  $$deg(D)=0$$
172  $$sum(D)=0$$
173\end{definition}
174$D \sim D'$ iff $D - D'$ is principal.
175
176
177\begin{definition}{Evaluation of a rational function} (function $r$ evaluated at $D$)
178  $$r(D)= \prod r(P)^{n_p}$$
179\end{definition}
180
181\section{Weil reciprocity}
182\begin{theorem}{(Weil reciprocity)}
183  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
184$$r(div(s)) = s(div(r))$$
185\end{theorem}
186Proof. (todo)
187
188\paragraph{Example}
189\begin{align*}
190  p(x)=x^2 - 1,&~ q(x)=\frac{x}{x-2}\\
191  div(p)&= 1 \cdot [1] + 1 \cdot [-1] - 2 \cdot [\infty]\\
192  div(q)&= 1 \cdot [0] - 1 \cdot [2]\\
193	&\text{(they have disjoint support)}\\
194  p(div(q)) &= p(0)^1 \cdot p(2)^{-1}= (0^2 - 1)^1 \cdot (2^2 - 1)^{-1} = \frac{-1}{3}\\
195  q(div(p)) &= q(1)^1 \cdot q(-1)^1 - q(\infty)^2\\
196	    &= (\frac{1}{1-2})^1 \cdot (\frac{-1}{-1-2})^1 \cdot (\frac{\infty}{\infty - 2})^2 = \frac{-1}{3}
197\end{align*}
198
199so, $p(div(q))=q(div(p))$.
200
201\section{Generic Weil Pairing}
202Let $E(\Bbbk)$, with $\Bbbk$ of char $p$, $n$ s.t. $p \nmid n$.
203
204$\Bbbk$ large enough: $E(\Bbbk)[n] = E(\overline{\Bbbk}) = \mathbb{Z}_n \oplus \mathbb{Z}_n$ (with $n^2$ elements).
205
206For $P, Q \in E[n]$,
207\begin{align*}
208  D_P &\sim [P] - [0]\\
209  D_Q &\sim [Q] - [0]
210\end{align*}
211
212We need them to have disjoint support:
213\begin{align*}
214  D_P &\sim [P] - [0]\\
215  D_Q' &\sim [Q+T] - [T]
216\end{align*}
217
218$$\Delta D = D_Q - D_Q' = [Q] - [0] - [Q+T] + [T]$$
219
220
221Note that $n D_P$ and $n D_Q$ are principal. Proof:
222\begin{align*}
223  n D_P &= n [P] - n [O]\\
224  deg(n D_P) &= n - n = 0\\
225  sum(n D_P) &= nP - nO = 0
226\end{align*}
227($nP = 0$ bcs. $P$ is n-torsion)
228
229Since $n D_P,~ n D_Q$ are principal, we know that $f_P,~ f_Q$ exist.
230
231Take
232\begin{align*}
233  f_P &: div(f_P) = n D_P\\
234  f_Q &: div(f_Q) = n D_Q
235\end{align*}
236
237We define
238$$
239e_n(P, Q) = \frac{f_P(D_Q)}{f_Q(D_P)}
240$$
241
242Remind: evaluation of a rational function over a divisor $D$:
243\begin{align*}
244  D &= \sum n_P [P]\\
245  r(D) &= \prod r(P)^{n_P}
246\end{align*}
247
248If $D_P = [P+S] - [S],~~ D_Q=[Q-T]-[T]$ what is $e_n(P, Q)$?
249
250\begin{align*}
251  f_P(D_Q) &= f_P(Q+T)^1 \cdot f_P(T)^{-1}\\
252  f_Q(D_P) &= f_Q(P+S)^1 \cdot f_Q(S)^{-1}
253\end{align*}
254
255$$
256e_n(P, Q) = \frac{f_P(Q+T)}{f_P(T)} / \frac{f_Q(P+S)}{f_Q(S)}
257$$
258
259with $S \neq \{O, P, -Q, P-Q \}$.
260
261
262\section{Properties}
263\begin{enumerate}[i.]
264  \item $e_n(P, Q)^n = 1 ~\forall P,Q \in E[n]$\\
265    ($\Rightarrow~ e_n(P,Q)$ is a $n^{th}$ root of unity)
266  \item Bilinearity
267    $$e_n(P_1+P_2, Q) = e_n(P_1, Q) \cdot e_n(P_2, Q)$$
268    $$e_n(P, Q_1+Q_2) = e_n(P, Q_1) \cdot e_n(P, Q_2)$$
269    \emph{proof:}
270    recall that $e_n(P,Q)=\frac{g(S+P)}{g(S)}$, then,
271    \begin{align*}
272      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)}\\
273				    &\text{(replace $S$ by $S+P_1$)}\\
274				    &= \frac{g(P_2 + P_1 + S)}{g(S)} = e_n(P_1+P_2, Q)
275    \end{align*}
276  \item Alternating
277    $$e_n(P, P)=1 ~\forall P\in E[n]$$
278  \item Nondegenerate
279    $$\text{if}~ e_n(P,Q)=1 ~\forall Q\in E[n],~ \text{then}~ P=0$$
280\end{enumerate}
281
282
283\section{Exercises}
284\emph{An Introduction to Mathematical Cryptography, 2nd Edition} - Section 6.8. Bilinear pairings on elliptic curves
285
286\begin{solution}{6.29}
287  $div(R(x) \cdot S(x)) = div( R(x)) + div( S(x))$, where $R(x), S(x)$ are rational functions.
288  \\proof:\\
289  \emph{Norm} of $f$: $N_f = f \cdot \overline{f}$, and we know that $N_{fg} = N_f \cdot N_g~\forall~\Bbbk[E]$,\\
290  then $$deg(f) = deg_x(N_f)$$\\
291  and $$deg(f \cdot g) = deg(f) + deg(g)$$
292
293  Proof:
294  $$deg(f \cdot g) = deg_x(N_{fg}) = deg_x(N_f \cdot N_g)$$
295  $$= deg_x(N_f) + deg_x(N_g) = deg(f) + deg(g)$$
296
297  So, $\forall P \in E(\Bbbk),~ ord_P(rs) = ord_P(r) + ord_P(s)$.\\
298  As $div(r) = \sum_{P\in E(\Bbbk)} ord_P(r)[P]$, $div(s) = \sum ord_P(s)[P]$.
299
300  So,
301  $$div(rs) = \sum ord_P(rs)[P]$$
302  $$= \sum ord_P(r)[P] + \sum ord_P(s)[P] = div(r) + div(s)$$
303\end{solution}
304
305\vspace{0.5cm}
306
307\begin{solution}{6.31}
308  $$e_m(P, Q) = e_m(Q, P)^{-1} \forall P, Q \in E[m]$$
309  Proof:
310  We know that $e_m(P, P) = 1$, so:
311  $$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)$$
312
313  and we know that $e_m(P, P) = 1$, then we have:
314  $$1 = e_m(P, Q) \cdot e_m(Q, P)$$
315  $$\Longrightarrow e_m(P, Q) = e_m(Q, P)^{-1}$$
316\end{solution}
317
318
319
320
321\end{document}