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
 38\maketitle
 39
 40\begin{abstract}
 41  Notes taken from \href{https://sites.google.com/site/matanprasma/artifact}{Matan Prsma} 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$.
 42
 43	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.
 44\end{abstract}
 45
 46\tableofcontents
 47
 48\section{Divisors and rational functions}
 49
 50\begin{definition}{Divisor}
 51  $$D= \sum_{P \in E(\mathbb{K})} n_p \cdot [P]$$
 52\end{definition}
 53
 54\begin{definition}{Degree \& Sum}
 55  $$deg(D)= \sum_{P \in E(\mathbb{K})} n_p$$
 56  $$sum(D)= \sum_{P \in E(\mathbb{K})} n_p \cdot P$$
 57\end{definition}
 58
 59\begin{definition}{Principal divisor}
 60  iff $deg(D)=0$ and $sum(D)=0$
 61\end{definition}
 62$D \sim D'$ iff $D - D'$ is principal.
 63
 64
 65\begin{definition}{Evaluation of a rational function}
 66  $$r(D)= \prod r(P)^{n_p}$$
 67\end{definition}
 68
 69\section{Weil reciprocity}
 70\begin{theorem}{(Weil reciprocity)}
 71  Let $E/ \mathbb{K}$ be an e.c. over an alg. closed field. If $r,~s \in \mathbb{K}\setminus \{0\}$ are rational functions whose divisors have disjoint support, then
 72$$r(div(s)) = s(div(r))$$
 73\end{theorem}
 74Proof. (todo)
 75
 76\section{Generic Weil Pairing}
 77Let $E(\mathbb{K})$, with $\mathbb{K}$ of char $p$, $n$ s.t. $p \nmid n$.
 78
 79$\mathbb{K}$ large enough: $E(\mathbb{K})[n] = E(\mathbb{\overline{K}}) = \mathbb{Z}_n \oplus \mathbb{Z}_n$ (with $n^2$ elements).
 80
 81For $P, Q \in E[n]$,
 82\begin{align*}
 83  D_P &\sim [P] - [0]\\
 84  D_Q &\sim [Q] - [0]
 85\end{align*}
 86
 87We need them to have disjoint support:
 88\begin{align*}
 89  D_P &\sim [P] - [0]\\
 90  D_Q' &\sim [Q+T] - [T]
 91\end{align*}
 92
 93$$\Delta D = D_Q - D_Q' = [Q] - [0] - [Q+T] + [T]$$
 94
 95
 96Note that $n D_P$ and $n D_Q$ are principal. Proof:
 97\begin{align*}
 98  n D_P &= n [P] - n [O]\\
 99  deg(n D_P) &= n - n = 0\\
100  sum(n D_P) &= nP - nO = 0
101\end{align*}
102($nP = 0$ bcs. $P$ is n-torsion)
103
104Since $n D_P,~ n D_Q$ are principal, we know that $f_P,~ f_Q$ exist.
105
106Take
107\begin{align*}
108  f_P &: div(f_P) = n D_P\\
109  f_Q &: div(f_Q) = n D_Q
110\end{align*}
111
112We define
113$$
114e_n(P, Q) = \frac{f_P(D_Q)}{f_Q(D_P)}
115$$
116
117Remind: evaluation of a rational function over a divisor $D$:
118\begin{align*}
119  D &= \sum n_P [P]\\
120  r(D) &= \prod r(P)^{n_P}
121\end{align*}
122
123If $D_P = [P+S] - [S],~~ D_Q=[Q-T]-[T]$ what is $e_n(P, Q)$?
124
125\begin{align*}
126  f_P(D_Q) &= f_P(Q+T)^1 \cdot f_P(T)^{-1}\\
127  f_Q(D_P) &= f_Q(P+S)^1 \cdot f_Q(S)^{-1}
128\end{align*}
129
130$$
131e_n(P, Q) = \frac{f_P(Q+T)}{f_P(T)} / \frac{f_Q(P+S)}{f_Q(S)}
132$$
133
134with $S \neq \{O, P, -Q, P-Q \}$.
135
136
137\section{Properties}
138
139
140\section{Exercises}
141\emph{An Introduction to Mathematical Cryptography, 2nd Edition} - Section 6.8. Bilinear pairings on elliptic curves
142
143\begin{solution}{6.29}
144  $div(R(x) \cdot S(x)) = div( R(x)) + div( S(x))$, where $R(x), S(x)$ are rational functions.
145  \\proof:\\
146  \emph{Norm} of $f$: $N_f = f \cdot \overline{f}$, and we know that $N_{fg} = N_f \cdot N_g~\forall~\mathbb{K}[E]$,\\
147  then $$deg(f) = deg_x(N_f)$$\\
148  and $$deg(f \cdot g) = deg(f) + deg(g)$$
149
150  Proof:
151  $$deg(f \cdot g) = deg_x(N_{fg}) = deg_x(N_f \cdot N_g)$$
152  $$= deg_x(N_f) + deg_x(N_g) = deg(f) + deg(g)$$
153
154  So, $\forall P \in E(\mathbb{K}),~ ord_P(rs) = ord_P(r) + ord_P(s)$.\\
155  As $div(r) = \sum_{P\in E(\mathbb{K})} ord_P(r)[P]$, $div(s) = \sum ord_P(s)[P]$.
156
157  So,
158  $$div(rs) = \sum ord_P(rs)[P]$$
159  $$= \sum ord_P(r)[P] + \sum ord_P(s)[P] = div(r) + div(s)$$
160\end{solution}
161
162\vspace{0.5cm}
163
164\begin{solution}{6.31}
165  $$e_m(P, Q) = e_m(Q, P)^{-1} \forall P, Q \in E[m]$$
166  Proof:
167  We know that $e_m(P, P) = 1$, so:
168  $$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)$$
169
170  and we know that $e_m(P, P) = 1$, then we have:
171  $$1 = e_m(P, Q) \cdot e_m(Q, P)$$
172  $$\Longrightarrow e_m(P, Q) = e_m(Q, P)^{-1}$$
173\end{solution}
174
175
176
177
178\end{document}