Difference sets and their application to secret sharing

Let  G be an (Abelian) group of finite order n, and let V be a subset of G
of size m. Then (G,V) is called a simple difference set if all non-zero
elements of G occur exactly once as a difference v_i-v_j where v_i and v_j
are elements of V. For instance, {1,2,4} is a difference set in the
additive group of F_7, the finite field with 7 elements.

More generally, an (n,m,r)-difference set is one where the non-zero
elements of G each occur exactly r times as a difference, rather than just
once. For example (Paley,Todd), the set of non-zero squares in the finite
field F_q, where q is a prime power such that q=4s-1, constitute a (q,
2s-1, s-1)-difference set in the additive group of that field.

Note that (V+g, G), where g is an element of G, is a difference set as
well. It is called a translate of (V,G). Note that, for instance,  (V,G)
is a simple difference set if and only if the intersection between V+g and
V consists of a single element, for all non-zero elements g in G.

If phi is an automorphism of G, then (phi(V),G) is also a difference set. 
Difference sets (V,G) and (W,G) are called equivalent if W is of the form
W=phi(V)+g, for some automorphism phi of G and some element g in G. An
integer t is called a Hall multiplier of a difference set (V,G) if t is
relatively prime to the order of G and if the automorphism phi_t that
multiplies elements of G by t, maps V to a translate of itself, i.e.,
phi_t(V)=V+h for some element h of G. A version of the classical
Multiplier Theorem states that if p is a prime greater than r that does
not divide the order of G but that does divide m-r, then p is a Hall
multiplier of (V,G).


Difference sets form a classical topic in mathematics, and they play an
important role in several branches of discrete mathematics and coding
theory. Interestingly, algebraic number theory is known to have an
important bearing on the theory as well. Even though quite some things are
known about difference sets, they are the subject of a number of famous
long standing open problems. See for instance the book A Course in
Combinatorics by van Lint and Wilson for an introduction to the topic.

In this project we study applications of difference sets to cryptography.
More precisely, we consider applications to cheater detection in secret
sharing schemes over finite fields (nicely presented in a recent paper by
Stinson et al.), as well as to secure & private storage.

A differential structure is a recently considered variation on the concept
of difference sets. It has particularly nice applications to cryptography,
stronger in fact than those of difference sets.

Instead of a single set V we consider a collection of disjoint subsets
V_1, ... , V_w of G, and we are interested in bounds on the size of the
intersections between (any translate of) a V_i with the union of the other
V_j's different from V_i. A structure is ``good'' if those intersections
are ``small,'' while each V_i is relatively ``large,'' and there are ``a
lot of'' V_i's. These relative sizes are only required to be upper bounded
by some given parameter. So they ``need not be exact.'' This relaxation
leads to many more potential constructions, also based on elementary
algebraic geometry. We may also address some existence questions
concerning differential structures. Study of some of the classical
foundations and constructions of difference sets will of course also be
part of this project.


Advisor: Ronald Cramer.