From Discrete Logarithm Problem to Menelaus Theorem

This week’s post touches on subjects spanning almost 2000 years — we start with a cryptographic problem and go back in time to discover a theorem that could be known to the Greeks. Its content is based on a paper co-authored with Anton Mityagin and Kobbi Nissim that appeared in ANTS VII in 2006. The paper was motivated by a cryptographic question, previously introduced by Claus-Peter Schnorr, but the machinery that we ended up using had more to do with extremal graph theory, projective geometry, and combinatorial number theory. It fits in nicely with the overarching theme of this blog, which is interconnectedness of mathematics and CS theory, and leaves open several intriguing questions at the intersection of these areas.

I. Motivation

Consider the problem of computing the discrete logarithm in a generic group of a known prime order ${p}$ : given two random elements ${g}$ and ${h}$ , find ${x}$ so that ${h=g^x}$ . Instead of having access to the group itself, we may only manipulate encodings of its elements (basically, a random mapping of the group ${{\mathbb Z}/p{\mathbb Z}}$ to a sufficiently large alphabet) via a group oracle. The group oracle accepts encodings of two elements and returns the encoding of their product. Think of it as a model of an abstract group, where the result of multiplying two group elements is treated as a new formal variable.

Let us try solving the discrete logarithm problem in this model. Given the encodings of two elements ${g}$ and ${h}$ , one can multiply them, obtaining the encoding of ${gh}$ , square the result, etc. In general, it is possible to compute (encodings of) elements of the form ${g^{a_i} h^{b_i}}$ , where ${(a_i,b_i)}$ are pairs of integers modulo ${p}$ (all arithmetic not involving ${g}$ or ${h}$ is going to be modulo ${p}$ from now on). Of course, there can be multiple ways of arriving at the same element. For instance, ${g^2h^2 = (gh)^2}$ (as the group is of the prime order, it is necessarily Abelian). Unless we do it on purpose, all elements that we obtain from the group oracle are going to be distinct with an overwhelming probability over ${x=\log_g h}$ (assume that the group order ${p}$ is large, say, at least ${2^{80}}$ ). Indeed, if ${g^{a_i} h^{b_i} = g^{a_j} h^{b_j}}$ , then ${a_i+b_ix=a_j+b_jx},$ which happens for ${(a_i,b_i)\neq(a_j,b_j)}$ with probability at most ${1/p}$ . On the other hand, if we do get a non-trivial relationship, we can recover ${x}$ right away.

In other words, the group oracle keeps outputting some random encodings that tell us nothing useful about the elements ${g}$ and ${h}$ (we could sample encodings from the same distribution ourselves, without access to the oracle), until it returns an element that we did see before, which immediately gives away the answer to the discrete logarithm problem.

If ${x}$ is chosen uniformly at random from ${{\mathbb Z}/p{\mathbb Z}}$ , the success probability of any algorithm in the generic group model making no more than ${n}$ group operations is bounded by ${{n\choose 2}/p = O(n^2/p)}$ : each pair of elements output by the group oracle collides with probability at most ${1/p}$ , there are at most ${{n\choose 2}}$ such pairs, union bound, check and mate. A formal version of this handwavy argument is due to Victor Shoup, which gives a tight (up to a constant) bound on the success probability of any algorithm for solving the discrete logarithm problem in the generic group model.

A simple algorithm matches this bound. Let ${n = 3m}$ . Compute ${g, g^2, g^3,\dots,g^m}$ (by repeat multiplications by ${g}$ ), ${g^{2m},g^{3m},\dots,g^{m^2}}$ (by repeat multiplications by ${g^m}$ ), and using the elements already available, compute ${hg,hg^2,hg^3,\dots,hg^m}$ . If ${x\in [-m,m^2-m]}$ , there’s going to be a collision between ${g^{im}}$ and ${ hg^j=g^{x+j}}$ for some ${i}$ and ${j \leq m}$ . This algorithm is known as the baby-step giant-step method — we are making “baby ”steps when we are multiplying ${h}$ by powers of ${g}$ , and “giants” steps, when we are computing powers of ${g^m}$ . If ${m = \lceil \sqrt{p}\rceil}$ , the discrete logarithm problem is solved with probability 1.

The above argument suggests that in order to solve the discrete logarithm problem in the generic group model one would want to maximize the probability of observing a collision. Collisions have simple geometric interpretation: each time the algorithm computes ${g^{a_i}h^{b_i}}$ , it draws a line ${a_i+b_ix}$ in the ${({{\mathbb Z}/p{\mathbb Z}})^2}$ space. An element ${z}$ is “covered” if two lines intersect above this element: ${a_i+b_iz = a_j+b_jz}$ . The adversary is trying to cover as many elements as possible with the fewest number of lines.

As we just have seen, the number of group operations required to solve the discrete logarithm problem in the generic group when ${g}$ and ${h}$ are chosen uniformly at random is ${\Theta(\sqrt{p})}$ . The question becomes much more interesting if we constrain the joint distribution of ${g}$ and ${h}$ .

What is the complexity of the discrete logarithm problem measured as the number of group operations, if ${h = g^x}$ , where ${x}$ is sampled uniformly from ${S \subset {{\mathbb Z}/p{\mathbb Z}}}$ ?

It turns out that this question has been answered for some simple sets ${S}$ , but it is wide open in general.

II. Geometric Formulation

We re-formulate the problem using the language of finite field geometry.

Given a subset ${S}$ of ${{{\mathbb Z}/p{\mathbb Z}}}$ , define its DL-complexity, denoted as ${C(S)}$ , as the minimal number of lines in ${({{\mathbb Z}/p{\mathbb Z}})^2}$ whose intersection points projected to the ${x}$ -axis cover ${S}$ .

In the notation of the previous section, the adversary is drawing lines ${y=a_i+b_ix}$ . It scores a hit when two lines intersect above point ${z\in S}$ , i.e., ${a_i+b_iz=a_j+b_jz}$ . The adversary’s goal is to cover the entire set ${S}$ with the smallest number of lines, which would correspond to solving the discrete logarithm problem for the case when ${h=g^x}$ and ${x\in S}$ .

What are the most basic facts about ${C(S)}$ ?

${C(S) = O(\sqrt{p})}$ . Indeed, we know that the (generic) baby-step giant-step algorithm covers the entire ${{{\mathbb Z}/p{\mathbb Z}}}$ with ${\Theta(\sqrt{p})}$ lines.
${C(S) \leq |S| + 1}$ — duh! It suffices to draw a single line ${y = 0}$ and one line for each element of ${z\in S\colon y=x - z}$ .
${C(S) > \sqrt{|S|}}$ : if ${n = C(S)}$ lines can cover the entire ${S}$ , then the number of intersection points, which is less than ${n^2}$ , is at least ${|S|}$ .

Putting these bounds together on this schematic picture drawn in the log-log scale, we can see that ${C(S)}$ lives inside the shaded triangle.
The most intriguing part of the triangle is the upper-left corner, marked with the target sign, that corresponds to sets that are as small as ${\sqrt{p}}$ but have the property that solving the discrete logarithm problem in these subsets is as hard as in the entire ${{{\mathbb Z}/p{\mathbb Z}}}$ . How can we get there, or just get closer? But first, why do we care at all?

One, rather vague motivation is that we are interested in characterizing these subsets because they capture the complexity of the discrete logarithm problem. Another, due to Claus-Peter Schnorr, who defined the problem in 2000, is that the amount of entropy needed to sample an element of that set is half of ${\log_2 p}$ . The observation that got us going back in 2005 was that modular exponentiation takes amount of time that depends on the exponent. Wouldn’t it be nice if we could choose exponents that allowed for faster exponentiation algorithms? These exponents could cover only a fraction of the entire space, which naturally led us to the question of understanding the discrete logarithm problem restricted to a subset, which turned out to be very interesting in its own right.

The first result, going back to Schnorr, is very encouraging:

For a random ${S \subset {{\mathbb Z}/p{\mathbb Z}}}$ of size ${O(\sqrt{p})}$ , ${C(S) > |S|/\log p}$ with probability at least ${1-1/p}$ .

It means a random subset has essentially maximal possible DL-complexity (up to a ${\log p}$ factor) with very high probability. Unfortunately, using (truly) random subsets forecloses the possibility of extracting any gains in exponentiation relative to the average case. Second, it really does not quite answer the question of whether any specific sets are particularly hard for the discrete logarithm problem.

In the rest of this post we explore several approaches towards constructing explicit sets and sets with succinct representation for which we can prove a lower bound on their DL-complexity stronger than ${\sqrt{|S|}}$ .

III. A first attempt

Rather than trying to solve the problem in full generality, let’s constrain the definition of ${C(S)}$ to capture only generalizations of the baby-step giant-step method. Let us call this restriction ${C_\mathrm{bsgs1}}$ , defined as follows:

Given a subset ${S}$ of ${{{\mathbb Z}/p{\mathbb Z}}}$ , let ${C_\mathrm{bsgs1}(S)}$ be the minimal number ${n}$ so that ${S}$ is covered by intersection of two sets of lines ${\{y=a_i\}_{i=1}^n}$ and ${\{y=x+b_j\}_{j=1}^n}$ , where ${a_i,b_j\in {{\mathbb Z}/p{\mathbb Z}}}$ .

Recall that the intersection of two lines covers an element of ${S}$ if these lines intersect at a point whose first coordinate is in ${S}$ .

The definition of ${C_\mathrm{bsgs1}}$ complexity considers only horizontal lines (analogous to the giant steps of the algorithm, ${g^{a_i}}$ ) and parallel slanted lines (corresponding to the elements ${hg^{b_j}}$ ). The 1 in BSGS1 refers to the fact that all slanted lines have slope of exactly 1 (for now — this condition will be relaxed later).

Can we come up with a constraint on ${S}$ that would guarantee that ${C_\mathrm{bsgs1}(S) \gg \sqrt{|S|}}$ ? It turns out that we can.

Assume for a moment that all pairwise sums of elements in ${S}$ are distinct, i.e., no four elements satisfy the following equation: ${a+b=c+d}$ , where ${a,b,c,d\in S}$ , unless ${\{a,b\}=\{c,d\}}$ . If this is the case, at least one of the intersection points of the lines in the following configuration will miss an element of ${S}$ :

To see why it is so, observe that ${x_1+y_2=x_2+y_1}$ — a contradiction with ${S}$ ‘s not having solutions to this equation.

We now introduce one more way of thinking about these lines in ${({{\mathbb Z}/p{\mathbb Z}})^2}$ that are trying to hit elements of ${S}$ (we promise it is going to be the last!). Associate lines with the vertices of a graph and draw an edge between two vertices if the intersection point of the corresponding vertices projects to ${S}$ (“kills an element of ${S}$ ”).

If all pairwise sums of ${S}$ are distinct, then the graph whose nodes are the horizontal and slanted lines does not have a 4-cycle. This property alone is sufficient to bound the total number of edges in the graph (and thus the number of elements of ${S}$ hit by these lines) to be less than ${O(n^{3/2})}$ . If the graph is bipartite, which is our case, this bound is known as the Zarankiewicz problem, which can be established via a simple counting argument.

If ${2n}$ lines cannot cover more than ${O(n^{3/2})}$ elements of ${S}$ , it means that ${C_\mathrm{bsgs1}(S) = \Omega(|S|^{2/3})}$ .

What’s left to do is to construct sets whose pairwise sums never repeat. They are known as modular Sidon sets, with several beautiful constructions resulting in sets of astonishingly high density. Ponder it for a moment: we want a subset of ${{{\mathbb Z}/p{\mathbb Z}}}$ such that no two pairs of its elements sum to the same thing. Obviously, by the pigeonhole principle, the size of such as set is ${O(\sqrt{p})}$ . This bound is tight, as there exist — explicit, and efficiently enumerable — sets of size ${\Theta(\sqrt{p})}$ !

Notice that when two lines cover an element of ${S}$ , their coefficients satisfy an especially simple condition: if ${a_i = x + b_j}$ , where ${x \in S}$ , then ${a_i - b_j\in S}$ . Let ${A = \{a_1,\dots,a_n\}}$ and ${B=\{b_1,\dots,b_n\}}$ . If all of ${S}$ is covered by intersections between lines ${\{y=a_i\}}$ and ${\{y=x + b_j\}}$ , then ${S\subset A-B}$ , where ${A-B}$ is the sumset of ${A}$ and ${(-B)}$ . Using the language of additive combinatorics, Erdős and D. Newman posed in 1977 the problem of constructing subsets of $\{1,\dots,p\}$ that cannot be covered by sumsets of small sets. They proved that the set of “small squares” ${SQ = \{x^2 | x < \sqrt{p}\}}$ has this property, or in our terminology, ${C_\mathrm{bsgs1}(SQ) = \Omega(|SQ|^{2/3-\epsilon})}$ for any ${\epsilon > 0}$ .

IV. Moving upwards

Let’s relax the constraint of the previous definition by allowing two classes of lines — horizontal and arbitrarily slanted, but the only hits that count are due to intersections between lines of different classes. Call the resulting measure of complexity ${C_\mathrm{bsgs}(S)}$ :

Given a subset ${S}$ of ${{{\mathbb Z}/p{\mathbb Z}}}$ , let ${C_\mathrm{bsgs}(S)}$ be the minimal number ${n}$ so that ${S}$ is covered by intersection of two classes of lines ${\{y=a_i\}_{i=1}^n}$ and ${\{y=c_jx+b_j\}_{j=1}^n}$ , for ${a_i,b_j,c_j\in {{\mathbb Z}/p{\mathbb Z}}}$ , where only intersections between lines of different classes count towards covering ${S}$ .

By analogy with the previous argument, we’d like to identify a local property on ${S}$ that will result in a non-trivial bound on ${C_\mathrm{bsgs}(S)}$ . More concretely, we should be looking for some condition on a small number of elements of ${S}$ that make them difficult to cover by few lines of two different classes.

Fortunately, one such property is not that difficult to find. Consider the following drawing:

The intercept theorem (known also as Thales’ theorem) implies that ${|A_1B_1|:|B_1C_1|=|A_2B_2|:|B_2C_2|}$ , and consequently (applying it a second time),

$\displaystyle {(x_1-y_1)/(y_1-z_1)= (x_2-y_2)/(y_2-z_2).\qquad(*)}$

Conversely, if the 6-tuple ${(x_1,y_1,z_1,x_2,y_2,z_2)}$ is such that ${(x_1-y_1) (y_2-z_2) \neq (x_2-y_2) (y_1-z_1) }$ , these points cannot be covered all at once by three horizontal and two slanted lines.

Consider again the bipartite graph drawn on the sets of ${n}$ horizontal and ${n}$ slanted lines, where two lines are adjacent in the graph if their intersection point covers an element of ${S}$ . What is the maximal density of this graph if it is prohibited from containing the ${K_{3,2}}$ subgraph? Somewhat surprisingly, the answer is asymptotically the same as before, namely, the number of edges in the graph is ${O(n^{3/2})}$ . Therefore, if the set ${S}$ avoids 6-tuples satisfying (*), then ${C_\mathrm{bsgs}(S)=\Omega(|S|^{2/3})}$ .

What about constructing sets that have that property? A short answer is that we don’t know how to do so explicitly, but at least there exist sets satisfying this property with succinct representation.

V. Going all the way

Having flexed our muscles with the watered-down notions of sets’ DL-complexity, let us try to extend our technique to handle the most general case of unrestricted lines, where everything goes and all intersections count towards the attacker’s goal of covering the entire set ${S}$ .

Once again, we’d like to find a local property with global repercussions. Concretely, we should be looking for a configuration of lines whose intersection points satisfy some avoidable condition, similar to ${x_1+y_2=x_2+y_1}$ or the quadratic polynomial of the previous section. It may seem that we should look no further than Menelaus’ theorem, which gives us just that. If your projective geometry is a bit rusty, Menelaus’ theorem applies to the six intersection points of four lines in the plane:
It states, in the form most relevant to us that

$\displaystyle{(x_A-x_E)(x_B-x_F)(x_C-x_D)=- (x_E-x_B)(x_F-x_C)(x_D-x_A).\qquad(**)}$

It seems like a nice local property but what about its global ramifications? Namely, if we manage to construct a set such that no 6-tuple satisfies the cubic polynomial (**), what can we say about the number of lines required to cover that set? Well, our luck runs out here. Recall that we used the local property to guarantee that the graph, whose nodes corresponded to lines and edges corresponded to elements of ${S}$ covered by intersection points, excluded a certain subgraph. First, it was a 4-cycle, then ${K_{3,2}}$ . Unfortunately, if the graph excludes a complete graph on four vertices, which Menelaus’ theorem guarantees for sets avoiding (**), the number of edges in that graph can be as large as ${\Theta(n^2)}$ . This is the consequence of Turán’s theorem (or Erdős–Stone) that yields no bound better than that unless the excluded subgraph is bipartite.

The only path forward is to find a Menelaus-like theorem that allows us to exclude a bipartite graph. It turns that the minimal such configuration involves seven lines and 12 intersection points:
Most compactly, the theorem states that the following determinant evaluates to 0:

$\displaystyle \det\left(\begin{matrix} x_1 - y_1 & x_1 - z_1 & z_1(x_1 - y_1) & y_1(x_1 - z_1) \\ x_2 - y_2 & x_2 - z_2 & z_2(x_2 - y_2) & y_2(x_2 - z_2) \\ x_3 - y_3 & x_3 - z_3 & z_3(x_3 - y_3) & y_3(x_3 - z_3) \\ x_4 - y_4 & x_4 - z_4 & z_4(x_4 - y_4) & y_4(x_4 - z_4) \end{matrix}\right)=0.$

Using the same argument as before, if ${S}$ avoids solutions to the above equation on 12 variables and total degree 6, the “hit” graph defined over the ${n}$ lines avoids the ${K_{3,4}}$ graph. A variant of the Zarankiewicz bound guarantees that such graph has ${O(n^{2-1/3})=O(n^{5/3})}$ edges (the exponent in the Zarankiewicz bound depends only on size of the smaller part of the excluded bipartite graph). Since each element of the set ${S}$ corresponds to at least one edge of the “hit” graph, ${|S|=O( n^{5/3})}$ and consequently ${C(S)=\Omega(|S|^{3/5})}$ , which is better than the trivial bound ${|S|^{1/2}}$ . Finding explicit constructions remains a challenge, although it is easy to demonstrate existence of such sets with succinct representation by probabilistic method.

VI. Bipartite Menelaus’ Theorem and Open Problems

Even though our original motivation was rooted in cryptography, we ended up proving a fact of projective geometry. In an equivalent form, which is most similar to the standard formulation of Menelaus’ theorem, it asserts that
where the line segments are signed: positive if they point in the same direction as the line they are part of (for some arbitrary but fixed orientation), and negative otherwise.

The classic (and classical — after all, Menelaus of Alexandria lived in the first century AD) theorem is implied by ours. Indeed, in the degenerate case when ${A_1=C_1}$ , ${B_2=C_2}$ , and ${A_3=B_3}$ , following a furious round of cancellations, we end up with Menelaus’. This explains why we refer to our “12-point’’ theorem as bipartite Menelaus’: it is the minimal Menelaus-like theorem that involves lines separated into two classes.

We did search far and wide for evidence that this theorem had been known before, and came up empty. In retrospect, such a theorem is inevitable — the number of intersections (i.e., equations) grows quadratically in the number of lines, each of which only requires two free variables to describe. This is a counting argument that really gives no insight into why bipartite Menelaus’ theorem is what it is. Is there a purely geometric proof? Is it a consequence of a simpler/deeper fact about projective geometries over finite fields? We’d love to know.

Let’s measure our progress against the initial goal of finding explicit sets that are as hard as the entire group against the discrete-logarithm-finding adversary. We are not there yet — although we did develop some machinery for arguing that some sets are more resistant than the most pessimistic square-root bound implies, but these sets are hard to construct and too small to be useful. What about proving that some natural sets, such as the sets of squares, as in Erdős-Newman, or cubes, have high DL-complexity? It is conceivable that the combinatorial approach based on excluded subgraphs is not sufficient to get us to the sweet spot of sets of size and DL-complexity ${\Theta(p^{1/2-o(1)})}$ . What can?

A necessary disclaimer: the generic group model is just that — a model. Any instantiation of the abstract group allows direct observation of the group elements, and may enable attacks not captured by the model. For instance, representation of the group elements as integers modulo ${q}$ has enough structural properties that index calculus is exponentially more effective in $({{\mathbb Z}/q{\mathbb Z}})^*$ than any generic algorithm. On the positive side, for many groups, such as some elliptic curves or prime-order subgroups of $({{\mathbb Z}/q{\mathbb Z}})^*$ for sufficiently large ${q}$ , no algorithms for finding discrete logarithms faster than generic methods are presently known. It motivates studying generic groups as a useful abstraction of many groups of cryptographic significance.

Notes

The abstract (generic) group model was introduced in the papers by Nechaev and Shoup, and hardness of the discrete logarithm in that model was shown to be ${\Theta(\sqrt{p})}$ . Several generic methods for computing discrete logarithm with similar total running time are known: Shank’s baby-step giant-step method, Pollard’s rho and kangaroo (lambda) methods. These algorithms can be adapted to intervals $[a,b]\subset \mathbb{Z}/p\mathbb{Z}$ to work in time $\sqrt{|a-b|}$ , matching the pessimistic square-root bound. For small-weight subsets of $\mathbb{Z}/p\mathbb{Z}$ see work of Stinson and references therein. Canetti put forward a variant of the Decisional Diffie-Hellman assumption where one of the exponents is sampled from an arbitrary distribution of bounded min-entropy. Chateauneuf, Ling, and Stinson gave a combinatorial characterization of algorithms for computing discrete logarithm in terms of slope coverings, and show how weak Sidon sets are related to optimal algorithms. Erdős and Newman defined the notion of bases for subsets of $\{1,\dots,p\}$ , which corresponds (up to a factor of 4) to BSGS1-complexity in ${{\mathbb Z}/p{\mathbb Z}}$ . They showed that random subsets of size $p^{1/2-\epsilon}$ have basis of size $\Theta(|S|)$ and for sets of squares their basis is $\Omega(|S|^{2/3})$ . Subsuming the counting argument of Erdős and Newman, Schnorr proved that the discrete logarithm problem has essentially optimal (up to a logarithmic factor) hardness on random subsets. Resolving the question of Erdős and Newman, Alon, Bukh, and Sudakov showed that for sets ${S}$ of size exactly ${\sqrt{p}}$ even their restricted DL-complexity, ${C_\textrm{bsgs1}(S)}$ is ${o(|S|)}$ . They also extend analysis of BSGS1-complexity for the set of squares to that of higher powers.

	Mostafa Touny on Avi wins the Turing, TCS for…
	Harvard Professors o… on Open letter to the Harvard…
	Harvard Professors o… on Open letter to the Harvard…
	Harvard, we have a p… on Letter to the Harvard Corporat…
	Eitan bachmat on Letter to the Harvard Corporat…

From Discrete Logarithm Problem to Menelaus Theorem

Published by Ilya Mironov

Leave a comment Cancel reply

Share this:

Related

Published by Ilya Mironov

Leave a comment Cancel reply