One of the central assumptions in cryptography is the hardness of the
discrete logarithm problem: given g^x find x, where g is a group element
of prime order p. In the adversary has only oracle access to the group,
the complexity of the problem is about p^1/2.

Define the complexity of the set S as the number of queries that the
adversary has to ask when x is known to belong to S. We show that the
adversary can be modeled as a set of lines, such that projections of
their intersection points cover S. An open problem is to construct small
sets of high complexity. We show several constructions that get us there
based on ideas from combinatorial number theory. The tools that we use
include Sidon sets and Turan numbers. As a special treat we will prove
and use bipartite Menelaus' theorem---an extension of a 2,000+-year old
theorem of planar (and projective) geometry.

This is joint work Anton Mityagin, UCSD, and Kobbi Nissim, Ben-Gurion
University.