| Definition [Pairing] Let $r$ be a prime number and $\mathbb{G}_1$ and $\mathbb{G}_T$ be cyclic groups of order $r$. Let $\mathbb{G}_2$ [not necessary cyclic] in which every element has order $r$. Then a pairing is the map \begin{equation} e: \mathbb{G}_1 \times \mathbb{G}_2 \rightarrow \mathbb{G}_T \end{equation} and which has the properties ($\mathsf{e}$ is the neutral element in the group):
|
Is there an easy example for a pairing. Yes - the usual exponentiation in $\mathbb{Z}^*_r$ for a prime number $r$ is a pairing. Thus most of the usual cryptographic assumptions can be expressed as a pairing problem. E.g.:
Set $\mathbb{G}_1 = \mathbb{G}_T = \mathbb{Z}^*_r$ and $\mathbb{G}_2 = \mathbb{Z}^+_{r-1}$. Then the Discrete Logarithm Assumption is equal to: Given $g \in \mathbb{G}_1$ and $c \in \mathbb{G}_T$ find $a \in \mathbb{G}_2$ such that $e(g,a) = c$.
To show that exponentiation is indeed a pairing observe that:
- $e(g,a) = g^a = 1$ for all $a \in \mathbb{Z}^+_{r-1}$, hence $g = 1 = \mathsf{e}_{\mathbb{Z}^*_r}$.
- $e(g,a) = g^a = 1$ for all $g \in \mathbb{Z}^*_{r}$, hence $a = 0 = \mathsf{e}_{\mathbb{Z}^+_{r-1}}$.
- $e(g_1^{e_1},a^{e_2})\;\hat{=}\;e(g_1^{e_1},e_2a) = g^{e_1e_2a} = e(g_1,a)^{e_1e_2}$
Pairings are mostly used in context with elliptic curves. One could ask the question: What are they good for?
Answer 1). Cryptanalysis. The discrete logarithm problem could be solved faster in finite multiplicative groups $\mathbb{F}^*_{q^k}$ than on elliptic curves. See for example the MOV-Attack.
Answer 2). To build new types of cryptosystems. Pairing-based cryptography became a big push when Boneh and Franklin [2] managed to build the first provable secure identity-based cryptography scheme using the Weil-Pairing.
Pairings that have been suggested to be used together with elliptic curve cryptography are for example the Weil Pairing and the Tate Pairing. Before i come to this, it is a good idea to make sure that you know the concept of a divisor in context of elliptic curves.
Divisors. A rational function $f$ can be described uniquely (up to a constant) by its zeros and its poles together with its multiplicities. Because if you know all the zeros $\alpha_i$ of $f$ with multiplicities $a_i$, then you can write $f$ as $f = \prod (x-\alpha_i)^{a_i}$. And if you consider the function $f$ to be a quotient $f = g/h$, then the zeros of $f$ are the zeros of $g$ and the poles of $f$ are the zeros of $h$. The usual notation to write down the poles and zeros of a function $f$ is
\begin{equation}
\mathsf{div}(f) = \sum a_i\langle\alpha_i\rangle
\end{equation}
A pole is a zero with negative multiplicity. If you have another function $f' = \prod (x-\beta_i)^{b_i}$ and if you multiply these functions together $ff' = \prod(x-\alpha_i)^{a_i}\prod (x-\beta_i)^{b_i}$ the poles and zeros add together. Hence
\begin{equation}
\mathsf{div}(ff') = \sum a_i\langle\alpha_i\rangle + \sum b_i\langle\beta_i\rangle = \mathsf{div}(f) + \mathsf{div}(f')
\end{equation}
If we want to do the same with a function that is defined over the points an a elliptic curve, we do only keep track of those zeros and poles that are valid points an that curve.
Again: If we want to determine the divisors of a function $f(X,Y)$ regarding a elliptic curve $E: Y^2 = X^3+aX+b$, than these are all the points that are simultaneously:
- (X,Y) is a zero of $f$, i.e., $f(X,Y) = 0$ and $(X,Y)$ is a point on $E$.
- (X,Y) is a pole of $f$, i.e., $f(X,Y) = \infty$ and $(X,Y)$ is a point on $E$.
\begin{equation}
\mathsf{div}(f) = 2(0,1) + 2(0,-1) = 2\langle P_1\rangle + 2\langle P_2\rangle
\end{equation}
Next, we have to look at the poles of $f$. Whenever $Y = 0$, we observe a pole. But again, not all points $(*,0)$ are on $E$. If we set in $Y=0$, then we are left with $0 = X^3 + 1 \Leftrightarrow X^3 \equiv -1\pmod{13}$. Since $3|\varphi(13) = 12$, we have $3$ possible solutions $P_3,P_4,P_5$, that are $X = -1,-3,4$. Hence we add to the divisors:
\begin{align*}
\mathsf{div}(f) & = 2(0,1) + 2(0,-1) - (-1,0) - (-3,0) - (4,0) \\
& = 2\langle P_1\rangle + 2\langle P_2\rangle - \langle P_3\rangle - \langle P_4\rangle - \langle P_5\rangle
\end{align*}
Likewise we could express the function $f$ via the product $\prod (x-\alpha_i)^{a_i}$ we could express the function $f(X,Y)$ via combination of the roots $(X,Y)$ represented as the line $aX+bY+c$.
If a function $f$ is applied to a divisor $D = \sum a_i\langle P_i\rangle$, i.e., $f(D)$, then this is equal to $$f(D) = \prod f(P_i)^{a_i}$$
Torsion Points. If you have an elliptic curve with elements of finite order $P$, than for each those elements there is a factor $m$ such that $mP$ is equal to the point of infinity. So the set of $m$-torsion points is $$E[\mathbb{F}_{q^k}][r] = \{P \in E[\mathbb{F}_{q^k}] | mP = O]$$
The integer $k$ such that $E[\mathbb{F}_{q}][r] \subseteq E[\mathbb{F}_{q^k}][r]$ is called the embedding degree. There exists an integer $k$ such that $E[\mathbb{F}_{q^k}]=r^2$. And it can be proved, that even larger values for $k$ do not increase this number. At least for the integer $k$, such that $r|q^k-1$, the size of the set $E[\mathbb{F}_{q^k}][r]$ is maximal, i.e., equal to $r^2$.
For an arbitrary ellitiptic curve, the embedding degree is expected to be large, which was proven by a theorem from Balasubramanian and Koblitz [3] (otherwise elliptic curve dl has subexponential runtime). This can be seen since $$r|q^k-1 \Leftrightarrow q^k \equiv 1\pmod{r}$$, hence $k$ is the order of $q$ in $\mathbb{Z}^*_r$ and this is know to be large on the average for large integers $r$.
The Weil Pairing. I will define the Weil Pairing here in context of the finite field $\mathbb{F}_q$ for a prime number $p$, as it is the most utilized case in cryptography. Let $E[\mathbb{F}_q][r]$ be the set of $r$-torsion points over $\mathbb{F}_p$. And let $k$ be the embedding degree. I.e., it holds that $E[\mathbb{F}_q][r] \subseteq E[\mathbb{F}_{q^k}][r]$. Note: It is possible to generate curves with a small embedding degree. We set $$\mathbb{G}_1 = E[\mathbb{F}_{q}][r]; \mathbb{G}_2 = E[\mathbb{F}_{q^k}][r]; \mathbb{G}_T = \mathbb{F}_{q^k}$$ Next, we have to define the function $e(P,Q): \mathbb{G}_1 \times \mathbb{G}_2 \rightarrow \mathbb{G}_T$. In particular, the map actually maps to the subgroup of $r$-th residues of unity in $\mathbb{F}^*_{q^k}$.
Then pick $P \in E[\mathbb{F}_q][r], Q \in E[\mathbb{F}_{q^k}][r]$ and any $R,S \in \mathbb{F}^*_{q^k}$. Let $f_Q$ be the rational function with the divisor $$\mathsf{div}(f_Q) = r\langle Q+R\rangle - r\langle R\rangle$$ and $f_P$ the rational function with the divisor $$\mathsf{div}(f_P) = r\langle P+S\rangle - r\langle S\rangle$$
Then the Weil Pairing is the function $e(P,Q)$ defined as
\begin{equation}
e(P,Q) = \frac{f_P(Q+S)}{f_P(S)}\frac{f_Q(P+R)}{f_Q(R)}
\end{equation}
It holds $e(P^a,Q^b)\;\hat{=}\;e(aP,bQ) = e(P,Q)^{ab}$, which is equivalent to the statement:
\begin{align}
&1.\;e(P_1+P_2,Q) = e(P_1,Q)e(P_2,Q)\\
&2.\;e(P,Q_1+Q_2) = e(P,Q_1)e(P,Q_2)\\
\end{align}
A corresponding proof that $e(P,Q)$ is indeed a pairing according to the definition above, i will show in one of my next posts.
Cryptographic Assumptions. The Weil Pairing, or in general, the availability of an efficient computable pairing function, allows to invalidate the Decisional Diffie-Hellmann assumption on elliptic curves. The reason is, that given $g,g^a,g^b,g^z$, then $z=xy$ if and only if $$e(g,g^z) = e(g^x,g^y)$$ However, one could repair this deficit by the definition of the Decisional Bilinear Diffie-Hellman assumption, i.e., given $g,g^x,g^y,g^z,e(g,g)^w$, decide if $w=xyz$.
[1] Ben Lynn, Dissertation - On the Implementation of Pairing-Based Cryptography, http://crypto.stanford.edu/pbc/thesis.pdf
[2] Dan Boneh, Matthew K. Franklin, Identity-Based Encryption from the Weil Pairing Advances in Cryptology - Proceedings of CRYPTO 2001 (2001)
[3] R. Balasubramanian and N. Koblitz. The improbability than an elliptic curve has subexponential discrete log problem under theMenezes-Okamoto-Vanstone algorithm. Journal of Cryptology, 11 (2):141–145, 1998.
No comments:
Post a Comment