THE CONSTRUCTION OF GEOMETRIC
THRESHOLD SCHEMES WITH PROJECTIVE
GEOMETRY
by
Leanne D. Holder
B.S., University of Southern Mississippi, 1994
A thesis submitted to the
University of Colorado at Denver
in partial fulfillment
of the requirements for the degree of
Master of Science
Applied Mathematics
1997
This thesis for the Master of Science
degree by
Leanne D. Holder
has been approved
by
Date
1
/Iff
Holder, Leanne D. (M.S., Applied Mathematics)
The Construction of Geometric Threshold Schemes With Projective Geometry
Thesis directed by Associate Professor William E. Cherowitzo
ABSTRACT
In a secret sharing scheme, a dealer has a secret and distributes shares
of the secret to the participants. The shares are distributed in such a way that
only certain subsets of the participants can combine their shares to recover the
secret. We use projective geometry to construct a secret sharing scheme for
which the shares are represented by points in a projective 4space. A sharply
focused set is a set of k points, no three collinear, in a finite projective plane
in which the (*) distinct secants formed by this set intersect a given line in
exactly k points. We use sharply focused sets to design a scheme so that
certain subsets of participants can pool their shares to calculate the secret.
Several examples show how sharply focused sets can be used for differing sizes
of the subsets of the participants that are allowed to calculate the secret. We
provide a proof that sharply focused sets obtained from a certain construction
correspond to cosets of a group. This implies that the possible sizes of these
sharply focused sets are divisors of the group order. Finally, we provide a new
construction that uses subplanes in planes of prime power order. The previous
construction method works only on planes of odd order, but the subplane
construction method works in planes of both even and odd order.
in
This abstract accurately represents the content of the candidates
thesis. I recommend its publication.
Signed
IV
ACKNOWLEDGMENT
There are many people who deserve more than just an acknowledgment on
this page. The following people deserve many hugs.
My advisor, Bill Cherowitzo, for the many geometric lessons on and off the
racketball court. May his seemingly bottomless well of patience not run
dry until long after I am finished with my studies.
My best friend, Allen Holder, for his love, encouragement, and patience over
the past five years. I consider myself extremely blessed to have him as my
husband.
My mom, Dianne M. Daniel, for teaching me how to play the game so well.
Bring on the goldfish.
My dad, Donnie L. Daniel, for his profound and more often than not, prac
tical words of wisdom.
CONTENTS
Chapter
1 Secret Sharing Schemes..................................... 1
1.1 A Generic Secret Sharing Scheme Involving the Employ
ees of a Bank...................................... 1
1.2 An Introduction to Projective Geometry.................... 2
1.3 Using Projective Geometry to Construct A Secret Shar
ing Scheme for a Bank.............................. 6
2 Sharply Focused Sets of lines in PG(2,q).................. 11
2.1 The Relationship Between Sharply Focused Sets and Se
cret Sharing Schemes for a Bank................... 11
2.2 Coordinate Representation of Points and Lines in PG(2,q) 13
2.3 Construction of Sharply Focused Sets in PG(2,q) .... 14
2.4 Two Examples with q = ll................................. 16
2.5 Two Examples with q=13................................... 21
2.6 Structure of the Incidence Tables........................ 23
2.7 General Method........................................... 25
3 Proving the Divisibility Argument......................... 27
3.1 A Relationship Between Points of Q and Points of l . 27
3.2 Sharply Focused Sets Correspond to Cosets of a Group . 30
4 Another Construction of Sharply Focused Sets.............. 33
vi
4.1 Even Characteristic Preamble............................. 34
4.2 Existence and Construction of Sharply Focused Sets in
Planes of Prime Power Order.......................... 34
4.3 Super Sharply Focused Sets in Planes of Even Order . 36
4.4 A Sharply Focused and Super Sharply Focused Set in
PG(2,16)................................................. 37
4.5 Advantages and Disadvantages of Each Construction of
Sharply Focused Sets .................................... 38
5 Further Studies............................................... 39
References............................................................ 40
vii
FIGURES
Figure
1.1 A Geometric Representation.................................... 7
1.2 Another Geometric Representation.............................. 9
2.1 Structure of the Incidence Tables............................ 23
4.1 Subplane of a Projective Plane............................... 33
Vlll
TABLES
Table
2.1 The Incidence Table for q = 11 and l an Exterior Line ... 16
2.2 The Incidence Table for q = 11 and l a Secant Line........... 20
2.3 The Incidence Table for q = 13 and l an Exterior Line ... 21
2.4 The Incidence Table for q = 13 and l a Secant Line........... 22
IX
1. Secret Sharing Schemes
In a secret sharing scheme, a dealer has a secret and would like to
give every participant of this scheme a share of the secret. The shares should
be distributed secretly, so that no participant knows the share of another
participant. Also, some time later a subset of the participants could pool their
shares in an attempt to compute the secret. In some situations the dealer may
want some of the subsets of participants to be able to compute the secret while
other subsets of the participants to be unable to compute the secret [2, 7]. If
the dealer is faced with this type of situation, then it is necessary to identify
the appropriate subsets of participants before the shares are distributed.
1.1 A Generic Secret Sharing Scheme Involving the Employees of
a Bank
In a bank, there is a vault that must be opened every day. The
president of the bank employs a number of senior tellers and vice presidents
but does not trust any individual with the combination to the vault. So, a
system needs to be designed in which certain combinations of these employees
can open the vault.
One plan is to design a system, call it Design A, whereby any three
senior tellers can open the vault or any two vice presidents can open the vault.
Although this appears as a practical solution in theory, this system might not
1
work in reality if only two senior tellers and one vice president show up for
work [7]. A more practical design, Design B, is obtained by adding to Design
A the ability for two tellers and one vice president to open the vault. One
must insure that no pair of senior tellers can open the vault while allowing any
vice president in cooperation with a pair of senior tellers the ability to open
the vault [6]. If we can do this, we will have obtained a secret sharing scheme
in which the dealer is the president of the bank, the participants are the vice
presidents and senior tellers, and the secret is the combination to the vault.
1.2 An Introduction to Projective Geometry
People who have studied only Euclidean geometry regard it as an obvious
fact that two coplanar lines with a common perpendicular are parallel, in
the sense that, however far we extend them, they will remain the same
distance apart. By stretching our imagination we can conceive the pos
sibility that this is merely a first approximation: that if we could extend
them for millions or billions of miles we might find the lines getting closer
together or farther apart. When we look along a straight railroad we get
the impression that the two parallel rails meet on the horizon. Anyhow,
by assuming that two coplanar lines always meet, we obtain a system of
propositions which is just as logically consistent as Euclids system [3].
Definition: [8] A finite projective plane consists of a finite set V of points and
a set of subsets of V called lines, which satisfies the axioms (Al), (A2), and
(A3):
(Al) Given two points, there is exactly one line that contains both;
(A2) Given two lines, there is exactly one point that lies on both;
(A3) There are four points, of which no three are collinear.
In this setting, if a point lies on a line then the point is said to be
incident with the line. Similarly, the line is also said to be incident with the
2
point. The axioms in the definition of a finite projective plane are the keys
to the proofs of the following lemmas dealing with the incidence of points and
lines in a finite projective plane, II.
Lemma 1.3.1. [1] If h and l2 are any two distinct lines of II, then there is a
point P in II not incident with and l2.
Lemma 1.3.2. [1] Any two lines of II are incident with the same number of
points.
Lemma 1.3.3. [1] Any two points of II are incident with the same number of
lines.
In a finite projective plane, there are a finite number of points on a
line, a finite number of lines through a point, and a finite number of points
and lines in the plane. The previous three lemmas can be combined with some
results not mentioned here to obtain the following important theorem on the
exact numbers for the above incidences.
Theorem 1.3.4. [1] Let U be a finite projective plane. Then there is an
integer q such that
(1) Every point of II is incident with exactly q + 1 lines;
(2) Every line of II is incident with exactly q + 1 points;
(3) II contains exactly q2 + q + 1 points;
(4) II contains exactly q2 + q + 1 lines.
One commonly used construction for obtaining a projective geometry,
denoted by PG(n,q), starts with a vector space. Let V(n+l,q) be a vector
space of rank n + 1 over a finite field GF(q) where q is a prime power. The
elements of V(n+l,q) are the (n+l)tuples of the form (xq, x\, , xn) where
3
the Xi are in GF(q). The points, lines, and planes of PG(n,q) are the rank
1,2, and 3 vector subspaces in V, where rank is the algebraic dimension of a
vector subspace. The geometric dimension of objects in PG(n,q) refers to the
geometric concept where lines are 1dimensional, planes are 2dimensional and
so forth. The rank and dimension always differ by one, i.e., a rank 2 subspace
corresponds to a line which is referred to as having geometric dimension 1.
In this construction, incidence is defined by subspace containment.
In the projective geometry setting, lines are regarded as certain sets of points
and similarly planes can also be regarded as certain sets of points. If a point
lies on a line or in a plane, then the point is said to be incident with the line
or plane. This is equivalent to the notion of a rank 1 subspace being contained
in a rank 2 or rank 3 subspace.
When n = 2, the vector space construction of a projective geometry
gives a finite projective plane that we examined earlier. Every plane arising
from this construction satisfies the axioms given in the formal definition of a
finite projective plane.
A well known result from Linear Algebra states that if S and T are
vector spaces then
rk(S') + rk(T) = rk(S n T) + rk(5 U T).
Let T = PG(4,q) be derived from a rank 5 vector space. Then we can use the
rank formula to determine the possible incidences of lines and planes in F.
First, we examine the relationship between two distinct planes, 7Ti
and 7t2, in T. If 7Ti and 7t2 lie in a common 3dimensional subspace of T,
(i.e., rank 4 vector space) then the rank formula tells us that these two planes
4
intersect in a line (a rank 2 vector subspace). But, if 7Ti and 7t2 do not lie in
a common 3dimensional subspace of F, by the rank formula, 7Ti and 7r2 must
intersect in a point, since their union would have rank 4. Let P, Q, and R
are be three noncollinear points in T. Since each point has rank 1 and two
points determine a line, the rank formula tells us that the smallest subspace
containing these 3 points is a rank 3 subspace of T, which is a projective plane.
Next, we examine the incidence relationship between a line, l and a
plane 7r, both in T. If l meets 7r, then l either meets ir in a point or is entirely
contained within 7r. Suppose two points of l are in n. Then since n is a vector
subspace, the span of any two points that lie in 7r, also lies in 7r. In this case,
it must be that l is entirely contained in 7r.
We will consider a special type of object called an oval in the projec
tive plane, 7r = PG(2,q). Similar to an oval in Euclidean geometry, an oval,
denoted fl, in 7r is set of q + 1 points in ir such that no three of the points are
collinear. Since no three points on fl are collinear, if l is a line in 7r, then l can
intersect fl in at most two points and we can classify l in the following way:
l is a tangent line to fl provided / fl fl = 1,
l is a secant line to fl provided \l n fl = 2,
l is an exterior line to fl provided \l fl fl = 0.
Let P be a point in 7r. Then P can be classified in three ways with respect to
fl:
if P is on fl then P is called an ovalpoint,
if P is not on fl but on a tangent line to fl then P is called an exterior
point, and
5
if P is neither on f2 nor on a tangent line to Cl then P is called an
interior point.
For q odd, we have that any exterior point to Cl has exactly two tangents
through it. When q is even, there are no interior points, since every point is
on a tangent line and all tangents with respect to Cl intersect at a unique point
in the plane, called the nucleus (or knot) of Cl.
We can use some of the incidence relationships between l, ir and a
point P in T to construct a secret sharing scheme that satisfies the requirements
of Design A and Design B. This is accomplished by assigning, as the shares
each participant receives in the scheme, a special point in T. The points of
7r and l will represent the shares distributed to the senior tellers and vice
presidents and a point P will represent the secret. We will describe a method
for distributing the shares in a projective 4space so that only certain pre
determined subsets of participants can calculate the secret.
1.3 Using Projective Geometry to Construct A Secret Sharing
Scheme for a Bank
We are now ready to examine the relationship between the bank
situation and some planes and lines in a projective 4space. In both Design A
and Design B, we would like the secret to be represented by a special point,
P, in a finite projective plane, Vd in T. The only information available about
P to the senior tellers and vice presidents is that P is represented by a point
in Vd. Vd is often referred to as the domain variety and is generally public
knowledge. The shares belonging to the senior tellers and the vice presidents
6
can be represented by specially selected points in F. By carefully selecting the
points that we pick to represent shares, we can alter the relationships between
l and Vd as well as l, tt and Vd to create a geometric interpretation of the secret
sharing schemes associated with the bank problem.
In Design A, the secret sharing scheme that we seek to develop is
sometimes referred to as a twolevel concurrence scheme. A twolevel concur
rence scheme requires concurrence of the participants in at least one of the two
levels before a controlled action can take place. In this instance, the controlled
action is the pooling of the shares to calculate the combination to the bank
vault. One concurrence level consists of the bank vice presidents and the other
concurrence level consists of the senior tellers. Any two points representing
the shares of the vice presidents will define a line l G T that intersects Vd in
only point P. Any three points representing the shares of the senior tellers
should define a plane tt G T that intersects Vd in only point P. In order to
have this property in the latter case we must insure that no three of these
points are collinear. For, if those points were collinear, they would only define
a line and not the desired plane tt that we require them to form.
r
l
/ / 'v
\ \ /
Figure 1.1. A Geometric Representation
7
Suppose the line l formed by two shares belonging to vice presidents
intersects the plane 7r formed by the three shares belonging to senior tellers in
exactly one point. Also, suppose that 7r and l both intersect Vd at the point
P. Then necessarily, the intersection of ir and l is P. This is the situation
as described in Design A. One point is not enough information to generate a
line and two points are not enough information to generate a plane. So, if l is
not contained in 7r and only one vice president and two senior tellers come to
work, then there will not be enough information among the three participants
to calculate the secret.
To avoid this situation in Design A, we created a new design, Design
B, having a stronger relationship between l and 7r other than their intersection
being only P. If l and n intersect at more than one point, then l must lie in
the plane 7r. Just as in Design A, l and ir both need to intersect Vd in the
point P. Since P is a point that represents the secret, the coordinates that
represent P are unknown to the senior tellers and vice presidents. Just one
vice president alone does not have enough information to generate a line that
intersects Vd at P, since two points are required to generate a line. Similarly,
any two senior tellers do not have enough information to generate a plane that
intersects Vd at the point P, since three points are required to generate a plane.
Furthermore, for this to be a perfect design, i.e., one in which no set of shares
other than the predetermined ones can be combined to obtain the secret, no
pair of the points in 7r belonging to the senior tellers can be collinear with P.
For three senior tellers to be able to pool their shares and calculate
the secret, it is necessary for the points representing the shares belonging to
8
the senior tellers to have the property that they are not collinear and all lie in
the same plane, ir. Thus, these points are constrained to lie on an oval.
The points representing the shares of the vice presidents must lie on
a line that intersects Vd at P. Since we are adding the new restriction that a
vice president and any two senior tellers have the ability to pool their shares
and calculate the secret, we need the points representing the shares belonging
to the vice presidents to also lie in 7r. In order for any vice president to be
able to calculate the secret with only two senior tellers, any pair of points in
7r given to senior tellers may not be collinear with any point on l belonging
to any of the vice presidents. With these restrictions, we can be assured that
one vice president and any pair of senior tellers can calculate the secret while
at the same time insuring that no pair of senior tellers can calculate the secret
alone. Figure 1.2 illustrates this concept.
Figure 1.2. Another Geometric Representation
In Figure 1.2, we have a geometric representation of a possible way
to distribute the shares. Suppose that a and b are used as shares, then a third
9
share, say c, collinear with a and b, could not be used in conjunction with a
and b. If this happened, then these three shares would generate a line instead
of the desired plane necessary to recover P. Any three shares distributed to the
senior tellers should not be collinear, since these points could not determine
a plane. It is for this reason that we require that the shares belonging to the
senior tellers lie on an oval of n.
An example of a geometric perfect secret sharing scheme for Design
B would be to let the shares belonging to the vice presidents be represented by
the points g and h and the shares belonging to the senior tellers be represented
by the points a, d, and /. Thus, the two vice presidents could calculate a line
intersecting Vd at P, and the three senior tellers could calculate the plane 7r
intersecting Vd at P, while any vice president and two senior tellers could also
calculate this plane intersecting Vd at P.
10
2.
Sharply Focused Sets of lines in PG(2,q)
2.1 The Relationship Between Sharply Focused Sets and Secret
Sharing Schemes for a Bank
In the previous bank illustration, the president of a bank does not
trust any individual with the combination to the vault. A system was designed
that would allow certain subsets of the employees to open the vault, while other
subsets were not able to open the vault. For instance, one vice president and
two senior tellers could open the vault, but one vice president and one senior
teller could not. The system that was designed in Chapter 1 to accommodate
the presidents wishes had strict restrictions on what type of points could
represent the shares belonging to the senior tellers and vice presidents. What
happens to our design of a perfect secret sharing scheme, when the president
adds more employees? We are interested in maximizing the number of shares
that can be distributed in 7r, so that an efficient design can be constructed for
any number of employees, such that:
any two vice presidents can combine their shares to calculate the se
cret,
any three senior tellers can combine their shares to calculate the secret,
and
any one vice president and any two of the senior tellers can combine
their shares to calculate the secret.
11
Since any line in n has q + 1 points, there are at most q points
available to use as shares for the vice presidents, since one point of the line
must be used to represent the secret. In a projective plane of odd order, there
are at most q + 1 points with the property that no three of the points are
collinear and these q + 1 points form an oval, Cl. Points of Cl are ideal choices
to represent the shares belonging to the senior tellers. In the bank illustration,
it was necessary that no pair of points in 7r belonging to the senior tellers be
collinear with P. Also, for any vice president and any two senior tellers to be
able to pool their shares to calculate the secret, it was necessary for the two
shares belonging to the senior tellers not be collinear with the share belonging
to the vice president. Out of the q + 1 points on l and the q + 1 points on the
oval, how many can be used as shares so that the incidences mentioned above
are avoided?
Any two shares given to the senior tellers determine a secant line of Cl
that intersects l in a point. We would like to determine the subsets of the q + 1
points of Cl whose secants intersect l in the smallest number of points. Such
subsets will provide the greatest number of points for use as shares for the
vice presidents. Let A be a subset of Q with k points. There are Q) distinct
secants formed by points of K. Let x represent the number of points at which
these secants intersect l. Observe that, for a fixed point on l, there are at most
LfJ secants of K that contain this point. Clearly, x\_~\ > (*) If k = 2m+ 1,
for some m, the minimum value of x consistent with this inequality is k, but if
k = 2m, /c 1 is the minimum number of shares that may not be distributed
to the vice presidents. The lower bound of k 1 can only be achieved under
12
special circumstances, which leads us to the following definition. A set, )C, of k
points no three collinear in a finite projective plane 7r = PG(2, q) is said to be
sharply focused on a line l if the Q) distinct lines defined by pairs of the points
of /C intersect l in only k distinct points [6]. By having the shares belonging
to the senior tellers be focused on as few points as possible on l, more shares
can be distributed. That is, the remaining points on l (other than P) are then
eligible to be used as shares for vice presidents.
2.2 Coordinate Representation of Points and Lines in PG(2,q)
Before we develop a construction for finding sharply focused sets and
present examples, we need a coordinate representation of points and lines in
a projective plane. Let P = GF(pn) be a finite field of order pn, p a prime
and define n to be the projective plane, PG(2,pn). Then the points of n
can be represented by ordered triples of elements from P, with not all of the
coordinates being zero. For instance, a point P e 7r can be represented by
(xi, x2, X3) where Xi E P and at least one Xi 7^ 0. Two points (2:1, X2, Â£3) and
(l/i, 2/2,2/3) are said to be equivalent if there is a scalar a e P, a / 0, such
that Xi = ayi for = 1, 2, 3. So that any point in 7r can be represented in the
form (aq,2:2,1), (1,2:2,0), or (0,1,0) where 1 is the identity of P [1].
The lines in tt are defined in the same manner at the points but
instead of using ordinary parenthesis, we use square brackets. So that if l is
a line of 7r, l [x\, x2,2:3] with not all 2^ = 0. Two lines, [xi,X2,x$\ and
[2/1, 2/2i 2/3] are equivalent if there is some scalar a 7r, a 7^ 0, such that
Xi = ayi for i = 1, 2, 3. A point, (a, b, c), and a line, [x,p, z], are incident
13
if and only ax + by + cz = 0. For m, x, y, k G T we can represent lines in
our projective plane as equations of lines used in the Euclidean Plane. The
line y mx + 6 can be written as [m, 1,6] and consists of all points of the
form (x,mx + 6,1) as well as the point (l,m,0). The line x = k has the
form [1,0, A;] and consists of all points represented by (k,y, 1) and (0,1,0).
The line [0,0,1], also referred to as the line at infinity, contains all points
represented by (l,a;,0) [1].
2.3 Construction of Sharply Focused Sets in PG(2,q)
We now develop the construction used in [6] to create sharply focused
sets in PG(2,g) with q odd.
Let fl be an arbitrary conic in 7r = PG(2,g), q odd and l either an
exterior line or a secant line of Q. A conjugate pair of points on Q with respect
to the line l are two points A and B, such that the tangent lines to O at A and
B both intersect l in the same point. If l is an exterior line to f2, then these
conjugate pairs are determined by first computing the tangent line equation
for each point on D. These q + 1 tangent lines intersect l in exterior points
and will lie two at time on each exterior point of l. If l is a secant line to fl,
then l and f2 share two points. Disregarding these two points, the remaining
q 1 points of can be classified into conjugate pairs by the same method
used when l was an exterior line. In the process of identifying conjugate pairs
of points on Q, we identify all the exterior points on l, so that the remaining
points on l must be interior points.
14
The secant/tangent incidence table is the main tool used to identify
sharply focused sets corresponding to l. This is a square table whose rows and
columns are indexed by points on not on l, and whose entries are indexed
by points on l, not on Q. More specifically, let i and j be two points on fl\l.
If i ^ j, then these two points determine a secant line that intersects l at the
point in the (i, j) position of the table. Similarly, if i = j, then this point has a
tangent line that intersects l at the point in the (i, i) position of the table. For
the ease of finding sharply focused sets, points of Q will be listed by conjugate
pairs in the table.
To look at specific examples, we will make several choices for the oval
as well as the line on which this oval is to be sharply focused. First we choose
for our arbitrary oval the specific conic,
ft = (O', j2,1) I j GF(,)} U {(0,1,0)}.
The exterior and secant lines that we will be dealing with in the examples
consist of the set of points in 7r that satisfy the equation y = c, c G GF(q)
along with the point (1,0,0). This line, l, will be referred to as y = c. If c is
a square in GF(g), then this will be a secant line to since l and O will have
two points in common. If c is not a square, then this will be an exterior line
to For simplicity, we will use a compact notation to represent points of fi
as well as points of l. The point (0,1,0) Â£ Q, will be represented by a and the
number j will indicate the point (j,j2,1) G f2. Similarly, the point (1,0,0) G l
will be represented with a and the number i will indicate the point (j, c, 1) of
l.
15
2.4 Two Examples with q = 11
The following two examples for q = 11 help to clarify the procedure
and also show how the secant/tangent incidence tables are used to obtain
sharply focused sets.
Example 2.4.1 Let q = 11 and, since 2 is not a square in GF(ll), let l be
the exterior line to Cl are given by y = 2. Then the six exterior points of l
with respect to Cl, a, 6, 5, 0, 4, 7, correspond to the following conjugate pairs
of points on Cl: {a, 0}, {5,7}, {6,4}, {3,8}, {9,10}, and {1,2}.
a 0 5 7 6 4 3 8 9 TO T 2
a a 0 5 7 6 4 3 8 9 10 1 2
0 0 a 7 5 4 6 8 3 10 9 2 1
5 5 7 6 4 a 0 9 10 1 2 3 8
7 7 5 4 6 0 a 10 9 2 1 8 3
6 6 4 a 0 5 7 1 2 3 8 9 10
4 4 6 0 a 7 5 2 1 8 3 10 9
3 3 8 9 10 1 2 0 a 7 5 4 6
8 8 3 10 9 2 1 a 0 5 7 6 4
9 9 10 1 2 3 8 7 5 4 6 0 a
10 10 9 2 1 8 3 5 7 6 4 a 0
1 1 2 3 8 9 10 4 6 0 a 7 5
2 2 1 8 3 10 9 6 4 a 0 5 7
Table 2.1. The Incidence Table for q = 11 and l an Exterior Line
Notice that every 2x2 block in Table 2.1 contains either exterior
points of l or interior points of l, but not both. Also, observe that this table
can be partitioned into four 6x6 blocks, where the two 6x6 blocks that
constitute the main diagonal contain only exterior points and the two 6x6
blocks that constitute the off diagonal contain only interior points of l.
We are searching for a set of k points on Cl whose secant and tangent
16
lines intersect l in exactly k points. We start the search for sharply focused
sets by taking a closer look at the two 6x6 blocks that lie on the main
diagonal of the table. The block that appears in the upper right corner of the
table contains only the six exterior points of l and is created from the secant
and tangent lines generated by three distinct conjugate pairs of elements in
Q, namely {a, 0}, {5,7}, and {6,4}. Similarly, the block that appears in the
lower right corner of the table also contains only the six exterior points of l.
This block is created from the secant and tangent lines generated by the three
other distinct conjugate pairs of elements in f2, {3,8}, {9,10}, and {1,2}. We
see that the two sets JCi = {a, 0,5,7,6,4} and /C2 = {3,8,9,10,1,2} are both
sharply focused on the six exterior points of l.
We can use certain elements from the three conjugate pairs that gen
erate each 6x6 block on the diagonal of the table to create sharply focused sets
of size three. Let JCi and /C2 be the two sets of points on Cl whose elements are
the first elements in each conjugate pair and the second elements in each con
jugate pair, respectively. Then we have that K.i = {a, 5,6} and /C2 = {0,7,4}.
The secant and tangent lines created from JCi intersect the points on l that
lie in the (1, Imposition of each 2x2 subblock. Since there are only 3 points
of l in each corner of the 2x2 subblocks, JCi is sharply focused on the points
a, 5, and 6 of l. A similar inspection with /C2, shows that this set is sharply
focused on the points 0, 7, and 4 of l.
Two more sharply focused sets of size six can be created in a similar
fashion to the sharply focused sets of size three that were created. Let JCi =
{a, 5,6,3,9,1} and /C2 = {0,7,4,8,10,2} be sets constructed from extracting
17
either the first or second elements in each conjugate pair listed across the top
row of the table. Then, by examining the (1, Imposition of each 2x2 subblock
of the table, we can see that /Ci is sharply focused on the points a, 5, 6, 3, 9,
and 1 of l. Similarly, by examining the (2,2)entry of each 2x2 subblock of
the table, we see that fC2 is sharply focused on the points 0, 7, 4, 8, 10, and 2.
For the final search for sharply focused sets, we will examine corre
sponding 2x2 subblocks in each of the four 6x6 blocks. More specifically,
for i = 1,2,3, we want to examine the blocks of size four created from the ^
conjugate pair and the (3M)^ conjugate pair of points on Q listed across the
top of the table.
The secant and tangent lines generated by the conjugate pairs, {a, 0}
and {3,8} intersect l in points that lie in the four 2x2 subblocks located in the
upper left corner of each of the 6x6 blocks. Since these four 2x2 subblocks
contain only four points of l, these two conjugate pairs form a sharply focused
set of four points.
Similarly, the two conjugate pairs, {5,7}, and {9,10} generate secant
and tangent lines whose intersections with l are the points located in the 2x2
subblocks located in the center of each 6x6 block. Since these four 2x2
subblocks contain only four points of l, the two conjugate pairs of points on Q
form a sharply focused set of size four.
A final sharply focused set of size four can be created from the re
maining two conjugate pairs of the table. The pairs, (6,4} and {1,2} have
secant and tangent lines that intersect l in exactly four points. The points of
intersection are in the 2x2 subblocks that are located in the bottom right
18
corner of each 6x6 block. Thus, these two conjugate pairs also form a sharply
focused set of size four.
Thus, by inspecting the table, we have found sharply focused sets of
sizes 6, 4, and 3. The sets of six points {a, 0,5,7,6,4} and {3,8,9,10,1,2}
of Q are both sharply focused on the points o, 0, 5, 7, 6, and 4 of l. The
sets {a, 5,6,3,9,1} and {0,7,4,8,10,2} are sharply focused on a, 5, 6, 3, 9,
and 1 of l and 0, 7, 4, 8, 10, and 2 of l respectively. The sets of four points
{a, 0,3,8}, {5,7,9,10}, and {6,4,1,2} of Cl are sharply focused on the points
o, 0, 3, 8, the points 6, 4, 1, 2, and the points 5, 7, 9, 10 of l, respectively.
The sets of three points {a, 5,6} and {0,7,4} of Cl are sharply focused on
the points o, 5, and 6 of l, while the sets of points {3,9,1} and {8,10,2} are
sharply focused on the points 0, 7, and 4 of 1.
Example 2.4.2 Again, let q = 11 but instead of using the exterior line y = 2
to Cl, we use a secant line in the search for sharply focused sets. Since 5 is a
square in GF(ll), let l be the secant line given by y = 5. Since l is a secant
line to Cl, the two points that lie on both l and Cl will be omitted from the
table. The five exterior points of l with respect to Cl, a, 3,6,5,8, have the
corresponding conjugate pairs of points on Cl: {a, 0}, {5,1}, {3,9}, {8,2}, and
{6,10}.
Since we have an odd number of conjugate pairs, this table cannot
be divided into four subblocks as was done for the previous example. Notice
that every 2x2 block in this table contains exterior points of l on the diagonal
and interior points of l on the off diagonal.
We can find sharply focused sets of size five by conducting a search
19
a 0 5 1 3 9 8 2 6 10
a a 0 5 1 3 9 8 2 6 10
0 0 a 1 5 9 3 2 8 10 6
5 5 1 3 9 8 2 6 10 a 0
T 1 5 9 3 2 8 10 6 0 a
3 3 9 8 2 6 10 a 0 5 1
9 9 3 2 8 10 6 0 a 1 5
8 8 2 6 10 a 0 5 1 3 9
2 2 8 10 6 0 a 1 5 9 3
6 6 10 a 0 5 1 3 9 8 2
10 10 6 0 a 1 5 9 3 2 8
Table 2.2. The Incidence Table for q = 11 and l a Secant Line
similar to that in the previous example. Let K,\ = {a, 5,3,8,6} and K2 =
{0,1,4,2,10} be sets constructed from extracting either the first or second
elements in each conjugate pair listed across the top row of the table. Then,
by examining the (1, l)entry of each 2x2 subblock of the table, we can see
that JCi is sharply focused on the points a, 5, 3, 8, and 6 of l. Similarly, by
examining the (2,2)entry of each 2x2 subblock of the table, we see that /C2
is also sharply focused on the points a, 5, 3, 8, and 6 of l.
By inspecting the table, it can be seen that sharply focused sets of
size 5 exist and can obtained by creating a set that contains exactly one point
from each conjugate pair of Cl. The sets {a, 5,3,8,6} and {0,1,9,2,10} of
points on Cl are both sharply focused on the five points a, 5, 3, 8, and 6 of l.
Thus, for q = 11, there exists sharply focused sets of sizes 3, 4, 5,
and 6.
20
2.5 Two Examples with q = 13
Next, we examine the various secant/tangent incidence tables for
q = 13 when l is an exterior line and a secant line.
Example 2.5.1
Let q 13 and since 2 is not a square in GF(13), let l be the exterior
line to 0. given by y = 2. Then the seven exterior points {a, 3,6,11,1,4,8}
of l with respect to Q have the corresponding conjugate pairs of points on fh
{a,0}, {1,2}, {3,5}, {4,7}, {6,9}, {8, iff}, and {H,l2}.
a 0 1 2 3 5 4 7 6 9 8 10 11 12
a a 0 1 2 3 5 4 7 6 9 8 10 11 12
0 0 a 2 1 5 3 7 4 9 6 10 8 12 11
T 1 2 3 5 4 7 6 9 8 10 11 12 a 0
2 2 1 5 3 7 4 9 6 10 8 12 11 0 a
3 3 5 4 7 6 9 8 10 11 12 a 0 1 2
5 5 3 7 4 9 6 10 8 12 11 0 a 2 1
4 4 7 6 9 8 10 11 12 a 0 1 2 3 5
7 7 4 9 6 10 8 12 11 0 a 2 1 5 3
6 6 9 8 10 11 12 a 0 1 2 3 5 4 7
9 9 6 10 8 12 11 0 a 2 1 5 3 7 4
8 8 10 11 12 a 0 1 2 3 5 4 7 6 9
Iff 10 8 12 11 0 a 2 1 5 3 7 4 9 6
IT 11 12 a 0 1 2 3 5 4 7 6 9 8 10
12 12 11 0 a 2 1 5 3 7 4 9 6 10 8
Table 2.3. The Incidence Table for q = 13 and l an Exterior Line
This table is similar to the table in Example 2.2, since the seven
exterior points of l lie on the main diagonal of each 2x2 subblock of the
incidence table and the seven interior points of l lie on the off diagonal of each
2x2 subblock of the table. By inspecting the table and conducting our search
in a similar fashion to the search in Example 2.2, it can be seen that two
21
sharply focused sets of size 7 exist. Namely, the sets {a, 1,3,4,6,11,8} and
(0,2,5,7,9,10,12} of points from f7 are both sharply focused on the points a,
1, 3, 4, 6, 8, and 11 of l.
Example 2.5.2
Again, let q = 13 but instead of using the exterior line y = 2 to Cl,
we use a secant line to aid in the search for sharply focused sets. Since 3 is
a square in GF(13), let l be the secant line given by y = 3. Then, the six
exterior points a, 8, 5, 0, 2, 11 of l with respect to Â£7 have the corresponding
points as conjugate pairs: {a, 0}, {5,10}, {8,2}, {6,7}, {3,1}, and {12,10}.
a 0 5 TT 8 2 6 7 3 I 12 10
a a 0 5 11 8 2 6 7 3 1 12 10
0 0 a 11 5 2 8 7 6 1 3 10 12
5 5 11 8 2 a 0 3 1 12 10 6 7
11 11 5 2 8 0 a 1 3 10 12 7 6
8 8 2 a 0 5 11 12 10 6 7 3 1
2 2 8 0 a 11 5 10 12 7 6 1 3
6 6 7 3 1 12 10 0 a 11 5 2 8
7 7 6 1 3 10 12 a 0 5 11 8 2
3 3 1 12 10 6 7 11 5 2 8 0 a
1 1 3 10 12 7 6 5 11 8 2 a 0
12 12 10 6 7 3 1 2 8 0 a 11 5
10 10 12 7 6 1 3 8 2 a 0 5 11
Table 2.4. The Incidence Table for q = 13 and l a Secant Line
Observe that we can partition this table into four 9x9 blocks. Also,
notice that in this table pairs of the exterior points lie in the 2x2 blocks on
the main diagonal, and pairs of the interior points lie in the 2x2 blocks on
the off diagonal. This table has a similar structure to the table in Example 2.1
and the search for sharply focused sets can be conducted in a similar fashion.
22
By inspecting the table, it can be seen that there are sharply focused
sets of size 6, 4, and 3. The sets {a, 5,8,6,3,12} and {0,11,2,7,1,10} of points
on ft are both sharply focused on the points a, 5, 8, 6, 3, and 12 of l. The sets
{a, 5,8,6,3,12} and {0,11,2,7,1,10} are both sharply focused on the points
a, 5, 8, 6, 3, and 12 of l. The sets {a, 0,6,7}, (5,11,3,1}, and (8,2,12,10} of
points of ft are sharply focused on the points a, 0, 6, 7, the points 8, 2, 12,
10, and the points 5, 11, 3, and 1 of l respectively. The two sets {a, 5,8} and
(0,11,2} of points on ft are both sharply focused on the points a, 5, and 8 of
1. Similarly, the two sets (6,3,12} and {7,1,10} are both sharply focused on
the points 0, 11, and 2 of l. Thus, for q = 13, there exists sharply focused sets
of size: 3, 4, 6, and 7.
2.6 Structure of the Incidence Tables
The structure of the incidence tables in Examples 2.12.4 can be
somewhat explained. The 2x2 blocks of each incidence table are always of
the form
a
a
b p
X y
y X
Figure 2.1. Structure of the Incidence Tables
23
where the nature of x and y (with respect to Cl) are determined by whether
q = lmod 4. The points b, [3 and a, a on Cl are conjugate pairs with respect
to some line l. That is, the tangents through both a and a intersect l at the
same point. The same is true for b and (3. If a secant through a and b intersects
l at x then so does the secant through a and (3. Similarly, if a secant through
a and (3 intersects l at y then so does the secant through a and b [6].
The secant/tangent incidence tables will be one of two basic designs,
depending on whether q = 1 mod 4 and whether l is a secant line or an
exterior line to fl.
If q = 1 mod 4 and l is an exterior line to Cl, then there will be an odd
number of conjugate pairs in Cl. Each 2x2 block of the incidence table
will have the exterior points of l on the diagonal and interior points of
l lie on the off diagonal. The same structure occurs for q = 1 mod 4
and l a secant line to Q.
If q = 1 mod 4 and l is an exterior line, then there will be an
even number, n, of conjugate pairs in Cl with respect to l. The table
can be partitioned into four subblocks each of size n x n. If the
conjugate pairs of Cl are arranged appropriately, then the two sub
blocks that lie on the main diagonal of the table consist of 2 x 2 blocks
of exterior points of l and the two subblocks on the off diagonal consist
of 2 x 2 blocks of interior points of l. The same structure also occurs
for q = 1 mod 4 and l a secant line to Cl.
24
2.7 General Method
After creating the secant/tangent table, it is a matter of examining
this table to determine the sharply focused sets. For small values of q, we can
obtain subsets of Q that are sharply focused on a line l by using the following
methods:
Suppose q = 1 mod 4 and l is an exterior line or q = 1 mod 4 and
l is a secant line. Then depending on the congruence of q, we can construct
sharply focused sets of size either or where n is the odd number of
conjugate pairs. To construct two sharply focused sets of the above size, we
take either all the first elements of each conjugate pair listed in the incidence
table or all the second elements of each conjugate pair listed in the table.
If q = 1 mod 4 and l is a secant line or q = 1 mod 4 and l is
an exterior line, then there are several ways to create sharply focused sets
of various sizes. Let n be the even number of conjugate pairs created in the
construction of the table. To create two sharply focused sets of size  we use
the first  conjugate pairs in the incidence table to construct one set and the
remaining  conjugate pairs in the incidence table to construct another set.
This creates two sets of  elements of Q that are sharply focused on all the
exterior points of l. To create sharply focused sets of size 4, we use only two
conjugate pairs. For 1 < k < , the kfi1 conjugate pair in the incidence table
and the ( + k) conjugate pair in the incidence table will produce a sharply
focused set of size 4.
In PG(2,q), q odd, there exists sharply focused sets of size k, where k
is 3, 4 or a proper divisor of q + 1 and q 1 other than 2. Simmons [6] offers no
25
proof that these are the only possible sizes of sharply focused sets, in the next
chapter we provide a proof that this is always the case for this construction.
26
3. Proving the Divisibility Argument
The restrictions imposed on the length of Simmons paper [6] did
not allow him to provide proofs for statements concerning the secant/tangent
incidence tables and the division property that sizes of sharply focused sets
must divide either q + 1 or q 1. We shall provide the proofs that the size of
a sharply focused set constructed by his method must divide q + 1 or q 1.
3.1 A Relationship Between Points of fl and Points of l
Let T = GF(g), where q is an odd prime power, be a field and let a
be a symbol not in T. The construction used to create sharply focused sets in
PG(2,q) used the specific conic = {(j,j2,1)j E GF(g)} U {(0,1,0)}, where
the points of are denoted by j and a. When c is not a square in GF(q),
l is the exterior line y = c whose points {(j, c, l)j e GF(g)} U {(1,0,0)}
are denoted by j and a. The points of Q, are identified with the elements of
T U {a} by x <* x and the points of l are identified by x <* x. By means
of these identifications, the secant/tangent incidence table defines a binary
operation on T U {o}, which is given by:
i j = <
a
i
if i j
if = ~j
if j = a
j if i = a.
27
Proof: Let i = (i, i2,1) and j = (j, j2,1) be two points of f2. The line through
i and j is given by y = (i + j)x ij. Note: if i = j then this is a tangent line.
The point of intersection of this line and l is the point whose ^coordinate
is c. Setting this line equal to c and solving for x, we find that the point of
intersection has first coordinate provided i ^ j. If i is the same point
as j, then the line through these points is the horizontal line given by y = i2
which intersects y = c at the point a.
The points i and a form the secant line x i. The line x = i
intersects the line y = c at the point with xcoordinate i. Similarly, the points
a and j form the secant line x = j, which intersects y = c at the point with
xcoordinate j.
Thus, we have a way of relating the points of to those of l by
examining the relationship between the elements of jFU{a} under the operation
of . Let T* T U {a}. The following theorem proves that T* is a group
under .
Theorem 3.1.1. T* = {a} is a group under the binary operation .
Proof: To show that T* is a group under , we need to show that the following
three properties are satisfied.
associativity: i (j k) = [i j) k V i, j, k G J*
identity: there exists e G T* such that ie = ei = *VG^r*
inverse: for all i G T* there is a j Â£ T* such that = e.
a. (Associativity)
28
Case 1. Suppose i,j,k ^ a. Then
i {j k) = (i j) k
= (ij)k.
Case 2. Suppose i a. Then
a (j A;) = j k
{aj)k.
The other cases involving element a are similar.
Case 3. Suppose k = j. Then
* (j ~j)
i a
i
i^2
CJz
c+ij
i+j
j
( j) j
29
Again, the remaining cases of this type are similar.
So, for any choice of i,j, k G J*, associativity holds.
b. (Identity) Since a j = j = j a, the identity of T* is a.
c. (Inverse) Since i % a = i i, for all i G J7*, the inverse of i is i.
For c a square in GF(q), the secant line l given by y = c interesects
in the points x and y. Notice that in this case x = x and y = y. Let i and j be
two distinct points of fi other than x and y. If the secant line through % and j
intersects l at, say x, then since x is also on fi, we have three points, i, j, and
x that are collinear. But, since fl is an oval, no three points are collinear and
this can never happen. Now, observe that a and a are not in the intersection
of Q, and l. Since a = (0,1,0) of is not the same as the point a = (1,0,0) of
l. Thus, a and a will never be in the set Qnl {x,y}. So, the secant/tangent
incidence table is closed since the two points removed from both and l do
not appear anywhere in the table. We find that the set T* \ {x, y} is closed
and possesses inverses for each element as well as an identity. Thus, J7*\{x,y}
is a group under the same binary operation defined above. The proof when
l a secant line is essentially the same as the proof when l is an exterior line.
Thus, regardless of whether l is an exterior line or a secant line, the
secant/tangent incidence table of the points of Â£1 and l is isomorphic to the
multiplication table of a group.
3.2 Sharply Focused Sets Correspond to Cosets of a Group
The next thing that we show is that sharply focused sets correspond
to the cosets of T*.
30
Theorem 3.2.1. Sharply focused sets constructed in this way have sizes that
are divisors ofq +1 or q 1, other than 2. Furthermore, these sharply focused
sets correspond to cosets in T*.
Proof: Let H = {6i, b2, , &&} be a sharply focused set of Cl such that
\H\ = k. We want to examine the subarray whose rows and columns are
indexed by the elements in H. Let denote the (i, j)entry of this subarray.
Since H is a sharply focused set the are all elements of a size k subset of
T*.
Suppose crj = csj = c for some r and s. This implies that the secant
line determine by br and bj intersects l in the same point as the secant line
determined by bs and bj. Since c and bj determine a unique line, this implies
that br,bs,bj are all collinear. This is impossible since they are all points of
an oval. Thus, no element appears twice in a column.
A similar argument shows that no element appears twice in the same
row.
This implies that the subarray indexed by H under is a Latin
square, a k x k array whose entries all come from a set, S, of size k, with the
property that each element of S appears exactly once in each row and column
of the array.
Examine
H &i = {&i &i, &2 ~b\, j bk &i}
= {a, &2 ~bi, , bk &i}.
31
Let the entries indexed by id bi be d^, where
dij [pi bi) (bj Â£>i)
= (bi bj) 2&i
= (kj 2&i.
By adding the same constant to each of the c^s, we obtain a set
of d^'s which come from a set of k elements. The addition of a constant to
all entries does not affect the property of the array of being a Latin square.
Notice that
d\j = (bi bi) (bj b\)
= a (bj
= bj b\ Â£ id &i.
Thus, each entry of the subarray indexed by id bi is an element of id b\
since this is a Latin square. This implies that id bi is closed under .
Since Cl is finite and id bi is closed under the operation of ffi, id bi is
a subgroup, and so, id is a coset. Since the order of a coset is the same as
the order of a subgroup, Lagranges theorem tells us that the sizes of sharply
focused sets must divide q + 1 oi q 1.
Although the proofs for the claims in [6] concerning the structure of
the secant/tangent incidence tables can be explicitly given using the previous
two theorems and some number theoretical arguments, the proofs will not be
provided here.
32
4. Another Construction of Sharply Focused
Sets
Chapter 2 was devoted to using Simmons [6] method to construct
sharply focused sets in planes of order q. We will show that there is a method
of constructing sharply focused sets in planes of any prime power order, by
using subplanes in PG(2,g). Let II be a projective plane and let n1 be a
projective plane whose points form a subset of the points of II and which is
such that every line CJ of ir' is the intersection of n' and a line C of II. Then
7r' is called a subplane of II [1].
Figure 4.1. Subplane of a Projective Plane
Since we are dealing with projective planes that are constructed over
finite fields we have the following useful theorem pertaining to subfields of
finite fields.
Theorem. [5] For each divisor m of n, GF(pn) has a unique subfield of order
pm. Moreover, these are the only sub fields of GF(pn).
33
4.1 Even Characteristic Preamble
One of the properties fundamental to the previous construction, with
q odd, is the existence of conjugate pairs of points on an oval with respect to
some line l. Recall that a conjugate pair consists of two points on an oval
whose tangents intersected a given line at the same point. When p is even
all tangents to the oval intersect at the same point in the plane, known as
the nucleus. Therefore, conjugate pairs in planes of even order do not exist.
If sharply focused sets are to be found in planes of even order, an alternate
construction to the one provided by [6] that does not rely on conjugate pairs
will need to be developed.
4.2 Existence and Construction of Sharply Focused Sets in Planes
of Prime Power Order
The following theorem provides us with a new construction of sharply
focused sets when q is a prime power.
Theorem 4.3.1. In PG(2,pe), p a prime, there exists sharply focused sets of
sizes pm + l, pm, and pm 1 where m is a divisor of e.
Proof: Let m be any divisor of e. Then 7r = PG(2,pm) is a subplane
of PG(2,pe). JC = {(:r, x2,1)  x E GF(pm)} U {(0,1,0)} is a set of pm + 1
points in 7r, with the property that no three are collinear. Then JC is sharply
focused on any exterior line l of K in 7r. Since 7r is a subplane of PG(2, pe), l
can be extended to a unique line V in PG(2,pe). JC being sharply focused on l
and l' being the extension of l in PG(2,pe) implies that JC is sharply focused
on V in PG(2,pe).
34
Now, suppose that l is a tangent line to the oval K in it at a point
P, and define S = K\ {P}, so \S\ = pm. Then l is an exterior line to S and
by the proceeding paragraph, S is sharply focused on l \ {P}.
Finally, suppose that l is a secant line to the oval K, in 7r at the
points P and Q, and define M. = JC \ {P, Q}, so that \M\ = pm 1. Then l
is an exterior line to M. and by the first paragraph of the proof, A4 is sharply
focused on l \ {P, Q}.
Thus, in PG(2,pe) there exist sharply focused sets of sizes p + 1,
pm, and pm 1 when mis a divisor of e.
This theorem can be used to construct sharply focused sets in pro
jective planes of both even and odd prime power orders. If tt' is a subplane
in a projective plane II, we use the pm + 1 points of a conic in II that lie in
n' to form the desired sharply focused set, 1C, M., or S, of points. Since K is
sharply focused on any exterior line in 7r', S is sharply focused on the appro
priate tangent line in 7r', and M. is sharply focused on the appropriate secant
line, we can construct sharply focused sets of sizes pm, pm + 1, and pm 1.
According to the construction method used for q, an odd prime power,
in PG(2,25) we should find sharply focused sets of sizes 3, 4, 6, 8, 12, and 13.
Since PG(2,5) is a subplane of PG(2,25), we can use the previous theorem to
construct another sharply focused set, a set of size 5.
Define Q to be a conic in PG(2,5) and l a tangent line to Cl at a point
P. Let S Cl \ {P} and observe that l is an exterior line to S. By Theorem
4.3.1, S is a set of 5 points sharply focused on l and therefore S is a sharply
focused set of 5 points in PG(2,25).
35
4.3 Super Sharply Focused Sets in Planes of Even Order
All of the constructions encountered so far have focused on finding a
set of k points in a projective plane and a line l so that the (2) distinct lines
defined by pairs of the points in K, intersect l in only k distinct points. If we
restrict our focus to projective planes of only even order, then it is possible
for us to construct super sharply focused sets. A super sharply focused set is
a set of m points, no three collinear, that are sharply focused on m 1 points
of a line.
Let 7T be a plane of order 2m with a subplane of order 2n. Let Cl be a
hyperoval, an oval together with its nucleus N, in PG(2,2n). Cl contains 2n + 2
points. Let / be the secant line to Cl through any point P on Cl and N. Let
K = Cl \ {P, N}. Then the 2n points in K, generate (22) distinct lines that
intersect / in 2n 1 points. Namely, the 2n points of JC generate lines that
intersect l at every point except for P and N. Thus, in projective planes of
even order we can create super sharply focused sets.
There is one possible advantage for having super sharply focused sets
as opposed to sharply focused sets in the creation of this particular type of
secret sharing scheme. For instance, suppose the president of the bank hires
temporary tellers during the holidays to help with the seasonal increase in
banking transactions. Then with the addition of several new tellers, he would
like to incorporate them into the current design rather than produce a new
design to redistribute the shares of the combinations to the current employees
as well as the new ones. In this light, it makes sense to have access to spare
shares that can be distributed when new employees are hired. By using super
36
sharply focused sets instead sharply focused sets, we can increase the number
of shares given out to the participants of the scheme by one. In this manner,
super sharply focused sets are more practical than sharply focused sets.
4.4 A Sharply Focused and Super Sharply Focused Set in PG(2,16)
Let Cl = 1)  i G GF(16)} U (0,1,0)} be a conic in PG(2,16)
and a a generator of GF(16)\{0}. Then (o;5)2 = a10 and (a5)3 = a:15 = 1
implies that GF(4) = {a5, a10,1,0} C GF(16).
Then we have that the points of G PG(2,16) that lie in PG(2,4)
are (a5, a10,1), (a10, a5,1), (0,1,0), (1,1,1), (0,0,1). These five points gen
erate 10 secants and 5 tangents which intersect each other at the following
points: (0,1,1), (0, a10,1), (0,a5,l), (1,1,0), (1,0,1), (l,a:10,0), (a10,0,1),
(a10, a10,1), (a5,a5,l), (l,a5,l), (l,a10,l), (a5,0,1), (l,a5,0), (a10,1,1),
(a5,1,1). These points are sharply focused on the lines y = s+a5, y = x+o:10,
y = ct5x + 1, y = a5x + a5, y = awx + 1, and y = a10x + a10 in PG(2,4),
which are exterior lines in PG(2,4) and secant lines in 7r. So,
JC={(a*,a10,1), (a10, a5,1), (0,1,0), (1,1,1), (0,0,1)}
is a set of five points in PG(2,16) that is sharply focused on a line.
We can also obtain a sharply focused set of size 4 by following the
construction given in Theorem 4.3.1. Let Cl 1C be defined as above and let l
be a tangent line to at P in PG(2,4). Then S = fl\{P} is a sharply focused
set of size 4 with respect to the tangent line l.
To obtain a super sharply focused set in PG(2,16), we let Cl be the
hyperoval given by {(a5, a10,1), (a10, a5,1), (0,1,0), (1,1,1), (0,0,1), (1,0,0)}
37
where N = (1,0,0) is the nucleus. Then let l be a secant line through any of
the first five points listed for Cl and N and let S' be a set that contains the
points of Cl g l. Then by Theorem 4.3.1, S is sharply focused on l.
So, in PG(2,16), by using the results from Theorem 4.3.1, we can
construct sharply focused sets of sizes 5 and 4, as well as a super sharply
focused set of size 4.
4.5 Advantages and Disadvantages of Each Construction of Sharply
Focused Sets
A limiting factor to the use of subplanes for constructing sharply
focused sets is the number of subplanes that can be generated to obtain a
sharply focused set. For instance, in PG(2,pe), where e is a prime, then the
only divisors of e are 1 and itself. In this case, the generated subplanes are
the psubplane and the whole space. In the situation where we deal with the
psubplane, we can obtain sharply focused sets of sizes p 1, p, and p + 1.
In the situation where we are only dealing with the whole space, this method
does not produce any nontrivial sharply focused sets.
The construction method provided in [6] relies on the ability to find
conjugate pairs of an oval with respect to either an exterior line or a secant
line in the plane. This method does not work in planes of even order, since
conjugate pairs no longer exist. However, in projective planes of even order,
we can always produce super sharply focused sets that do not exist in planes
of odd order.
38
5. Further Studies
In this thesis we have examined two types of constructions for finding
sharply focused sets for use in secret sharing schemes. In this chapter, we would
like to mention a few problems and questions that have not been solved. These
remain to be studied further.
This papers offers two different constructions for finding sharply fo
cused sets. Whether or not there exist other constructions of sharply
focused sets still needs to be addressed.
The construction provided by Simmons [6] requires the use of conics
but the subplane construction does not. It still remains to be deter
mined whether or not sharply focused sets based on other types of arcs
in planes of even order greater than 16 exist. An exhaustive search
using the LunelliSce oval in PG(2,16) did not find any nontrivial
sharply focused sets.
PG(2,8) is the smallest case in which the subplane construction does
not give a sharply focused set. An exhaustive search found no sharply
focused sets in this plane, other than the trivial supersharply focused
quadrangles. Is this always the case for PG(2,2P), p a prime?
39
REFERENCES
[1] A. Albert and R. Sandler, An Introduction to Finite Projective
Planes, Holt, Rinehart, and Winston, Inc., 1968.
[2] E. F. Brickell, Some Ideal Secret Sharing Schemes, in Lecture
Notes in Computer Science, Advances in Cryptology EUROCRYPTO 89,
J. Quizquater and J. Vandewalle, eds., vol. 434, SpringerVerlag, April
1989, pp. 468490.
[3] H. Coxeter, Projective Geometry, SpringerVerlag, 1987.
[4] P. Dembowski, Finite Geometries, SpringerVerlag, 1968.
[5] J. A. Gallian, Contemporary Abstract Algebra, D.C. Heath and
Company, 1990.
[6] G. Simmons, Sharply Focused Sets of Lines on a Conic in PG(2,q),
in Congressus Numerantium, vol. 73, January 1990, pp. 181204.
[7] D. R. Stinson, Cryptography, Theory and Practice, CRC Press,
1995.
[8] W. Wallis, Combinatorial Designs, Marcel Dekker Inc., 1988.
40

PAGE 1
THE CONSTR UCTION OF GEOMETRIC THRESHOLD SCHEMES WITH PR OJECTIVE GEOMETR Y b y Leanne D. Holder B.S., Univ ersit y of Southern Mississippi, 1994 A thesis submitted to the Univ ersit y of Colorado at Den v er in partial fulllmen t of the requiremen ts for the degree of Master of Science Applied Mathematics 1997
PAGE 2
This thesis for the Master of Science degree b y Leanne D. Holder has been appro v ed b y William E. Chero witzo Stanley E. P a yne J. Ric hard Lundgren Date
PAGE 3
Holder, Leanne D. (M.S., Applied Mathematics) The Construction of Geometric Threshold Sc hemes With Projectiv e Geometry Thesis directed b y Associate Professor William E. Chero witzo ABSTRA CT In a secret sharing sc heme, a dealer has a secret and distributes shares of the secret to the participan ts. The shares are distributed in suc h a w a y that only certain subsets of the participan ts can com bine their shares to reco v er the secret. W e use projectiv e geometry to construct a secret sharing sc heme for whic h the shares are represen ted b y poin ts in a projectiv e 4space. A sharply focused set is a set of k poin ts, no three collinear, in a nite projectiv e plane in whic h the k 2 distinct secan ts formed b y this set in tersect a giv en line in exactly k poin ts. W e use sharply focused sets to design a sc heme so that certain subsets of participan ts can pool their shares to calculate the secret. Sev eral examples sho w ho w sharply focused sets can be used for diering sizes of the subsets of the participan ts that are allo w ed to calculate the secret. W e pro vide a proof that sharply focused sets obtained from a certain construction correspond to cosets of a group. This implies that the possible sizes of these sharply focused sets are divisors of the group order. Finally w e pro vide a new construction that uses subplanes in planes of prime po w er order. The previous construction method w orks only on planes of odd order, but the subplane construction method w orks in planes of both ev en and odd order. iii
PAGE 4
This abstract accurately represen ts the con ten t of the candidate's thesis. I recommend its publication. Signed William E. Chero witzo iv
PAGE 5
A CKNO WLEDGMENT There are man y people who deserv e more than just an ac kno wledgmen t on this page. The follo wing people deserv e man y h ugs. My advisor, Bill Cher owitzo for the man y geometric lessons on and o the rac k etball court. Ma y his seemingly bottomless w ell of patience not run dry un til long after I am nished with m y studies. My best friend, A llen Holder for his lo v e, encouragemen t, and patience o v er the past v e y ears. I consider m yself extremely blessed to ha v e him as m y h usband. My mom, Dianne M. Daniel for teac hing me ho w to \pla y the game" so w ell. Bring on the goldsh. My dad, Donnie L. Daniel for his profound and more often than not, practical w ords of wisdom.
PAGE 6
CONTENTS Chapter 1 Secret Sharing Sc hemes . . . . . . . . . . 1 1.1 A Generic Secret Sharing Sc heme In v olving the Emplo yees of a Bank . . . . . . . . . . . . 1 1.2 An In troduction to Projectiv e Geometry . . . . 2 1.3 Using Projectiv e Geometry to Construct A Secret Sharing Sc heme for a Bank . . . . . . . . . 6 2 Sharply F ocused Sets of lines in PG(2,q) . . . . . . 11 2.1 The Relationship Bet w een Sharply F ocused Sets and Secret Sharing Sc hemes for a Bank . . . . . . 11 2.2 Coordinate Represen tation of P oin ts and Lines in PG(2,q) 13 2.3 Construction of Sharply F ocused Sets in PG(2,q) . . 14 2.4 Tw o Examples with q = 11 . . . . . . . . 16 2.5 Tw o Examples with q = 13 . . . . . . . . 21 2.6 Structure of the Incidence T ables . . . . . . 23 2.7 General Method . . . . . . . . . . . 25 3 Pro ving the Divisibilit y Argumen t . . . . . . . 27 3.1 A Relationship Bet w een P oin ts of n and P oin ts of l . 27 3.2 Sharply F ocused Sets Correspond to Cosets of a Group 30 4 Another Construction of Sharply F ocused Sets . . . . 33 vi
PAGE 7
4.1 Ev en Characteristic Pream ble . . . . . . . 34 4.2 Existence and Construction of Sharply F ocused Sets in Planes of Prime P o w er Order . . . . . . . 34 4.3 Super Sharply F ocused Sets in Planes of Ev en Order . 36 4.4 A Sharply F ocused and Super Sharply F ocused Set in PG(2,16) . . . . . . . . . . . . . 37 4.5 Adv an tages and Disadv an tages of Eac h Construction of Sharply F ocused Sets . . . . . . . . . 38 5 F urther Studies . . . . . . . . . . . . . 39 References . . . . . . . . . . . . . . . . 40 vii
PAGE 8
FIGURES Figure 1.1 A Geometric Represen tation . . . . . . . . 7 1.2 Another Geometric Represen tation . . . . . . . 9 2.1 Structure of the Incidence T ables . . . . . . . 23 4.1 Subplane of a Projectiv e Plane . . . . . . . . 33 viii
PAGE 9
T ABLES T able 2.1 The Incidence T able for q = 11 and l an Exterior Line . 16 2.2 The Incidence T able for q = 11 and l a Secan t Line . . 20 2.3 The Incidence T able for q = 13 and l an Exterior Line . 21 2.4 The Incidence T able for q = 13 and l a Secan t Line . . 22 ix
PAGE 10
1. Secret Sharing Sc hemes In a secret sharing sc heme, a dealer has a secret and w ould lik e to giv e ev ery participan t of this sc heme a share of the secret. The shares should be distributed secretly so that no participan t kno ws the share of another participan t. Also, some time later a subset of the participan ts could pool their shares in an attempt to compute the secret. In some situations the dealer ma y w an t some of the subsets of participan ts to be able to compute the secret while other subsets of the participan ts to be unable to compute the secret [2, 7 ]. If the dealer is faced with this t ype of situation, then it is necessary to iden tify the appropriate subsets of participan ts before the shares are distributed. 1.1 A Generic Secret Sharing Sc heme In v olving the Emplo y ees of a Bank In a bank, there is a v ault that m ust be opened ev ery da y The presiden t of the bank emplo ys a n um ber of senior tellers and vice presiden ts but does not trust an y individual with the com bination to the v ault. So, a system needs to be designed in whic h certain com binations of these emplo y ees can open the v ault. One plan is to design a system, call it Design A, whereb y an y three senior tellers can open the v ault or an y t w o vice presiden ts can open the v ault. Although this appears as a practical solution in theory this system migh t not 1
PAGE 11
w ork in realit y if only t w o senior tellers and one vice presiden t sho w up for w ork [7]. A more practical design, Design B, is obtained b y adding to Design A the abilit y for t w o tellers and one vice presiden t to open the v ault. One m ust insure that no pair of senior tellers can open the v ault while allo wing an y vice presiden t in cooperation with a pair of senior tellers the abilit y to open the v ault [6]. If w e can do this, w e will ha v e obtained a secret sharing sc heme in whic h the dealer is the presiden t of the bank, the participan ts are the vice presiden ts and senior tellers, and the secret is the com bination to the v ault. 1.2 An In troduction to Projectiv e Geometry P eople who ha v e studied only Euclidean geometry regard it as an ob vious fact that t w o coplanar lines with a common perpendicular are p ar allel in the sense that, ho w ev er far w e extend them, they will remain the same distance apart. By stretc hing our imagination w e can conceiv e the possibilit y that this is merely a rst appro ximation: that if w e could extend them for millions or billions of miles w e migh t nd the lines getting closer together or farther apart. When w e look along a straigh t railroad w e get the impression that the t w o parallel rails meet on the horizon. An yho w, b y assuming that t w o coplanar lines alw a ys meet, w e obtain a system of propositions whic h is just as logically consisten t as Euclid's system [3]. Denition: [8] A nite pr oje ctive plane consists of a nite set P of poin ts and a set of subsets of P called lines, whic h satises the axioms (A1), (A2), and (A3): (A1) Giv en t w o poin ts, there is exactly one line that con tains both; (A2) Giv en t w o lines, there is exactly one poin t that lies on both; (A3) There are four poin ts, of whic h no three are collinear. In this setting, if a poin t lies on a line then the poin t is said to be incident with the line. Similarly the line is also said to be incident with the 2
PAGE 12
poin t. The axioms in the denition of a nite projectiv e plane are the k eys to the proofs of the follo wing lemmas dealing with the incidence of poin ts and lines in a nite projectiv e plane, Lemma 1.3.1. [1] If l 1 and l 2 are an y t w o distinct lines of then there is a poin t P in not inciden t with l 1 and l 2 Lemma 1.3.2. [1] An y t w o lines of are inciden t with the same n um ber of poin ts. Lemma 1.3.3. [1] An y t w o poin ts of are inciden t with the same n um ber of lines. In a nite projectiv e plane, there are a nite n um ber of poin ts on a line, a nite n um ber of lines through a poin t, and a nite n um ber of poin ts and lines in the plane. The previous three lemmas can be com bined with some results not men tioned here to obtain the follo wing importan t theorem on the exact n um bers for the abo v e incidences. Theorem 1.3.4. [1] L et b e a nite pr oje ctive plane. Then ther e is an inte ger q such that (1) Every p oint of is incident with exactly q + 1 lines; (2) Every line of is incident with exactly q + 1 p oints; (3) c ontains exactly q 2 + q + 1 p oints; (4) c ontains exactly q 2 + q + 1 lines. One commonly used construction for obtaining a projectiv e geometry denoted b y PG(n,q), starts with a v ector space. Let V(n+1,q) be a v ector space of rank n + 1 o v er a nite eld GF(q) where q is a prime po w er. The elemen ts of V(n+1,q) are the (n+1)tuples of the form ( x 0 ; x 1 ; ; x n ) where 3
PAGE 13
the x i are in GF(q). The poin ts, lines, and planes of PG(n,q) are the rank 1, 2, and 3 v ector subspaces in V where rank is the algebraic dimension of a v ector subspace. The geometric dimension of objects in PG(n,q) refers to the geometric concept where lines are 1dimensional, planes are 2dimensional and so forth. The rank and dimension alw a ys dier b y one, i.e., a rank 2 subspace corresponds to a line whic h is referred to as ha ving geometric dimension 1. In this construction, incidence is dened b y subspace con tainmen t. In the projectiv e geometry setting, lines are regarded as certain sets of poin ts and similarly planes can also be regarded as certain sets of poin ts. If a poin t lies on a line or in a plane, then the poin t is said to be incident with the line or plane. This is equiv alen t to the notion of a rank 1 subspace being con tained in a rank 2 or rank 3 subspace. When n = 2, the v ector space construction of a projectiv e geometry giv es a nite projectiv e plane that w e examined earlier. Ev ery plane arising from this construction satises the axioms giv en in the formal denition of a nite projectiv e plane. A w ell kno wn result from Linear Algebra states that if S and T are v ector spaces then rk( S ) + rk( T ) = rk( S \ T ) + rk( S [ T ) : Let = PG(4,q) be deriv ed from a rank 5 v ector space. Then w e can use the rank form ula to determine the possible incidences of lines and planes in First, w e examine the relationship bet w een t w o distinct planes, 1 and 2 in If 1 and 2 lie in a common 3dimensional subspace of (i.e., rank 4 v ector space) then the rank form ula tells us that these t w o planes 4
PAGE 14
in tersect in a line (a rank 2 v ector subspace). But, if 1 and 2 do not lie in a common 3dimensional subspace of b y the rank form ula, 1 and 2 m ust in tersect in a poin t, since their union w ould ha v e rank 4. Let P Q and R are be three noncollinear poin ts in Since eac h poin t has rank 1 and t w o poin ts determine a line, the rank form ula tells us that the smallest subspace con taining these 3 poin ts is a rank 3 subspace of whic h is a projectiv e plane. Next, w e examine the incidence relationship bet w een a line, l and a plane both in If l meets then l either meets in a poin t or is en tirely con tained within Suppose t w o poin ts of l are in Then since is a v ector subspace, the span of an y t w o poin ts that lie in also lies in In this case, it m ust be that l is en tirely con tained in W e will consider a special t ype of object called an o v al in the projectiv e plane, = PG(2,q). Similar to an o v al in Euclidean geometry an oval denoted n, in is set of q + 1 poin ts in suc h that no three of the poin ts are collinear. Since no three poin ts on n are collinear, if l is a line in then l can in tersect n in at most t w o poin ts and w e can classify l in the follo wing w a y: l is a tangent line to n pro vided j l \ n j = 1, l is a se c ant line to n pro vided j l \ n j = 2, l is an exterior line to n pro vided j l \ n j = 0. Let P be a poin t in Then P can be classied in three w a ys with respect to n: if P is on n then P is called an ovalp oint if P is not on n but on a tangen t line to n then P is called an exterior p oint and 5
PAGE 15
if P is neither on n nor on a tangen t line to n then P is called an interior p oint F or q odd, w e ha v e that an y exterior poin t to n has exactly t w o tangen ts through it. When q is ev en, there are no in terior poin ts, since ev ery poin t is on a tangen t line and all tangen ts with respect to n in tersect at a unique poin t in the plane, called the nucleus (or knot) of n. W e can use some of the incidence relationships bet w een l and a poin t P in to construct a secret sharing sc heme that satises the requiremen ts of Design A and Design B. This is accomplished b y assigning, as the shares eac h participan t receiv es in the sc heme, a special poin t in The poin ts of and l will represen t the shares distributed to the senior tellers and vice presiden ts and a poin t P will represen t the secret. W e will describe a method for distributing the shares in a projectiv e 4space so that only certain predetermined subsets of participan ts can calculate the secret. 1.3 Using Projectiv e Geometry to Construct A Secret Sharing Sc heme for a Bank W e are no w ready to examine the relationship bet w een the bank situation and some planes and lines in a projectiv e 4space. In both Design A and Design B, w e w ould lik e the secret to be represen ted b y a special poin t, P in a nite projectiv e plane, V d in The only information a v ailable about P to the senior tellers and vice presiden ts is that P is represen ted b y a poin t in V d V d is often referred to as the domain v ariet y and is generally public kno wledge. The shares belonging to the senior tellers and the vice presiden ts 6
PAGE 16
can be represen ted b y specially selected poin ts in By carefully selecting the poin ts that w e pic k to represen t shares, w e can alter the relationships bet w een l and V d as w ell as l and V d to create a geometric in terpretation of the secret sharing sc hemes associated with the bank problem. In Design A, the secret sharing sc heme that w e seek to dev elop is sometimes referred to as a t w olev el concurrence sc heme. A t w olev el concurrence sc heme requires concurrence of the participan ts in at least one of the t w o lev els before a con trolled action can tak e place. In this instance, the con trolled action is the pooling of the shares to calculate the com bination to the bank v ault. One concurrence lev el consists of the bank vice presiden ts and the other concurrence lev el consists of the senior tellers. An y t w o poin ts represen ting the shares of the vice presiden ts will dene a line l 2 that in tersects V d in only poin t P An y three poin ts represen ting the shares of the senior tellers should dene a plane 2 that in tersects V d in only poin t P In order to ha v e this propert y in the latter case w e m ust insure that no three of these poin ts are collinear. F or, if those poin ts w ere collinear, they w ould only dene a line and not the desired plane that w e require them to form. p l P G V dFigure 1.1. A Geometric Represen tation 7
PAGE 17
Suppose the line l formed b y t w o shares belonging to vice presiden ts in tersects the plane formed b y the three shares belonging to senior tellers in exactly one poin t. Also, suppose that and l both in tersect V d at the poin t P Then necessarily the in tersection of and l is P This is the situation as described in Design A. One poin t is not enough information to generate a line and t w o poin ts are not enough information to generate a plane. So, if l is not con tained in and only one vice presiden t and t w o senior tellers come to w ork, then there will not be enough information among the three participan ts to calculate the secret. T o a v oid this situation in Design A, w e created a new design, Design B, ha ving a stronger relationship bet w een l and other than their in tersection being only P If l and in tersect at more than one poin t, then l m ust lie in the plane Just as in Design A, l and both need to in tersect V d in the poin t P Since P is a poin t that represen ts the secret, the coordinates that represen t P are unkno wn to the senior tellers and vice presiden ts. Just one vice presiden t alone does not ha v e enough information to generate a line that in tersects V d at P since t w o poin ts are required to generate a line. Similarly an y t w o senior tellers do not ha v e enough information to generate a plane that in tersects V d at the poin t P since three poin ts are required to generate a plane. F urthermore, for this to be a perfect design, i.e., one in whic h no set of shares other than the predetermined ones can be com bined to obtain the secret, no pair of the poin ts in belonging to the senior tellers can be collinear with P F or three senior tellers to be able to pool their shares and calculate the secret, it is necessary for the poin ts represen ting the shares belonging to 8
PAGE 18
the senior tellers to ha v e the propert y that they are not collinear and all lie in the same plane, Th us, these poin ts are constrained to lie on an o v al. The poin ts represen ting the shares of the vice presiden ts m ust lie on a line that in tersects V d at P Since w e are adding the new restriction that a vice presiden t and an y t w o senior tellers ha v e the abilit y to pool their shares and calculate the secret, w e need the poin ts represen ting the shares belonging to the vice presiden ts to also lie in In order for an y vice presiden t to be able to calculate the secret with only t w o senior tellers, an y pair of poin ts in giv en to senior tellers ma y not be collinear with an y poin t on l belonging to an y of the vice presiden ts. With these restrictions, w e can be assured that one vice presiden t and an y pair of senior tellers can calculate the secret while at the same time insuring that no pair of senior tellers can calculate the secret alone. Figure 1.2 illustrates this concept. P p Wd a b e c l f g h V d GFigure 1.2. Another Geometric Represen tation In Figure 1.2, w e ha v e a geometric represen tation of a possible w a y to distribute the shares. Suppose that a and b are used as shares, then a third 9
PAGE 19
share, sa y c collinear with a and b could not be used in conjunction with a and b If this happened, then these three shares w ould generate a line instead of the desired plane necessary to reco v er P An y three shares distributed to the senior tellers should not be collinear, since these poin ts could not determine a plane. It is for this reason that w e require that the shares belonging to the senior tellers lie on an o v al of An example of a geometric perfect secret sharing sc heme for Design B w ould be to let the shares belonging to the vice presiden ts be represen ted b y the poin ts g and h and the shares belonging to the senior tellers be represen ted b y the poin ts a d and f Th us, the t w o vice presiden ts could calculate a line in tersecting V d at P and the three senior tellers could calculate the plane in tersecting V d at P while an y vice presiden t and t w o senior tellers could also calculate this plane in tersecting V d at P 10
PAGE 20
2. Sharply F ocused Sets of lines in PG(2,q) 2.1 The Relationship Bet w een Sharply F ocused Sets and Secret Sharing Sc hemes for a Bank In the previous bank illustration, the presiden t of a bank does not trust an y individual with the com bination to the v ault. A system w as designed that w ould allo w certain subsets of the emplo y ees to open the v ault, while other subsets w ere not able to open the v ault. F or instance, one vice presiden t and t w o senior tellers could open the v ault, but one vice presiden t and one senior teller could not. The system that w as designed in Chapter 1 to accommodate the presiden t's wishes had strict restrictions on what t ype of poin ts could represen t the shares belonging to the senior tellers and vice presiden ts. What happens to our design of a perfect secret sharing sc heme, when the presiden t adds more emplo y ees? W e are in terested in maximizing the n um ber of shares that can be distributed in so that an ecien t design can be constructed for an y n um ber of emplo y ees, suc h that: an y t w o vice presiden ts can com bine their shares to calculate the secret, an y three senior tellers can com bine their shares to calculate the secret, and an y one vice presiden t and an y t w o of the senior tellers can com bine their shares to calculate the secret. 11
PAGE 21
Since an y line in has q + 1 poin ts, there are at most q poin ts a v ailable to use as shares for the vice presiden ts, since one poin t of the line m ust be used to represen t the secret. In a projectiv e plane of odd order, there are at most q + 1 poin ts with the propert y that no three of the poin ts are collinear and these q + 1 poin ts form an o v al, n. P oin ts of n are ideal c hoices to represen t the shares belonging to the senior tellers. In the bank illustration, it w as necessary that no pair of poin ts in belonging to the senior tellers be collinear with P Also, for an y vice presiden t and an y t w o senior tellers to be able to pool their shares to calculate the secret, it w as necessary for the t w o shares belonging to the senior tellers not be collinear with the share belonging to the vice presiden t. Out of the q + 1 poin ts on l and the q + 1 poin ts on the o v al, ho w man y can be used as shares so that the incidences men tioned abo v e are a v oided? An y t w o shares giv en to the senior tellers determine a secan t line of n that in tersects l in a poin t. W e w ould lik e to determine the subsets of the q +1 poin ts of n whose secan ts in tersect l in the smallest n um ber of poin ts. Suc h subsets will pro vide the greatest n um ber of poin ts for use as shares for the vice presiden ts. Let K be a subset of n with k poin ts. There are k 2 distinct secan ts formed b y poin ts of K Let x represen t the n um ber of poin ts at whic h these secan ts in tersect l Observ e that, for a xed poin t on l there are at most b k 2 c secan ts of K that con tain this poin t. Clearly x b k 2 c k 2 If k = 2 m + 1, for some m the minim um v alue of x consisten t with this inequalit y is k but if k = 2 m k 1 is the minim um n um ber of shares that ma y not be distributed to the vice presiden ts. The lo w er bound of k 1 can only be ac hiev ed under 12
PAGE 22
special circumstances, whic h leads us to the follo wing denition. A set, K of k poin ts no three collinear in a nite projectiv e plane = PG(2 ; q ) is said to be sharply fo cuse d on a line l if the k 2 distinct lines dened b y pairs of the poin ts of K in tersect l in only k distinct poin ts [6]. By ha ving the shares belonging to the senior tellers be focused on as few poin ts as possible on l more shares can be distributed. That is, the remaining poin ts on l (other than P ) are then eligible to be used as shares for vice presiden ts. 2.2 Coordinate Represen tation of P oin ts and Lines in PG(2,q) Before w e dev elop a construction for nding sharply focused sets and presen t examples, w e need a coordinate represen tation of poin ts and lines in a projectiv e plane. Let F = GF ( p n ) be a nite eld of order p n p a prime and dene to be the projectiv e plane, PG(2 ; p n ). Then the poin ts of can be represen ted b y ordered triples of elemen ts from F with not all of the coordinates being zero. F or instance, a poin t P 2 can be represen ted b y ( x 1 ; x 2 ; x 3 ) where x i 2 F and at least one x i 6 = 0. Tw o poin ts ( x 1 ; x 2 ; x 3 ) and ( y 1 ; y 2 ; y 3 ) are said to be equiv alen t if there is a scalar 2 F ; 6 = 0, suc h that x i = y i for i = 1 ; 2 ; 3. So that an y poin t in can be represen ted in the form ( x 1 ; x 2 ; 1) ; (1 ; x 2 ; 0) ; or (0 ; 1 ; 0) where 1 is the iden tit y of F [1]. The lines in are dened in the same manner at the poin ts but instead of using ordinary paren thesis, w e use square brac k ets. So that if l is a line of l = [ x 1 ; x 2 ; x 3 ] with not all x i = 0. Tw o lines, [ x 1 ; x 2 ; x 3 ] and [ y 1 ; y 2 ; y 3 ] are equiv alen t if there is some scalar 2 ; 6 = 0, suc h that x i = y i for i = 1 ; 2 ; 3. A poin t, ( a; b; c ), and a line, [ x; y; z ], are inciden t 13
PAGE 23
if and only ax + by + cz = 0. F or m; x; y; k 2 F w e can represen t lines in our projectiv e plane as equations of lines used in the Euclidean Plane. The line y = mx + b can be written as [ m; 1 ; b ] and consists of all poin ts of the form ( x; mx + b; 1) as w ell as the poin t (1 ; m; 0). The line x = k has the form [ 1 ; 0 ; k ] and consists of all poin ts represen ted b y ( k; y; 1) and (0 ; 1 ; 0). The line [0 ; 0 ; 1], also referred to as the line at innity con tains all poin ts represen ted b y (1 ; x; 0) [1]. 2.3 Construction of Sharply F ocused Sets in PG(2,q) W e no w dev elop the construction used in [6] to create sharply focused sets in PG(2, q ) with q odd. Let n be an arbitrary conic in = PG(2, q ), q odd and l either an exterior line or a secan t line of n. A c onjugate p air of poin ts on n with respect to the line l are t w o poin ts A and B suc h that the tangen t lines to n at A and B both in tersect l in the same poin t. If l is an exterior line to n, then these conjugate pairs are determined b y rst computing the tangen t line equation for eac h poin t on n. These q + 1 tangen t lines in tersect l in exterior poin ts and will lie t w o at time on eac h exterior poin t of l If l is a secan t line to n, then l and n share t w o poin ts. Disregarding these t w o poin ts, the remaining q 1 poin ts of n can be classied in to conjugate pairs b y the same method used when l w as an exterior line. In the process of iden tifying conjugate pairs of poin ts on n, w e iden tify all the exterior poin ts on l so that the remaining poin ts on l m ust be in terior poin ts. 14
PAGE 24
The secan t/tangen t incidence table is the main tool used to iden tify sharply focused sets corresponding to l This is a square table whose ro ws and columns are indexed b y poin ts on n, not on l and whose en tries are indexed b y poin ts on l not on n. More specically let i and j be t w o poin ts on n n l If i 6 = j then these t w o poin ts determine a secan t line that in tersects l at the poin t in the ( i; j ) position of the table. Similarly if i = j then this poin t has a tangen t line that in tersects l at the poin t in the ( i; i ) position of the table. F or the ease of nding sharply focused sets, poin ts of n will be listed b y conjugate pairs in the table. T o look at specic examples, w e will mak e sev eral c hoices for the o v al as w ell as the line on whic h this o v al is to be sharply focused. First w e c hoose for our arbitrary o v al the specic conic, n = f ( j; j 2 ; 1) j j 2 GF ( q ) g [ f (0 ; 1 ; 0) g : The exterior and secan t lines that w e will be dealing with in the examples consist of the set of poin ts in that satisfy the equation y = c c 2 GF ( q ) along with the poin t (1 ; 0 ; 0). This line, l will be referred to as \ y = c ". If c is a square in GF( q ), then this will be a secan t line to n, since l and n will ha v e t w o poin ts in common. If c is not a square, then this will be an exterior line to n. F or simplicit y w e will use a compact notation to represen t poin ts of n as w ell as poin ts of l The poin t (0 ; 1 ; 0) 2 n will be represen ted b y a and the n um ber j will indicate the poin t ( j; j 2 ; 1) 2 n. Similarly the poin t (1 ; 0 ; 0) 2 l will be represen ted with a and the n um ber i will indicate the poin t ( j; c; 1) of l 15
PAGE 25
2.4 Tw o Examples with q = 11 The follo wing t w o examples for q = 11 help to clarify the procedure and also sho w ho w the secan t/tangen t incidence tables are used to obtain sharply focused sets. Example 2.4.1 Let q = 11 and, since 2 is not a square in GF(11), let l be the exterior line to n are giv en b y y = 2. Then the six exterior poin ts of l with respect to n, a 6, 5, 0, 4, 7, correspond to the follo wing conjugate pairs of poin ts on n: f a; 0 g f 5 ; 7 g f 6 ; 4 g f 3 ; 8 g f 9 ; 10 g and f 1 ; 2 g a 0 5 7 6 4 3 8 9 10 1 2 a a 0 5 7 6 4 3 8 9 10 1 2 0 0 a 7 5 4 6 8 3 10 9 2 1 5 5 7 6 4 a 0 9 10 1 2 3 8 7 7 5 4 6 0 a 10 9 2 1 8 3 6 6 4 a 0 5 7 1 2 3 8 9 10 4 4 6 0 a 7 5 2 1 8 3 10 9 3 3 8 9 10 1 2 0 a 7 5 4 6 8 8 3 10 9 2 1 a 0 5 7 6 4 9 9 10 1 2 3 8 7 5 4 6 0 a 10 10 9 2 1 8 3 5 7 6 4 a 0 1 1 2 3 8 9 10 4 6 0 a 7 5 2 2 1 8 3 10 9 6 4 a 0 5 7 T able 2.1. The Incidence T able for q = 11 and l an Exterior Line Notice that ev ery 2 2 bloc k in T able 2.1 con tains either exterior poin ts of l or in terior poin ts of l but not both. Also, observ e that this table can be partitioned in to four 6 6 bloc ks, where the t w o 6 6 bloc ks that constitute the main diagonal con tain only exterior poin ts and the t w o 6 6 bloc ks that constitute the o diagonal con tain only in terior poin ts of l W e are searc hing for a set of k poin ts on n whose secan t and tangen t 16
PAGE 26
lines in tersect l in exactly k poin ts. W e start the searc h for sharply focused sets b y taking a closer look at the t w o 6 6 bloc ks that lie on the main diagonal of the table. The bloc k that appears in the upper righ t corner of the table con tains only the six exterior poin ts of l and is created from the secan t and tangen t lines generated b y three distinct conjugate pairs of elemen ts in n, namely f a; 0 g f 5 ; 7 g and f 6 ; 4 g Similarly the bloc k that appears in the lo w er righ t corner of the table also con tains only the six exterior poin ts of l This bloc k is created from the secan t and tangen t lines generated b y the three other distinct conjugate pairs of elemen ts in n, f 3 ; 8 g f 9 ; 10 g and f 1 ; 2 g W e see that the t w o sets K 1 = f a; 0 ; 5 ; 7 ; 6 ; 4 g and K 2 = f 3 ; 8 ; 9 ; 10 ; 1 ; 2 g are both sharply focused on the six exterior poin ts of l W e can use certain elemen ts from the three conjugate pairs that generate eac h 6 6 bloc k on the diagonal of the table to create sharply focused sets of size three. Let K 1 and K 2 be the t w o sets of poin ts on n whose elemen ts are the rst elemen ts in eac h conjugate pair and the second elemen ts in eac h conjugate pair, respectiv ely Then w e ha v e that K 1 = f a; 5 ; 6 g and K 2 = f 0 ; 7 ; 4 g The secan t and tangen t lines created from K 1 in tersect the poin ts on l that lie in the (1 ; 1)position of eac h 2 2 subbloc k. Since there are only 3 poin ts of l in eac h corner of the 2 2 subbloc ks, K 1 is sharply focused on the poin ts a 5, and 6 of l A similar inspection with K 2 sho ws that this set is sharply focused on the poin ts 0, 7, and 4 of l Tw o more sharply focused sets of size six can be created in a similar fashion to the sharply focused sets of size three that w ere created. Let K 1 = f a; 5 ; 6 ; 3 ; 9 ; 1 g and K 2 = f 0 ; 7 ; 4 ; 8 ; 10 ; 2 g be sets constructed from extracting 17
PAGE 27
either the rst or second elemen ts in eac h conjugate pair listed across the top ro w of the table. Then, b y examining the (1 ; 1)position of eac h 2 2 subbloc k of the table, w e can see that K 1 is sharply focused on the poin ts a 5, 6, 3, 9, and 1 of l Similarly b y examining the (2 ; 2)en try of eac h 2 2 subbloc k of the table, w e see that K 2 is sharply focused on the poin ts 0, 7, 4, 8, 10, and 2. F or the nal searc h for sharply focused sets, w e will examine corresponding 2 2 subbloc ks in eac h of the four 6 6 bloc ks. More specically for i = 1 ; 2 ; 3, w e w an t to examine the bloc ks of size four created from the i th conjugate pair and the (3+ i ) th conjugate pair of poin ts on n listed across the top of the table. The secan t and tangen t lines generated b y the conjugate pairs, f a; 0 g and f 3 ; 8 g in tersect l in poin ts that lie in the four 2 2 subbloc ks located in the upper left corner of eac h of the 6 6 bloc ks. Since these four 2 2 subbloc ks con tain only four poin ts of l these t w o conjugate pairs form a sharply focused set of four poin ts. Similarly the t w o conjugate pairs, f 5 ; 7 g and f 9 ; 10 g generate secan t and tangen t lines whose in tersections with l are the poin ts located in the 2 2 subbloc ks located in the cen ter of eac h 6 6 bloc k. Since these four 2 2 subbloc ks con tain only four poin ts of l the t w o conjugate pairs of poin ts on n form a sharply focused set of size four. A nal sharply focused set of size four can be created from the remaining t w o conjugate pairs of the table. The pairs, f 6 ; 4 g and f 1 ; 2 g ha v e secan t and tangen t lines that in tersect l in exactly four poin ts. The poin ts of in tersection are in the 2 2 subbloc ks that are located in the bottom righ t 18
PAGE 28
corner of eac h 6 6 bloc k. Th us, these t w o conjugate pairs also form a sharply focused set of size four. Th us, b y inspecting the table, w e ha v e found sharply focused sets of sizes 6, 4, and 3. The sets of six poin ts f a; 0 ; 5 ; 7 ; 6 ; 4 g and f 3 ; 8 ; 9 ; 10 ; 1 ; 2 g of n are both sharply focused on the poin ts a 0, 5, 7, 6, and 4 of l The sets f a; 5 ; 6 ; 3 ; 9 ; 1 g and f 0 ; 7 ; 4 ; 8 ; 10 ; 2 g are sharply focused on a 5, 6, 3, 9, and 1 of l and 0, 7, 4, 8, 10, and 2 of l respectiv ely The sets of four poin ts f a; 0 ; 3 ; 8 g f 5 ; 7 ; 9 ; 10 g and f 6 ; 4 ; 1 ; 2 g of n are sharply focused on the poin ts a 0, 3, 8, the poin ts 6, 4, 1, 2, and the poin ts 5, 7, 9, 10 of l respectiv ely The sets of three poin ts f a; 5 ; 6 g and f 0 ; 7 ; 4 g of n are sharply focused on the poin ts a; 5 ; and 6 of l while the sets of poin ts f 3 ; 9 ; 1 g and f 8 ; 10 ; 2 g are sharply focused on the poin ts 0, 7, and 4 of l Example 2.4.2 Again, let q = 11 but instead of using the exterior line y = 2 to n, w e use a secan t line in the searc h for sharply focused sets. Since 5 is a square in GF(11), let l be the secan t line giv en b y y = 5. Since l is a secan t line to n, the t w o poin ts that lie on both l and n will be omitted from the table. The v e exterior poin ts of l with respect to n, a; 3 ; 6 ; 5 ; 8, ha v e the corresponding conjugate pairs of poin ts on n: f a; 0 g f 5 ; 1 g f 3 ; 9 g f 8 ; 2 g and f 6 ; 10 g Since w e ha v e an odd n um ber of conjugate pairs, this table cannot be divided in to four subbloc ks as w as done for the previous example. Notice that ev ery 2 2 bloc k in this table con tains exterior poin ts of l on the diagonal and in terior poin ts of l on the o diagonal. W e can nd sharply focused sets of size v e b y conducting a searc h 19
PAGE 29
a 0 5 1 3 9 8 2 6 10 a a 0 5 1 3 9 8 2 6 10 0 0 a 1 5 9 3 2 8 10 6 5 5 1 3 9 8 2 6 10 a 0 1 1 5 9 3 2 8 10 6 0 a 3 3 9 8 2 6 10 a 0 5 1 9 9 3 2 8 10 6 0 a 1 5 8 8 2 6 10 a 0 5 1 3 9 2 2 8 10 6 0 a 1 5 9 3 6 6 10 a 0 5 1 3 9 8 2 10 10 6 0 a 1 5 9 3 2 8 T able 2.2. The Incidence T able for q = 11 and l a Secan t Line similar to that in the previous example. Let K 1 = f a; 5 ; 3 ; 8 ; 6 g and K 2 = f 0 ; 1 ; 4 ; 2 ; 10 g be sets constructed from extracting either the rst or second elemen ts in eac h conjugate pair listed across the top ro w of the table. Then, b y examining the (1 ; 1)en try of eac h 2 2 subbloc k of the table, w e can see that K 1 is sharply focused on the poin ts a 5, 3, 8, and 6 of l Similarly b y examining the (2 ; 2)en try of eac h 2 2 subbloc k of the table, w e see that K 2 is also sharply focused on the poin ts a 5, 3, 8, and 6 of l By inspecting the table, it can be seen that sharply focused sets of size 5 exist and can obtained b y creating a set that con tains exactly one poin t from eac h conjugate pair of n. The sets f a; 5 ; 3 ; 8 ; 6 g and f 0 ; 1 ; 9 ; 2 ; 10 g of poin ts on n are both sharply focused on the v e poin ts a 5, 3, 8, and 6 of l Th us, for q = 11, there exists sharply focused sets of sizes 3, 4, 5, and 6. 20
PAGE 30
2.5 Tw o Examples with q = 13 Next, w e examine the v arious secan t/tangen t incidence tables for q = 13 when l is an exterior line and a secan t line. Example 2.5.1 Let q = 13 and since 2 is not a square in GF(13), let l be the exterior line to n giv en b y y = 2. Then the sev en exterior poin ts f a; 3 ; 6 ; 11 ; 1 ; 4 ; 8 g of l with respect to n ha v e the corresponding conjugate pairs of poin ts on n: f a; 0 g f 1 ; 2 g f 3 ; 5 g f 4 ; 7 g f 6 ; 9 g f 8 ; 10 g and f 11 ; 12 g a 0 1 2 3 5 4 7 6 9 8 10 11 12 a a 0 1 2 3 5 4 7 6 9 8 10 11 12 0 0 a 2 1 5 3 7 4 9 6 10 8 12 11 1 1 2 3 5 4 7 6 9 8 10 11 12 a 0 2 2 1 5 3 7 4 9 6 10 8 12 11 0 a 3 3 5 4 7 6 9 8 10 11 12 a 0 1 2 5 5 3 7 4 9 6 10 8 12 11 0 a 2 1 4 4 7 6 9 8 10 11 12 a 0 1 2 3 5 7 7 4 9 6 10 8 12 11 0 a 2 1 5 3 6 6 9 8 10 11 12 a 0 1 2 3 5 4 7 9 9 6 10 8 12 11 0 a 2 1 5 3 7 4 8 8 10 11 12 a 0 1 2 3 5 4 7 6 9 10 10 8 12 11 0 a 2 1 5 3 7 4 9 6 11 11 12 a 0 1 2 3 5 4 7 6 9 8 10 12 12 11 0 a 2 1 5 3 7 4 9 6 10 8 T able 2.3. The Incidence T able for q = 13 and l an Exterior Line This table is similar to the table in Example 2.2, since the sev en exterior poin ts of l lie on the main diagonal of eac h 2 2 subbloc k of the incidence table and the sev en in terior poin ts of l lie on the o diagonal of eac h 2 2 subbloc k of the table. By inspecting the table and conducting our searc h in a similar fashion to the searc h in Example 2.2, it can be seen that t w o 21
PAGE 31
sharply focused sets of size 7 exist. Namely the sets f a; 1 ; 3 ; 4 ; 6 ; 11 ; 8 g and f 0 ; 2 ; 5 ; 7 ; 9 ; 10 ; 12 g of poin ts from n are both sharply focused on the poin ts a 1, 3, 4, 6, 8, and 11 of l Example 2.5.2 Again, let q = 13 but instead of using the exterior line y = 2 to n, w e use a secan t line to aid in the searc h for sharply focused sets. Since 3 is a square in GF(13), let l be the secan t line giv en b y y = 3. Then, the six exterior poin ts a 8, 5, 0, 2, 11 of l with respect to n ha v e the corresponding poin ts as conjugate pairs: f a; 0 g f 5 ; 10 g f 8 ; 2 g f 6 ; 7 g f 3 ; 1 g and f 12 ; 10 g a 0 5 11 8 2 6 7 3 1 12 10 a a 0 5 11 8 2 6 7 3 1 12 10 0 0 a 11 5 2 8 7 6 1 3 10 12 5 5 11 8 2 a 0 3 1 12 10 6 7 11 11 5 2 8 0 a 1 3 10 12 7 6 8 8 2 a 0 5 11 12 10 6 7 3 1 2 2 8 0 a 11 5 10 12 7 6 1 3 6 6 7 3 1 12 10 0 a 11 5 2 8 7 7 6 1 3 10 12 a 0 5 11 8 2 3 3 1 12 10 6 7 11 5 2 8 0 a 1 1 3 10 12 7 6 5 11 8 2 a 0 12 12 10 6 7 3 1 2 8 0 a 11 5 10 10 12 7 6 1 3 8 2 a 0 5 11 T able 2.4. The Incidence T able for q = 13 and l a Secan t Line Observ e that w e can partition this table in to four 9 9 bloc ks. Also, notice that in this table pairs of the exterior poin ts lie in the 2 2 bloc ks on the main diagonal, and pairs of the in terior poin ts lie in the 2 2 bloc ks on the o diagonal. This table has a similar structure to the table in Example 2.1 and the searc h for sharply focused sets can be conducted in a similar fashion. 22
PAGE 32
By inspecting the table, it can be seen that there are sharply focused sets of size 6, 4, and 3. The sets f a; 5 ; 8 ; 6 ; 3 ; 12 g and f 0 ; 11 ; 2 ; 7 ; 1 ; 10 g of poin ts on n are both sharply focused on the poin ts a 5, 8, 6, 3, and 12 of l The sets f a; 5 ; 8 ; 6 ; 3 ; 12 g and f 0 ; 11 ; 2 ; 7 ; 1 ; 10 g are both sharply focused on the poin ts a 5, 8, 6, 3, and 12 of l The sets f a; 0 ; 6 ; 7 g f 5 ; 11 ; 3 ; 1 g and f 8 ; 2 ; 12 ; 10 g of poin ts of n are sharply focused on the poin ts a 0, 6, 7, the poin ts 8, 2, 12, 10, and the poin ts 5, 11, 3, and 1 of l respectiv ely The t w o sets f a; 5 ; 8 g and f 0 ; 11 ; 2 g of poin ts on n are both sharply focused on the poin ts a 5, and 8 of l Similarly the t w o sets f 6 ; 3 ; 12 g and f 7 ; 1 ; 10 g are both sharply focused on the poin ts 0, 11, and 2 of l Th us, for q = 13, there exists sharply focused sets of size: 3, 4, 6, and 7. 2.6 Structure of the Incidence T ables The structure of the incidence tables in Examples 2.12.4 can be somewhat explained. The 2 2 bloc ks of eac h incidence table are alw a ys of the form b a b a x yy xFigure 2.1. Structure of the Incidence T ables 23
PAGE 33
where the nature of x and y (with respect to n) are determined b y whether q 1mod 4. The poin ts b and a on n are conjugate pairs with respect to some line l That is, the tangen ts through both a and in tersect l at the same poin t. The same is true for b and If a secan t through a and b in tersects l at x then so does the secan t through and Similarly if a secan t through a and in tersects l at y then so does the secan t through and b [6]. The secan t/tangen t incidence tables will be one of t w o basic designs, depending on whether q 1 mod 4 and whether l is a secan t line or an exterior line to n. If q 1 mod 4 and l is an exterior line to n, then there will be an odd n um ber of conjugate pairs in n. Eac h 2 2 bloc k of the incidence table will ha v e the exterior poin ts of l on the diagonal and in terior poin ts of l lie on the o diagonal. The same structure occurs for q 1 mod 4 and l a secan t line to n. If q 1 mod 4 and l is an exterior line, then there will be an ev en n um ber, n, of conjugate pairs in n with respect to l The table can be partitioned in to four subbloc ks eac h of size n n If the conjugate pairs of n are arranged appropriately then the t w o subbloc ks that lie on the main diagonal of the table consist of 2 2 bloc ks of exterior poin ts of l and the t w o subbloc ks on the o diagonal consist of 2 2 bloc ks of in terior poin ts of l The same structure also occurs for q 1 mod 4 and l a secan t line to n. 24
PAGE 34
2.7 General Method After creating the secan t/tangen t table, it is a matter of examining this table to determine the sharply focused sets. F or small v alues of q w e can obtain subsets of n that are sharply focused on a line l b y using the follo wing methods: Suppose q 1 mod 4 and l is an exterior line or q 1 mod 4 and l is a secan t line. Then depending on the congruence of q w e can construct sharply focused sets of size either n +1 2 or n 1 2 where n is the odd n um ber of conjugate pairs. T o construct t w o sharply focused sets of the abo v e size, w e tak e either all the rst elemen ts of eac h conjugate pair listed in the incidence table or all the second elemen ts of eac h conjugate pair listed in the table. If q 1 mod 4 and l is a secan t line or q 1 mod 4 and l is an exterior line, then there are sev eral w a ys to create sharply focused sets of v arious sizes. Let n be the ev en n um ber of conjugate pairs created in the construction of the table. T o create t w o sharply focused sets of size n 2 w e use the rst n 2 conjugate pairs in the incidence table to construct one set and the remaining n 2 conjugate pairs in the incidence table to construct another set. This creates t w o sets of n 2 elemen ts of n that are sharply focused on all the exterior poin ts of l T o create sharply focused sets of size 4, w e use only t w o conjugate pairs. F or 1 k n 2 the k th conjugate pair in the incidence table and the ( n 2 + k ) conjugate pair in the incidence table will produce a sharply focused set of size 4. In PG(2, q ), q odd, there exists sharply focused sets of size k where k is 3, 4 or a proper divisor of q +1 and q 1 other than 2. Simmons [6] oers no 25
PAGE 35
proof that these are the only possible sizes of sharply focused sets, in the next c hapter w e pro vide a proof that this is alw a ys the case for this construction. 26
PAGE 36
3. Pro ving the Divisibilit y Argumen t The restrictions imposed on the length of Simmons' paper [6] did not allo w him to pro vide proofs for statemen ts concerning the secan t/tangen t incidence tables and the division propert y that sizes of sharply focused sets m ust divide either q + 1 or q 1. W e shall pro vide the proofs that the size of a sharply focused set constructed b y his method m ust divide q + 1 or q 1. 3.1 A Relationship Bet w een P oin ts of n and P oin ts of l Let F = GF ( q ), where q is an odd prime po w er, be a eld and let a be a sym bol not in F The construction used to create sharply focused sets in PG(2,q) used the specic conic n = f ( j; j 2 ; 1) j j 2 GF ( q ) g [ f (0 ; 1 ; 0) g where the poin ts of n are denoted b y j and a When c is not a square in GF(q), l is the exterior line y = c whose poin ts f ( j; c; 1) j j 2 GF ( q ) g [ f (1 ; 0 ; 0) g are denoted b y j and a The poin ts of n are iden tied with the elemen ts of F [ f a g b y x $ x and the poin ts of l are iden tied b y x $ x By means of these iden tications, the secan t/tangen t incidence table denes a binary operation on F [ f a g whic h is giv en b y: i j = 8 > > > > > > > > > > < > > > > > > > > > > : c + ij i + j if i 6 = j a if i = j i if j = a j if i = a: 27
PAGE 37
Proof: Let i = ( i; i 2 ; 1) and j = ( j; j 2 ; 1) be t w o poin ts of n. The line through i and j is giv en b y y = ( i + j ) x ij Note: if i = j then this is a tangen t line. The poin t of in tersection of this line and l is the poin t whose y coordinate is c Setting this line equal to c and solving for x w e nd that the poin t of in tersection has rst coordinate c + ij i + j pro vided i 6 = j If i is the same poin t as j then the line through these poin ts is the horizon tal line giv en b y y = i 2 whic h in tersects y = c at the poin t a The poin ts i and a form the secan t line x = i The line x = i in tersects the line y = c at the poin t with xcoordinate i Similarly the poin ts a and j form the secan t line x = j whic h in tersects y = c at the poin t with xcoordinate j Th us, w e ha v e a w a y of relating the poin ts of n to those of l b y examining the relationship bet w een the elemen ts of F[f a g under the operation of Let F = F [ f a g The follo wing theorem pro v es that F is a group under Theorem 3.1.1. F = F [ f a g is a gr oup under the binary op er ation Proof: T o sho w that F is a group under w e need to sho w that the follo wing three properties are satised. associativit y: i ( j k ) = ( i j ) k 8 i; j; k 2 F iden tit y: there exists e 2 F suc h that i e = e i = i 8 i 2 F in v erse: for all i 2 F there is a j 2 F suc h that i j = j i = e a. (Associativit y) 28
PAGE 38
Case 1. Suppose i; j; k 6 = a Then i ( j k ) = ( i j ) k = i c + jk j + k = c + i c + jk j + k i + c + jk j + k = c + k c + ij i + j k + c + ij i + j = c + ij i + j k = ( i j ) k: Case 2. Suppose i = a Then a ( j k ) = j k = ( a j ) k: The other cases in v olving elemen t a are similar. Case 3. Suppose k = j Then i ( j j ) = i a = i = i ( c j 2 ) c j 2 = c + ij i + j j = ( i j ) j: 29
PAGE 39
Again, the remaining cases of this t ype are similar. So, for an y c hoice of i; j; k 2 F associativit y holds. b. (Iden tit y) Since a j = j = j a the iden tit y of F is a c. (In v erse) Since i i = a = i i for all i 2 F the in v erse of i is i F or c a square in GF(q), the secan t line l giv en b y y = c in teresects n in the poin ts x and y Notice that in this case x = x and y = y Let i and j be t w o distinct poin ts of n other than x and y If the secan t line through i and j in tersects l at, sa y x then since x is also on n, w e ha v e three poin ts, i j and x that are collinear. But, since n is an o v al, no three poin ts are collinear and this can nev er happen. No w, observ e that a and a are not in the in tersection of n and l Since a = (0 ; 1 ; 0) of n is not the same as the poin t a = (1 ; 0 ; 0) of l Th us, a and a will nev er be in the set n \ l = f x; y g : So, the secan t/tangen t incidence table is closed since the t w o poin ts remo v ed from both n and l do not appear an ywhere in the table. W e nd that the set F n f x; y g is closed and possesses in v erses for eac h elemen t as w ell as an iden tit y Th us, F nf x; y g is a group under the same binary operation dened abo v e. The proof when l a secan t line is essen tially the same as the proof when l is an exterior line. Th us, regardless of whether l is an exterior line or a secan t line, the secan t/tangen t incidence table of the poin ts of n and l is isomorphic to the m ultiplication table of a group. 3.2 Sharply F ocused Sets Correspond to Cosets of a Group The next thing that w e sho w is that sharply focused sets correspond to the cosets of F 30
PAGE 40
Theorem 3.2.1. Sharply fo cuse d sets c onstructe d in this way have sizes that ar e divisors of q +1 or q 1 other than 2. F urthermor e, these sharply fo cuse d sets c orr esp ond to c osets in F Proof: Let H = f b 1 ; b 2 ; ; b k g be a sharply focused set of n suc h that j H j = k W e w an t to examine the subarra y whose ro ws and columns are indexed b y the elemen ts in H Let c ij denote the ( i; j )en try of this subarra y Since H is a sharply focused set the c ij are all elemen ts of a size k subset of F Suppose c rj = c sj = c for some r and s This implies that the secan t line determine b y b r and b j in tersects l in the same poin t as the secan t line determined b y b s and b j Since c and b j determine a unique line, this implies that b r ; b s ; b j are all collinear. This is impossible since they are all poin ts of an o v al. Th us, no elemen t appears t wice in a column. A similar argumen t sho ws that no elemen t appears t wice in the same ro w. This implies that the subarra y indexed b y H under is a Latin square, a k k arra y whose en tries all come from a set, S of size k with the propert y that eac h elemen t of S appears exactly once in eac h ro w and column of the arra y Examine H b 1 = f b 1 b 1 ; b 2 b 1 ; ; b k b 1 g = f a; b 2 b 1 ; ; b k b 1 g : 31
PAGE 41
Let the en tries indexed b y H b 1 be d ij where d ij = ( b i b 1 ) ( b j b 1 ) = ( b i b j ) 2 b 1 = c ij 2 b 1 : By adding the same constan t to eac h of the c ij 's, w e obtain a set of d ij 's whic h come from a set of k elemen ts. The addition of a constan t to all en tries does not aect the propert y of the arra y of being a Latin square. Notice that d 1 j = ( b 1 b 1 ) ( b j b 1 ) = a ( b j b 1 ) = b j b 1 2 H b 1 : Th us, eac h en try of the subarra y indexed b y H b 1 is an elemen t of H b 1 since this is a Latin square. This implies that H b 1 is closed under Since n is nite and H b 1 is closed under the operation of H b 1 is a subgroup, and so, H is a coset. Since the order of a coset is the same as the order of a subgroup, Lagrange's theorem tells us that the sizes of sharply focused sets m ust divide q + 1 or q 1. Although the proofs for the claims in [6] concerning the structure of the secan t/tangen t incidence tables can be explicitly giv en using the previous t w o theorems and some n um ber theoretical argumen ts, the proofs will not be pro vided here. 32
PAGE 42
4. Another Construction of Sharply F ocused Sets Chapter 2 w as dev oted to using Simmon's [6] method to construct sharply focused sets in planes of order q W e will sho w that there is a method of constructing sharply focused sets in planes of an y prime po w er order, b y using subplanes in PG(2 ; q ). Let be a projectiv e plane and let 0 be a projectiv e plane whose poin ts form a subset of the poin ts of and whic h is suc h that ev ery line L 0 of 0 is the in tersection of 0 and a line L of Then 0 is called a subplane of [1]. P p WFigure 4.1. Subplane of a Projectiv e Plane Since w e are dealing with projectiv e planes that are constructed o v er nite elds w e ha v e the follo wing useful theorem pertaining to subelds of nite elds. Theorem. [5] F or e ach divisor m of n GF( p n ) has a unique subeld of or der p m Mor e over, these ar e the only subelds of GF( p n ). 33
PAGE 43
4.1 Ev en Characteristic Pream ble One of the properties fundamen tal to the previous construction, with q odd, is the existence of conjugate pairs of poin ts on an o v al with respect to some line l Recall that a conjugate pair consists of t w o poin ts on an o v al whose tangen ts in tersected a giv en line at the same poin t. When p is ev en all tangen ts to the o v al in tersect at the same poin t in the plane, kno wn as the nucleus Therefore, conjugate pairs in planes of ev en order do not exist. If sharply focused sets are to be found in planes of ev en order, an alternate construction to the one pro vided b y [6 ] that does not rely on conjugate pairs will need to be dev eloped. 4.2 Existence and Construction of Sharply F ocused Sets in Planes of Prime P o w er Order The follo wing theorem pro vides us with a new construction of sharply focused sets when q is a prime po w er. Theorem 4.3.1. In PG( 2 ; p e ), p a prime, ther e exists sharply fo cuse d sets of sizes p m + 1 p m and p m 1 wher e m is a divisor of e Proof: Let m be an y divisor of e Then = PG(2 ; p m ) is a subplane of PG(2 ; p e ). K = f ( x; x 2 ; 1) j x 2 GF ( p m ) g [ f (0 ; 1 ; 0) g is a set of p m + 1 poin ts in with the propert y that no three are collinear. Then K is sharply focused on an y exterior line l of K in Since is a subplane of PG(2 ; p e ), l can be extended to a unique line l 0 in PG(2 ; p e ). K being sharply focused on l and l 0 being the extension of l in PG(2 ; p e ) implies that K is sharply focused on l 0 in PG(2 ; p e ). 34
PAGE 44
No w, suppose that l is a tangen t line to the o v al K in at a poin t P and dene S = K n f P g so j S j = p m Then l is an exterior line to S and b y the proceeding paragraph, S is sharply focused on l n f P g Finally suppose that l is a secan t line to the o v al K in at the poin ts P and Q and dene M = K n f P; Q g so that jMj = p m 1. Then l is an exterior line to M and b y the rst paragraph of the proof, M is sharply focused on l n f P; Q g Th us, in PG(2 ; p e ) there exist sharply focused sets of sizes p m + 1, p m and p m 1 when m is a divisor of e This theorem can be used to construct sharply focused sets in projectiv e planes of both ev en and odd prime po w er orders. If 0 is a subplane in a projectiv e plane w e use the p m + 1 poin ts of a conic in that lie in 0 to form the desired sharply focused set, K M or S of poin ts. Since K is sharply focused on an y exterior line in 0 S is sharply focused on the appropriate tangen t line in 0 and M is sharply focused on the appropriate secan t line, w e can construct sharply focused sets of sizes p m p m + 1, and p m 1. According to the construction method used for q an odd prime po w er, in PG(2,25) w e should nd sharply focused sets of sizes 3, 4, 6, 8, 12, and 13. Since PG(2,5) is a subplane of PG(2,25), w e can use the previous theorem to construct another sharply focused set, a set of size 5. Dene n to be a conic in PG(2,5) and l a tangen t line to n at a poin t P Let S = n n f P g and observ e that l is an exterior line to S By Theorem 4.3.1, S is a set of 5 poin ts sharply focused on l and therefore S is a sharply focused set of 5 poin ts in PG(2,25). 35
PAGE 45
4.3 Super Sharply F ocused Sets in Planes of Ev en Order All of the constructions encoun tered so far ha v e focused on nding a set of k poin ts in a projectiv e plane and a line l so that the k 2 distinct lines dened b y pairs of the poin ts in K in tersect l in only k distinct poin ts. If w e restrict our focus to projectiv e planes of only ev en order, then it is possible for us to construct super sharply focused sets. A sup er sharply fo cuse d set is a set of m poin ts, no three collinear, that are sharply focused on m 1 poin ts of a line. Let be a plane of order 2 m with a subplane of order 2 n Let n be a h ypero v al, an o v al together with its n ucleus N in PG(2,2 n ). n con tains 2 n +2 poin ts. Let l be the secan t line to n through an y poin t P on n and N Let K = n n f P; N g Then the 2 n poin ts in K generate 2 n 2 distinct lines that in tersect l in 2 n 1 poin ts. Namely the 2 n poin ts of K generate lines that in tersect l at ev ery poin t except for P and N Th us, in projectiv e planes of ev en order w e can create super sharply focused sets. There is one possible adv an tage for ha ving super sharply focused sets as opposed to sharply focused sets in the creation of this particular t ype of secret sharing sc heme. F or instance, suppose the presiden t of the bank hires temporary tellers during the holida ys to help with the seasonal increase in banking transactions. Then with the addition of sev eral new tellers, he w ould lik e to incorporate them in to the curren t design rather than produce a new design to redistribute the shares of the com binations to the curren t emplo y ees as w ell as the new ones. In this ligh t, it mak es sense to ha v e access to spare shares that can be distributed when new emplo y ees are hired. By using super 36
PAGE 46
sharply focused sets instead sharply focused sets, w e can increase the n um ber of shares giv en out to the participan ts of the sc heme b y one. In this manner, super sharply focused sets are more practical than sharply focused sets. 4.4 A Sharply F ocused and Super Sharply F ocused Set in PG(2,16) Let n = f ( i; i 2 ; 1) j i 2 GF (16) g [ (0 ; 1 ; 0) g be a conic in PG(2,16) and a generator of GF(16) nf 0 g Then ( 5 ) 2 = 10 and ( 5 ) 3 = 15 = 1 implies that GF(4) = f 5 ; 10 ; 1 ; 0 g GF (16). Then w e ha v e that the poin ts of n 2 PG(2 ; 16) that lie in PG(2,4) are ( 5 ; 10 ; 1), ( 10 ; 5 ; 1), (0 ; 1 ; 0), (1 ; 1 ; 1), (0 ; 0 ; 1). These v e poin ts generate 10 secan ts and 5 tangen ts whic h in tersect eac h other at the follo wing poin ts: (0 ; 1 ; 1), (0 ; 10 ; 1), (0 ; 5 ; 1), (1 ; 1 ; 0), (1 ; 0 ; 1), (1 ; 10 ; 0), ( 10 ; 0 ; 1), ( 10 ; 10 ; 1), ( 5 ; 5 ; 1), (1 ; 5 ; 1), (1 ; 10 ; 1), ( 5 ; 0 ; 1), (1 ; 5 ; 0), ( 10 ; 1 ; 1), ( 5 ; 1 ; 1). These poin ts are sharply focused on the lines y = x + 5 y = x + 10 y = 5 x + 1, y = 5 x + 5 y = 10 x + 1, and y = 10 x + 10 in PG(2,4), whic h are exterior lines in PG(2,4) and secan t lines in So, K = f ( 5 ; 10 ; 1) ; ( 10 ; 5 ; 1) ; (0 ; 1 ; 0) ; (1 ; 1 ; 1) ; (0 ; 0 ; 1) g is a set of v e poin ts in PG(2,16) that is sharply focused on a line. W e can also obtain a sharply focused set of size 4 b y follo wing the construction giv en in Theorem 4.3.1. Let n = K be dened as abo v e and let l be a tangen t line to n at P in PG(2,4). Then S = n nf P g is a sharply focused set of size 4 with respect to the tangen t line l T o obtain a super sharply focused set in PG(2,16), w e let n be the h ypero v al giv en b y f ( 5 ; 10 ; 1), ( 10 ; 5 ; 1), (0 ; 1 ; 0), (1 ; 1 ; 1), (0 ; 0 ; 1), (1 ; 0 ; 0) g 37
PAGE 47
where N = (1 ; 0 ; 0) is the n ucleus. Then let l be a secan t line through an y of the rst v e poin ts listed for n and N and let S be a set that con tains the poin ts of n 62 l Then b y Theorem 4.3.1, S is sharply focused on l So, in PG(2,16), b y using the results from Theorem 4.3.1, w e can construct sharply focused sets of sizes 5 and 4, as w ell as a super sharply focused set of size 4. 4.5 Adv an tages and Disadv an tages of Eac h Construction of Sharply F ocused Sets A limiting factor to the use of subplanes for constructing sharply focused sets is the n um ber of subplanes that can be generated to obtain a sharply focused set. F or instance, in PG(2 ; p e ), where e is a prime, then the only divisors of e are 1 and itself. In this case, the generated subplanes are the p subplane and the whole space. In the situation where w e deal with the p subplane, w e can obtain sharply focused sets of sizes p 1, p and p + 1. In the situation where w e are only dealing with the whole space, this method does not produce an y nontrivial sharply focused sets. The construction method pro vided in [6] relies on the abilit y to nd conjugate pairs of an o v al with respect to either an exterior line or a secan t line in the plane. This method does not w ork in planes of ev en order, since conjugate pairs no longer exist. Ho w ev er, in projectiv e planes of ev en order, w e can alw a ys produce super sharply focused sets that do not exist in planes of odd order. 38
PAGE 48
5. F urther Studies In this thesis w e ha v e examined t w o t ypes of constructions for nding sharply focused sets for use in secret sharing sc hemes. In this c hapter, w e w ould lik e to men tion a few problems and questions that ha v e not been solv ed. These remain to be studied further. This papers oers t w o dieren t constructions for nding sharply focused sets. Whether or not there exist other constructions of sharply focused sets still needs to be addressed. The construction pro vided b y Simmons [6] requires the use of conics but the subplane construction does not. It still remains to be determined whether or not sharply focused sets based on other t ypes of arcs in planes of ev en order greater than 16 exist. An exhaustiv e searc h using the LunelliSce o v al in PG(2,16) did not nd an y nontrivial sharply focused sets. PG(2,8) is the smallest case in whic h the subplane construction does not giv e a sharply focused set. An exhaustiv e searc h found no sharply focused sets in this plane, other than the trivial supersharply focused quadrangles. Is this alw a ys the case for PG(2,2 p ), p a prime? 39
PAGE 49
REFERENCES [1] A. Alber t and R. Sandler An In troduction to Finite Projectiv e Planes Holt, Rinehart, and Winston, Inc., 1968. [2] E. F. Brickell Some Ideal Secret Sharing Sc hemes in Lecture Notes in Computer Science, Adv ances in CryptologyEUR OCR YPTO '89, J. Quizquater and J. V andew alle, eds., v ol. 434, SpringerV erlag, April 1989, pp. 468{490. [3] H. Co xeter Projectiv e Geometry SpringerV erlag, 1987. [4] P. Dembo wski Finite Geometries SpringerV erlag, 1968. [5] J. A. Gallian Con temporary Abstract Algebra D.C. Heath and Compan y 1990. [6] G. Simmons Sharply Focused Sets of Lines on a Conic in PG(2,q) in Congressus Numeran tium, v ol. 73, Jan uary 1990, pp. 181{204. [7] D. R. Stinson Cryptograph y Theory and Practice CR C Press, 1995. [8] W. W allis Com binatorial Designs Marcel Dekk er Inc., 1988. 40
