De Bruijn Sequences and the Discrete Logarithm Problem

This blog post is about De Bruijn sequences and its relationship to cryptography. We focus here on De Bruijn sequences over the alphabet $A=\{0,1\}$.

Definition [De Bruijn sequence (binary)]. A binary string of length $2^n$ is called a De Bruijn sequence of order $n$ if each possible $n$-bit string occurs exactly once (incl. wrap-around) as a substring. 

Picture 1 - DeBruijn graph for n=3

De Bruijn sequences are the shortest possible bitstring that contains all possible $n$-bit substrings. For each $n$ there are $$\frac{2^{2^{n-1}}}{2^n}$$ possible De Bruijn sequences. For example, a De Bruijn sequence of order $n=3$ is $$00011101$$ and of order $n=4$ is $$0000101100111101$$ There are several ways to create De Bruijn sequences. One way is walk along an Hamiltonian Cycle in the corresponding De Bruijn graph (see Picture 1). A De Bruijn graph is a directed graph of degree $2$ which has $2^n$ vertices. There is an edge from vertex $i$ to the two vertices $$(2i\;\text{mod}\:2^{n-1})\;\text{and}\;(2i\;\text{mod}\;2^{n-1})+1$$ The example sequence above for $n=3$ can be obtained by visiting the vertices in the graph from Picture 1 in the following order: $0,1,3,7,6,5,2,4,(0)$. Another way to create De Bruijn sequences is to use a Linear Feedback Shift Register (LFSR), loaded with a primitive polynomial of degree $n$ to create a $m$-sequence. $m$-sequences are De Bruijn sequences that miss the substring $0_n$, i.e., the substring that consists of $n$ zeros (sometimes also called a punctured De Bruijn sequence). There is also a relationship between discrete logarithms in GF$(2^n)$ and $m$-sequences which however is not the relationship i want to cover here. A good point to start reading about this topic is the book Algebraic Shift Registers Sequences from Goresky and Klapper [1].

Dlogs and Factoring with polynomial number of arithmetic steps

❚ This post is related to a paper of mine, that will get published around the end of October this year in the Journal of Groups, Complexity and Cryptography (GCC). Some people may think, when they read the headline of this post, this must be a post about Shor's quantum factoring/dlog algorithm, because it is well known that dlogs and factoring can not be solved in polynomial number of arithmetic steps otherwise.

 But this is not true.

This sounds very unintuitive, because in cryptography we nearly always work with finite fields, where the bit length is restricted by the size of the modulus and the complexity of an algorithm is hence often measured as the number of arithmetic steps.

But of course you can do this, if you increase the available space. It is not obvious how to do it, but Adi Shamir [1] already showed in 1979 how this could be done, it you allow integers in memory/registers that are of exponential size.

Discrete logarithms with auxiliary input

Auxiliary Input helps

The discrete logarithm problem with auxiliary input is defined as the problem to compute the integer $e$ given the input $(g,g^e = r,\mathcal{G})$, whereof $\mathcal{G}$ is an abelian group and $g$ is of prime order $p$ if one knows the additional input $$\left(g^{e^2},g^{e^3},...,g^{e^d}\right) \in \mathcal{G}^d$$ In [1] Jung Hee Cheon presents an algorithm which solves the problem in $\mathcal{O}(\sqrt{p/d} + \sqrt{d})$ using $$\mathcal{O}\left(\max\left(\sqrt{(p-1)/d},\sqrt{d}\right)\right)$$ space if $d | (p-1)$. The algorithm works even if the input is reduced to $(g,g^e=r,\mathcal{G},g^{e^d},d)$ only.

If $p|(p+1)$ he shows how to solve the problem given the full input in $\mathcal{O}\left(\sqrt{p/d} + d\right)$ using the same amount of space as in the case $p|(p-1)$.

Estimating discrete logarithms via sum of group elements

The discrete logarithm problem is one of the cornerstones of modern asymmetric cryptography. Several algorithms exist and each approaches the problem in different ways. For example, the Pohlig-Hellman algorithm exploits smooth group orders, the index calculus algorithm uses a small set of known discrete logarithms in order to combine them to solve the problem in question and Pollards Rho-Algorithms makes use of the birthday paradox.

I am not aware of any approach that makes use of the fact, that the residues $r_i$ in the group $\mathcal{G} \subseteq \mathbb{F}_p$ generated by the element $g$ are often nearly equal distributed. Ok, this is not always true and there are some deep and highly non-trivial theorems about the distribution of these group elements. But for our purposes we can assume that the average size of a group element is $(p-1)/2$. That means, if we assume that $g$ is a primitive root, hence $\mathcal{G} = \mathbb{F}^*_p$, and $r_i \equiv g^i\pmod{p}$ it holds: $$ \sum^e_{i=1} r_i \approx e\cdot \frac{p-1}{2} $$ And since $e < p$ it in particular holds $$ S := \sum^e_{i=1} r_i = e\cdot \frac{p-1}{2} + \mathcal{O}(p^{1/2}) < p^2 $$ So if we can compute $S$ we get a very good approximation of $e$ since $$ \frac{2\cdot S}{p-1} = e + \mathcal{O}(1) $$

Elliptic Curves with trace t = 1 [Practice]

So here comes the practical aspect of the previous post about elliptic curves with trace $1$.

I use SAGE for practical demonstration. You can use the online notebook functionality of it, e.g., under sagenb.org or nt.sagenb.org.

I use the curve $y^2 = x^3 + x + 4$, which has $19$ points over $\mathbb{F}_{19}$ and hence has trace equal to one.

--- Input
p = 19;
K = GF(19);
E = EllipticCurve(K,[1,4]); #y^2 = x^3 + x + 4
print "E is: ",E;
print "#E[K] = ",E.count_points();  
--- Output
E is:  Elliptic Curve defined by y^2 = x^3 + x + 4 over Finite Field of size 19
#E[GF(19)] =  19

Elliptic Curves with trace t = 1 [Theory]

In this post, i will show the proof that one could efficiently compute the discrete logarithm on a curve $E[\mathbb{F}_p]$ if the number of points on that curve is equal to $p$. Such a curve is called anomalous. Since $$\#E[\mathbb{F}_p] = p+1-t$$ this is again equal to the statement that the trace $t$ of the curve is equal to $1$. The proof was given by Nigel Smart [1], Satoh and Araki [2], or Semaev [3] independently roughly at the same time ($\sim$ 1999).

Remark: The attack is somehow similar to the described lift in that post, which executes the lift $\mathbb{Z}/p\mathbb{Z} \rightarrow \mathbb{Z}/p^2\mathbb{Z}$, and that solves the dlp in the subgroup of order $p$ in $\mathbb{Z}/p^2\mathbb{Z}$.

An explicit formula for the discrete logarithm

I guess, but i am not sure, many people don't know that there is an explicit formula for the discrete logarithm in finite fields $\mathbb{F}^*_p$. I remember that i was quite surprised when i learned the formula many years ago.

Theorem [Explicit DL Formula] Let $p$ be a prime number $>2$ and $g$ be a primitive root in $\mathbb{F}^*_p$. Then the discrete logarithm of the element $a \in \mathbb{F}^*_p$ is equal to \begin{equation} \mathsf{dlog}_{p,g}(a) = \sum^{p-2}_{k=1} \frac{a^k}{1-g^k}\pmod{p}\end{equation}

The proof is actually not that complicated and can be found in Niederreiter [1]. I will give here a new proof for you:

[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)}$.