In this post I want to talk about a thing from the Kryptos universe that are not directly related to the statue. But i think it may be an indirect hint to some Kryptos related methods. The Mayan Symbols in Ed Scheidts driveway I think everyone who knows Kryptos knows Ed Scheidt. The former Chairman of the Cryptographic Center at the CIA and founder of the cryptosystems used around the Kryptos statue. As already shown in Part 4 of my Kryptos series, in the driveway of Ed Scheidts house, there are two symbols: Figure 1 - Garage driveway of Ed Scheidt We denote the left symbol set with $S_1$ and the right one with $S_2$. It took me a while to find his house on Google Maps - Street View. To save you some time, here is the link with a view on the driveway. I you go back in time in Streetview, you can see that the symbols were already there in 2012. But it is impossible to say when they were built. $S_1$ is clearly visible from the street, $S_2$ is hidden in the view. But you can u...
This post contains some basic facts about Pairing-based Cryptography. I write this post mainly for the reason to have a easy to find reference for myself and to recall some definitions. For readers that are more interested in pairings in context of cryptography, a good further reading source is the dissertation of Lynn [1], wherefrom i also adopted the usage of the multiplicative notation as a shortcut to represent $$\underbrace{a\circ a\circ ... \circ a}_{n\;times} = a^n$$ if $\circ$ is the group operation of $\mathbb{G}$ and $a \in \mathbb{G}$.
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:
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:
\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.
| 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.
Comments
Post a Comment