Secret Sharing Schemes:
An Application of Projective Geometry to Cryptography
Alexsis Venter
May 5, 2005
What is Cryptography?
What is a Secret Sharing Scheme?
Schemes of Different Access Structures
Howis Projective Geometry used in Secret Sharing?
Specific Examples
Benefits of Secret Sharing with
Projective Geometry
What is Cryptography?
Technically speaking, Cryptography is the process of designing systems to communicate over nonsecure channels. This is a wide field dealing withthings ranging from war secrets written in code to making an online purchase.
Basically, you have an input which is the message sent and an output which is the message received. What happens in between is the encryption. Although there are many complex and variable methods of encrypting a message, one basic idea uses a key to transform each bit of the message.
A cryptographer’s goal is to always improve upon the current techniques that keep our information secure and to be looking for ways in which the current procedures may be vulnerable.
What is a Secret Sharing Scheme?
A Secret Sharing Scheme is a method of distributing information in order to ensure that a previously determined set of users,and no other set, will be able to reconstruct the secret information. For example, you may want the users to be able to reconstruct the key mentioned above, or you may want them to be able to reconstruct the message itself. Each user is given a share of information which could be simply one part of the secret or a more complex piece of information somehow derived from the secret. The Access Structure is made up of the specific predetermined groups of users you are enabling to reconstruct the secret.
Schemes of Different Access Structures
Our text (Projective Geometry by Beutelspacher & Rosenbaum) in section 6.4 discusses three common schemes and gives the details of the implementation of the Projective Geometry methods.
1.The most basic scheme is the Threshold t-scheme. In this scenario, each user is given a share of “equal value.” Any t users can combine their shares to recreate the secret;any t-1 users may not. All users have equal rights and t users are required to reconstruct the secret.
2.Another scheme is the Compartment Scheme. Users here are separated into different classes and in each class you have a threshold scheme. Then in order to combine the different classes, you use another threshold scheme.
3.Finally, we will consider the Multilevel Scheme. In this situation, different types of users have different amounts of info or “pull” with regards to their share. Consider the following classic example: You are the President of a bank and you would like to split up the safe combination between different levels of employees including the Managers and Senior Tellers. You would like the following combinations of employees to be able to reconstruct the safe combination:
- Three Managers
- Four Senior Tellers
- Any combination of 4-k Senior Tellers and k Managers (k=1,2,3,4) More simply stated: any Manager can substitute in for a Senior Teller
In this setting, it is clear that the Managers have more power than the Senior Tellers.
How is Projective Geometry used in Secret Sharing?
Projective Geometry provides the mathematical structure or framework in which we can work out several algorithms. For example, some algorithms or procedures are performed using modular arithmetic and linear algebra concepts.
We will now look at some of the specific examples in the Projective Geometry framework and then later consider the benefits of these methods.
Specific Examples
Construction of a 2-Threshold Scheme
Step 1Use the Projective Space P = PG (2, q) and fix a line gЄP. Note that our dimension is 2 so we are working in a plane dealing with points (dim=0) and lines (dim=1).
Step 2Choose a point on g to be the secret. Call it X.
Step 3Choose a hyperplane H through X not containing g. Since we are in PG (2, q), a hyperplane is a line. So choose a line through X that is different from the line g. Call it H.
Step 4Choose a set of points in H that are in general position and contain X. Call this set S. I will explain general position later.
Step 5Distribute as shares the points xi in S not equal to X.
So how does it work?
Consider two users who will combine their shares. Let’s say user 1 and user 3 decide to unite. What they will have is two points (their shares) and the given line g. They will use their two points to determine the line H and then find H ∩g = X.
In this basic example, it is not clear why the points of S must be in general position. Here we review the relevant definitions and in the next example we will better understand the requirement.
From section 2.5 in our text, recall the following definition.
Let P be a projective space of dimension d. We say that a set S of at least d+1 points of P is in general position if any d+1 points of S form a basis of P.
The next definition in the section combined with Theorem 2.5.1 give us the fact that we can choose a set of points in general position by using a normal rational curve.
Construction of a 3-Threshold Scheme
Step 1Use the Projective Space P = PG (3, q) and fix a line gЄP. Note that our dimension is 3 so we are working in 3-space dealing with points (dim=0), lines (dim=1), and planes (dim=2).
Step 2Choose a point on g to be the secret. Call it X.
Step 3Choose a hyperplane H through X not containing g. Since we are in PG (3, q), a hyperplane is a plane. So choose a plane through X that doesn’t contain the line g. Call it H.
Step 4Choose a set of points in H that are in general position and contain X. Call this set S.
Step 5Distribute as shares the points xi in S not equal to X.
So how does it work?
Consider three users who will combine their shares. Let’s say user 1, user 2, and user 3 decide to unite. What they will have is three points (their shares) and the given line g. They will use their three points to determine the plane H (possible since shares were constructed as points in general position) and then find H ∩g = X.
You can now see how the general form works. A line is given which is open knowledge and the shares are points of a hyperplane in general position. So when enough users combine their shares, they will be able to recreate the hyperplane. And based on the construction of the hyperplane, the secret is found by intersecting the hyperplane with the line. As we move to threshold schemes where more users are required, the hyperplane will become a subspace of greater dimension. Also recall that our secret can always be represented as a point. We always start with a given line, and we construct a hyperplane not containing that line. So by Corollary 1.3.12, the hyperplane and the line intersect in a point.
Construction of a Compartment Scheme
Specific requirements of this example are that 2 compartments must unite after having two users in each compartment combine their shares.
Step 1Use the Projective Space P = PG (2+n, q) = PG (4, q), and fix a line gЄP. (n = the number of compartments)
Step 2Choose a point on g to be the secret. Call it X.
Step 3Choose a line h different from g, with h containing X.
Step 4Choose 2 (n) points on h not equal to X and call them X1, X2.
Step 5Through each point Xi, choose a line gi such that the subspace spanned by h with each of the gi’s and g are independent. [Let the set {<h, gi>, i = 1, 2, …, n} U {<h, g>} of lines be independent.]
Step 6Each member of compartment i is given a point on gi not equal to Xi.
So how does it work?
Well first off, consider a single compartment. When two users combine their shares, they will be able to reconstruct the gi line corresponding to their compartment. So they have two lines, the gi and the given line g. This is not enough to find the secret. What you need to do is calculate the subspace generated by all four users’ points and name this subspaceU. In this example, the two lines g1 and g2 are in U because 2 points on each line are in U. Sincelines g1 and g2 are in U, so are points X1 and X2. It follows that h is contained in U and then that X is contained in U. Since x Є (U ∩ g), we just need to know that X is the only point on g contained in U. This is guaranteed by the condition that the set of lines in the intersection of the three planes[<h, g1> U <h, g2> U <h, g>] are independent.
Construction of a Multilevel Scheme
We now construct the most complex scheme we will tackle today. We will construct a multilevel (2, 3) scheme with the following access structure interpretation. We will use the bank setting again and decide that
- 2 managers,
- 3 tellers,
- 2 tellers and 1 manager
will be able to reconstruct the vault combination.
Step1Use the Projective Space P = PG (3, q) and fix a line gЄP.
Step 2Choose a point on g to be the secret. Call it X.
Step 3Choose a line h different from g, with h containing X.
Step 4Choose a hyperplane H through h that only intersects g in X. Since we are in PG (3, q), a hyperplane is a plane, so H is a plane.
Step 5Distribute as shares for the managers the points miЄM on h different from X.
Step 6Distribute as shares for the tellers the points tiЄT in H subject to the following conditions:
- The union of T and {X} is a set of points of H in general position.
- Any subspace through 2 points of T contains no point of M.
So how does it work?
Consider each case of the access structure above.
Case 12 Managers combine their shares. The users will be able to determine the line h and compute h ∩ g to find X. Note, the intersection of two distinct lines is a point.
Case 23 Tellers combine their shares. The users will be able to determine the plane H and compute H ∩ g to find X. Note that the intersection of a line and a plane could be a point or the entire line. That is why we specified in the construction of H that it should only intersect g at the point X.
Case 32 Tellers and 1 Manager combine shares. The users will again be able to determine the plane H because they have 3 points in H. The two points from the tellers are distinct, and the manager’s point (on h in H) will not be collinear with them because of the 2nd condition in step six.
Benefits of Secret Sharing with Projective Geometry
- The probability of success for an attacker can be kept as small as you need it to be.
- If an attacker is going to try to guess the secret (a point on g), the probability is the same for each point: 1/ (q+1).
- Secret sharing schemes are easily implemented
- Participant management is simple – if you need to add more users, simply add more points on your line, etc. Removal can be a bit more difficult.