# Bilinear pairing
This note just focuses on properties of bilinear paring, if you want to study more, read the references
The definition below is given for free modules over a ring.
## Definition
The definition below is given for free modules over a ring.
Let $M_1, M_2$ be free modules over a commutative ring $R$. A bilinear form is a mapping $e : M_1 \times M_2 \to R$ such that:
- $e(aP, Q) = e(P, aQ) = a \cdot e(P, Q)$
- $e(P + P', Q) = e(P, Q) + e(P', Q)$
- $e(P, Q + Q') = e(P, Q) + e(P, Q')$
## Proposition 1
Let $M$ be a $\mathbb{Z}/n\mathbb{Z}$ module of rank 2, and let $(P, Q)$ be a pair of generators. Let $e$ be an alternating pairing on $M \times M$ taking values in a multiplicative group $G$ of order $n$, and let $\zeta = e(P, Q)$. Then

$$
e([a]P + [b]Q, [c]P + [d]Q) = \zeta^{\det \begin{pmatrix} a & b \\ c & d \end{pmatrix}}
$$
## Theorem 1
Let $E$ be an elliptic curve defined over a field $K$, let $n$ be a positive integer and let $\mu_n$ be the set of $n$-th roots of unity. Assume that $K$'s characteristic $p \nmid n$ then there exists a pairing
$$
e_n : E[n] \times E[n] \to \mu_n
$$
such that:
- $e_n(P_1 + P_2, Q) = e_n(P_1, Q)e_n(P_2, Q)$ and
$e_n(P, Q_1 + Q_2) = e_n(P, Q_1)e_n(P, Q_2)$ (bilinearity)
- If $e_n(P, Q) = 1$ for all $Q \in E[n]$ then $P = \mathcal{O}$ and
if $e_n(P, Q) = 1$ for all $P \in E[n]$ then $Q = \mathcal{O}$ (non-degeneracy)
- $e_n(P, P) = 1$ for all $P \in E[n]$ (alternating)
- $e_n(P, Q) = e_n(Q, P)^{-1}$ for all $P, Q \in E[n]$ (skew symmetry)
- $e_n(\sigma P, \sigma Q) = \sigma(e_n(P, Q))$ for all $\sigma \in \text{Gal}(\bar{K}/K)$ (Galois action)
### Remark 1
Note that given two points $P, Q \in E[n]$ where $Q = kP$, $Q$ and $P$ are linearly dependent, we have that
$$
e_n(P, Q) = 1
$$
## Theorem 2
Let $E, E'$ be elliptic curves, let $\phi : E \to E'$ be an isogeny, $\hat{\phi} : E' \to E$ its dual, let $n$ be a positive integer. For any $P \in E[n]$ and $Q \in E'[n]$
$$
e'_n(\phi(P), Q) = e_n(P, \hat{\phi}(Q)).
$$
where $e_n$ and $e'_n$ denote the Weil pairing of $E$ and $E'$ respectively.
### Corollary 1
Let $\phi : E \to E'$ be an isogeny of degree $d$. For any $n, P, Q$
$$
e'_n(\phi(P), \phi(Q)) = e_n(P, Q)^d
$$
## Example ([DLOG on the Surface](https://cryptohack.org/challenges/isogenies/))
The challenge give $P, Q$ are points of Elliptic curves $E$ order $n$; $a,b,c,d$ are integers and $R=aP+bQ$, $S=cP+dQ$, ask us to find $a,b,c,d$
- Let $e = e_n(P,Q)$
- Value $a$
- $e_n(R,Q)$
$=e_n(aP + bQ,Q)$
$=e_n(aP,Q)$ * $e_n(bQ,Q)$
$=e_n(P,Q)^a$ * $e_n(Q,Q)^b$
$=e_n(P,Q)^a$ * $1$
$=e^a$
- We can find $a$ by discrete logarithm
- Value $b$
- $e_n(R,P)$
$=e_n(aP + bQ,P)$
$=e_n(aP,P)$ * $e_n(bQ,P)$
$=e_n(P,P)^a$ * $e_n(Q,P)^b$
$=1$ * $(e_n(P,Q)^{-b})$
$=e^{-b}$
- We can find $b$ by discrete logarithm
- Value $c$
- $e_n(S,Q)$
$=e_n(cP + dQ,Q)$
$=e_n(cP,Q)$ * $e_n(dQ,Q)$
$=e_n(P,Q)^c$ * $e_n(Q,Q)^d$
$=e_n(P,Q)^c$ * $1$
$=e^c$
- We can find $c$ by discrete logarithm
- Value $d$
- $e_n(S,P)$
$=e_n(cP + dQ,P)$
$=e_n(cP,P)$ * $e_n(dQ,P)$
$=e_n(P,P)^c$ * $e_n(Q,P)^d$
$=1$ * $(e_n(P,Q)^{-d})$
$=e^{-d}$
- We can find $d$ by discrete logarithm
## References
- https://github.com/defeo/MathematicsOfIBC/blob/popayan-temp/poly.pdf
- https://www.sagemath.org/files/thesis/hansen-thesis-2009.pdf
- https://en.wikipedia.org/wiki/Pairing-based_cryptography