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...
[Paper Review] A new index calculus algorithm with complexity $L(1/4 + o(1))$ in small characteristic.
Scientific breakthroughs are rare events. And I can not directly judge if this is indeed a breakthrough or not, but there are people out there, which do so.
It is the paper from Antoine Joux. It introduces a new techniques for the index calculus algorithm and improves the running time to $L(1/4+o(1))$. And it is also the follow up paper by Razvan Barbulescu, Pierrick Gaudry, Antoine Joux and Emmanuel Thomé. The later improves (heuristically) the running time even to quasi-polynomial complexity, i.e., $n^{\mathcal{O}(\log n)}$.
The first improvement of Joux et al. is about phase 1) of the index calculus algorithm. He found a more efficient way to generate elements $G^r = X_r$, such that $X_r$ can be factored into small elements, i.e., elements from the factor-base.
Instead of choosing at first a factor base and then trying to find elements $X_r = G^r$, that could be factored within that factor base, Joux idea is to start with a polynomial $f$, that is already known or constructed that way, that it can be factored in many small irreducible polynomials.
He then applies Homographies to $f$, that is a change of the polynomial that preserves the property of having many irreducible factors. In particular he uses $$f(X) \rightarrow F_{abcd}(X) = (cX+d)^{\text{deg}f}f\left(\frac{aX+b}{cX+d}\right)$$ The additional term $(cX+d)^{\text{deg}f}$ is responsible to make $F_{abcd}(X)$ indeed a polynomial, i.e., not to contain fraction terms.
The polynomial $f(X)$ is defined in $\mathbb{F}_q$, whereof the elements $a,b,c,d$ are taken from $\mathbb{F}_{q^2}$. As a natural choice for $f$, i.e., a polynomial that has many factors, he chooses $$f(X) = X^q - X$$ since every element from $F_q$ is a root of that polynomial. So we can write $$f(X) = \prod_{\alpha \in \mathbb{F}_q}(X-\alpha) = X^q - X$$ Now the homographie $X \rightarrow \frac{aX+b}{cX+d}, ad-bc \neq 0$ is applied, as well as multiplied with $(cX+d)^{q+1})$:
\begin{align*}
(1)\;\;(cX+d)^{q+1}\prod_{\alpha \in \mathbb{F}_q}\left(\frac{aX+b}{cX+d}-\alpha\right) = (cX+d)^{q+1}\left(\left(\frac{aX+b}{cX+d}\right)^q - \frac{aX+b}{cX+d}\right)
\end{align*}
The LHS of (1) can be simplified to
\begin{align*}
(cX+d)^{q+1}\prod_{\alpha \in \mathbb{F}_q}\left(\frac{aX+b}{cX+d}-\alpha\right) & = (cX+d)^{q+1}\prod_{\alpha \in \mathbb{F}_q}\left(\frac{aX+b - \alpha cX - \alpha d}{cX+d}\right) \\
& = (cX+d)\prod_{\alpha \in \mathbb{F}_q}((a- \alpha c)X + (b - \alpha d))
\end{align*}
The RHS of (1) can be simplified to (using the fact that $(x+y)^q = x^q + y^q$)
\begin{align*}
& (cX+d)^{q+1}\left(\left(\frac{aX+b}{cX+d}\right)^q - \frac{aX+b}{cX+d}\right) = (cX+d)(aX+b)^q - (cX+d)^q(aX+b) \\
& = ca^qX^{q+1}+cb^qX + da^qX^q + db^q - c^qaX^{q+1}-c^qbX^q - d^qaX-d^qb\\
& = (ca^q-c^qa)X^{q+1} + (da^q-d^qa)X^q + (cb^q-c^qb)X + (db^q -d^qb)\\
\end{align*}
Next, two polynomials $h_0(X)$ and $h_1(X)$ are chosen, that have at most degree 2. Furthermore, they have the property $$X^q = \frac{h_0(X)}{h_1(X)}$$
as well as $$h_1(X)X^q - h_0(X)$$ as an irreducible factor $I(X)$ of degree $n$ (therewith it creates $\mathbb{F}_{q^n}$). Then the RHS could further be rewritten as
\begin{align*}
& = (ca^q-c^qa)X\frac{h_0(X)}{h_1(X)} + (da^q-d^qa)\frac{h_0(X)}{h_1(X)}\\
&+ (cb^q-c^qb)X\frac{h_1(X)}{h_1(X)} + (db^q -d^qb)\frac{h_1(X)}{h_1(X)}\pmod{I(X)}
\end{align*} So in total we have the equation
\begin{align*}
& (cX+d)\prod_{\alpha \in \mathbb{F}_q}((a- \alpha c)X + (b - \alpha d)) \\
& = \\
& (ca^q-c^qa)X\frac{h_0(X)}{h_1(X)} + (da^q-d^qa)\frac{h_0(X)}{h_1(X)}\\
&+ (cb^q-c^qb)X\frac{h_1(X)}{h_1(X)} + (db^q -d^qb)\frac{h_1(X)}{h_1(X)}\pmod{I(X)}
\end{align*}
That is a relation between a product of linear polynomials on the left side and a fraction with low-degree numerator and constant denominator (consider $h_1(X)$ as an element of the factor base).
It can be proven that there exists $q^3+q$ different equations for random chosen values of $(a,b,c,d)$. Since $\mathcal{O}(q^2)$ quadruples (a,b,c,d) are sufficient, there are enough possibilities to choose from in order to get sufficient systems of relations.
However, Joux argues that linear polynomials are not sufficient to solve all discrete logarithms. He repeats his idea with another Homographie to get quadratic polynomials by $$X \rightarrow \frac{aX^2+bC+c}{dX^2+eX+f}$$.
So by simply picking random values for $(a,b,c,d)$ one gets enough relations and indeed one could compute the discrete logarithms for all the elements from the factor base in polynomial time (actually due to the small base field).
His second improvement is about phase 3) of the index calculus algorithm. In the so called Descent Phase (or individual logarithm phase). And this is the point where, as far as i understood the algorithms, the original paper and the follow up paper with its quasi-polynomial runtime diverge.
The goal of the Descent Phase is to express a multiplicative of the residue in question, say $g^iZ$ for some $i$, as a linear combination of the factors from the factor base. The strategy is to first find a suitable representation of $Z$ with polynomial of low-degree. Then one tries to find recursively a representation of these polynomials of even lower degree until one ends with polynomials from the factor base.
So if $p(Z)$ is the polynomial that expresses $Z$, then we have to find a polynomial $t$ that expresses $g^iZ$. So the polynomial $t$ must
It is the paper from Antoine Joux. It introduces a new techniques for the index calculus algorithm and improves the running time to $L(1/4+o(1))$. And it is also the follow up paper by Razvan Barbulescu, Pierrick Gaudry, Antoine Joux and Emmanuel Thomé. The later improves (heuristically) the running time even to quasi-polynomial complexity, i.e., $n^{\mathcal{O}(\log n)}$.
# The Idea of the Index Calculus Algorithm #
The idea of the index calculus algorithm is, in order to find the discrete logarithm of the group element $X$ to the base $G$, to- build a factor-base of size $s$. That is, a set of small integers or low degree polynomials. Then random group elements $X_r$ are generated via $G^r = X_r$ (hence their logarithm is known). Then these $X_r$ elements are tried to be factored completely within the factor base only. (Hence the $X_r$ have a smooth factorization).
- If $s$ independent elements are found, that are successfully factored within the factor base, $s$ equations can be build:
\begin{align*}
G^{r_1} & = b_1^{e_{1,1}}b_2^{e_{1,2}}...b_s^{e_{1,s}}\\
G^{r_2} & = b_1^{e_{2,1}}b_2^{e_{2,2}}...b_s^{e_{2,s}}\\
... &\\
G^{r_s} & = b_1^{e_{s,1}}b_2^{e_{s,2}}...b_s^{e_{s,s}}
\end{align*}
Writing this in terms of logarithms to the base $G$, we get $s$ equations and $s$ unknown
\begin{align*}
r_1 & = e_{1,1}\log_G b_1 + e_{1,2}\log_G b_2 + ... + e_{1,s}\log_G \\
r_2 & = e_{2,1}\log_G b_1 + e_{2,2}\log_G b_2 + ... + e_{2,s}\log_G \\
... &\\
r_s & = e_{s,1}\log_G b_1 + e_{s,2}\log_G b_2 + ... + e_{s,s}\log_G \\
\end{align*}
which can be solved for the $s$ unknowns $\log_G b_i$. So, one gets the discrete logarithm for each element from the factor base. - Pick a random integer $h$ and compute $g^hX$ until this could be factored completely within the factor-base $$g^hX = b_1^{f_1}b_2^{f_2}...b_s^{f_2}$$ the algorithm succeeded and returns the logarithm of $X$ by
\begin{align*}
\log_G X = f_1\log_G b_1 + f_2\log_G b_2 + ... + f_s\log_G b_s - h
\end{align*}
# Improvements #
I will not cover all details here, but i want to describe what are the main reasons for the improvement.
The first improvement of Joux et al. is about phase 1) of the index calculus algorithm. He found a more efficient way to generate elements $G^r = X_r$, such that $X_r$ can be factored into small elements, i.e., elements from the factor-base.
Instead of choosing at first a factor base and then trying to find elements $X_r = G^r$, that could be factored within that factor base, Joux idea is to start with a polynomial $f$, that is already known or constructed that way, that it can be factored in many small irreducible polynomials.
He then applies Homographies to $f$, that is a change of the polynomial that preserves the property of having many irreducible factors. In particular he uses $$f(X) \rightarrow F_{abcd}(X) = (cX+d)^{\text{deg}f}f\left(\frac{aX+b}{cX+d}\right)$$ The additional term $(cX+d)^{\text{deg}f}$ is responsible to make $F_{abcd}(X)$ indeed a polynomial, i.e., not to contain fraction terms.
The polynomial $f(X)$ is defined in $\mathbb{F}_q$, whereof the elements $a,b,c,d$ are taken from $\mathbb{F}_{q^2}$. As a natural choice for $f$, i.e., a polynomial that has many factors, he chooses $$f(X) = X^q - X$$ since every element from $F_q$ is a root of that polynomial. So we can write $$f(X) = \prod_{\alpha \in \mathbb{F}_q}(X-\alpha) = X^q - X$$ Now the homographie $X \rightarrow \frac{aX+b}{cX+d}, ad-bc \neq 0$ is applied, as well as multiplied with $(cX+d)^{q+1})$:
\begin{align*}
(1)\;\;(cX+d)^{q+1}\prod_{\alpha \in \mathbb{F}_q}\left(\frac{aX+b}{cX+d}-\alpha\right) = (cX+d)^{q+1}\left(\left(\frac{aX+b}{cX+d}\right)^q - \frac{aX+b}{cX+d}\right)
\end{align*}
The LHS of (1) can be simplified to
\begin{align*}
(cX+d)^{q+1}\prod_{\alpha \in \mathbb{F}_q}\left(\frac{aX+b}{cX+d}-\alpha\right) & = (cX+d)^{q+1}\prod_{\alpha \in \mathbb{F}_q}\left(\frac{aX+b - \alpha cX - \alpha d}{cX+d}\right) \\
& = (cX+d)\prod_{\alpha \in \mathbb{F}_q}((a- \alpha c)X + (b - \alpha d))
\end{align*}
The RHS of (1) can be simplified to (using the fact that $(x+y)^q = x^q + y^q$)
\begin{align*}
& (cX+d)^{q+1}\left(\left(\frac{aX+b}{cX+d}\right)^q - \frac{aX+b}{cX+d}\right) = (cX+d)(aX+b)^q - (cX+d)^q(aX+b) \\
& = ca^qX^{q+1}+cb^qX + da^qX^q + db^q - c^qaX^{q+1}-c^qbX^q - d^qaX-d^qb\\
& = (ca^q-c^qa)X^{q+1} + (da^q-d^qa)X^q + (cb^q-c^qb)X + (db^q -d^qb)\\
\end{align*}
Next, two polynomials $h_0(X)$ and $h_1(X)$ are chosen, that have at most degree 2. Furthermore, they have the property $$X^q = \frac{h_0(X)}{h_1(X)}$$
as well as $$h_1(X)X^q - h_0(X)$$ as an irreducible factor $I(X)$ of degree $n$ (therewith it creates $\mathbb{F}_{q^n}$). Then the RHS could further be rewritten as
\begin{align*}
& = (ca^q-c^qa)X\frac{h_0(X)}{h_1(X)} + (da^q-d^qa)\frac{h_0(X)}{h_1(X)}\\
&+ (cb^q-c^qb)X\frac{h_1(X)}{h_1(X)} + (db^q -d^qb)\frac{h_1(X)}{h_1(X)}\pmod{I(X)}
\end{align*} So in total we have the equation
\begin{align*}
& (cX+d)\prod_{\alpha \in \mathbb{F}_q}((a- \alpha c)X + (b - \alpha d)) \\
& = \\
& (ca^q-c^qa)X\frac{h_0(X)}{h_1(X)} + (da^q-d^qa)\frac{h_0(X)}{h_1(X)}\\
&+ (cb^q-c^qb)X\frac{h_1(X)}{h_1(X)} + (db^q -d^qb)\frac{h_1(X)}{h_1(X)}\pmod{I(X)}
\end{align*}
That is a relation between a product of linear polynomials on the left side and a fraction with low-degree numerator and constant denominator (consider $h_1(X)$ as an element of the factor base).
It can be proven that there exists $q^3+q$ different equations for random chosen values of $(a,b,c,d)$. Since $\mathcal{O}(q^2)$ quadruples (a,b,c,d) are sufficient, there are enough possibilities to choose from in order to get sufficient systems of relations.
However, Joux argues that linear polynomials are not sufficient to solve all discrete logarithms. He repeats his idea with another Homographie to get quadratic polynomials by $$X \rightarrow \frac{aX^2+bC+c}{dX^2+eX+f}$$.
So by simply picking random values for $(a,b,c,d)$ one gets enough relations and indeed one could compute the discrete logarithms for all the elements from the factor base in polynomial time (actually due to the small base field).
His second improvement is about phase 3) of the index calculus algorithm. In the so called Descent Phase (or individual logarithm phase). And this is the point where, as far as i understood the algorithms, the original paper and the follow up paper with its quasi-polynomial runtime diverge.
The goal of the Descent Phase is to express a multiplicative of the residue in question, say $g^iZ$ for some $i$, as a linear combination of the factors from the factor base. The strategy is to first find a suitable representation of $Z$ with polynomial of low-degree. Then one tries to find recursively a representation of these polynomials of even lower degree until one ends with polynomials from the factor base.
So if $p(Z)$ is the polynomial that expresses $Z$, then we have to find a polynomial $t$ that expresses $g^iZ$. So the polynomial $t$ must
- be of lower degree
- contain $p(Z)$ as a factor
"...given an oracle to solve bilinear systems, we could use a much faster descent from degree deg ? to ? ... would then give a quasi-polynomial complexity... Moreoever, this would get rid of the use of classical descent, together with the constraint of having $q=p^l$, with $l\geq 2$."And this is what the follow up paper does in order to achieve quasi-polynomial runtime. But I guess i will cover the follow up paper in another post.
Comments
Post a Comment