Gus Simmons held 1994 IACR Distinguished Lecture

Abstract

The talk was about two related problems. The first is; given n participants, in how many ways can a secret piece of information or the ability to execute a controlled action, such as an encryption or decryption, be shared mong them. This can be restated as a purely logical question:

Given n logical variables, A, B, --- N, find all of the inequivalent logical expressions, Q, in disjunctive normal form on the uncomplemented literals satisfying:

1. Every variable occurs at least once in Q 2. Every term in Q contains at least two variables 3. No term is a superset of another

Two expressions, Q and Q', are equivalent if one can be transformed into the other by a permutation of the labels on the variables.

1. says that all participants are involved. 2. says that no participant knows the secret or is able to execute the controlled action alone and 3. merely acknowledges that it is not possible to enforce control for any superset of a set of participants who already have the joint capability to do so.

The solutions for n = 2, 3 and 4 are:

n = 2
AB

n = 3
ABC
AB + AC + BC
AB + AC

n = 4
ABCD

ABC + ABD + ACD + BCD
ABC + ABD + ACD
ABC + ABD
ABC + ABD + CD
ABC + AD
ABC + AD + BD
ABC + AD + BD + CD

AB + AC + AD + BC + BD + CD
AB + AC + AD + BC + CD
AB + AD + BC + CD
AB + AC + AD + BC
AB + AC + AD
AB + AC + CD
AB + CD

The second problem is to find a way to realize these schemes. There are many ways to do this, but I was interested in geometric realizations.

The setting for geometrical shared secret, or control, schemes is that the secret is an unknown point, x, on a publicly known line q. x is to be "indicated" by the intersection of q with various linear spaces spanned by designated sets of flats (shares) known privately to the n participants to the scheme. The minimal dimension of the space, L, spanned by all of the shares is at least 1, for a 2 out of n scheme, and at most n-1, for an n out of n scheme. Implementing a geometrical control scheme consists of identifying flats in L with the property that only designated sets of them span spaces intersecting q at x, and such that no space spanned by a set not including at least one of the designated sets lies on x. Under these conditions, the equivocation about the secret to any collection of participants that does not include one of the designated sets will be the same as it is to an outsider who only knows that the secret is a point on q.

Geometric control schemes are not unique. For example, a 2 out of n scheme could be realized by giving each participant as his share a different point, not x, on a line distinct from q that intersects q at x, or by giving each participant a different line, not on x, in a plane which intersects q at x. An optimal control scheme will be in the lowest dimension space possible since this minimizes the maximum amount of information in a share.

Solutions for n = 2, 3 and 4 are:

To avoid needless repetition the indicator space, L, will by definition be a space (line, plane, 3-space etc.) not containing q, but incident with q at point x.

n = 2
1. AB
L a line. A and B distinct points on L.

n = 3
2. ABC
L a plane. A, B, and C points in general position on L; such that no pair of them define a line on x.

3. AB + AC + BC

L a line. A, B and C distinct points on L

4. AB + AC

L a line. A and u distinct points on L. B and C are point u.

n = 4

5. ABCD

L a 3-space. A, B, C and D points in general position on L; such that no proper subset of them spans a space on x.

6. ABC + ABD + ACD + BCD

L a plane. A, B, C and D points in general position on L; such that no pair of them define a line on x.

7. ABC + ABD + ACD

L a plane. r a line in L not on x. B, C and D distinct points on r. A a point not on r; such that lines AB, AC or AD are not on x

8. ABC + ABD

L a plane. r a line in L not on x. u a point not on r. A and B points on r; such that lines uA and uB are not on x. C and D are u.

9. ABC + ABD + CD

L a plane. r and s distinct lines in L that intersect in point u; r on x and s not on x. A and B distinct points on s, not u. C and D distinct points on r, not u

10. ABC + AD

L a plane. r and s lines in L, not on x, that intersect on point u. A a point on r, not u. and C distinct points on s; such that lines AC and BC are not on x. D is s.

11. ABC + AD + BD

L a plane. r and s lines in L, not on x, that intersect on point u. A and B distinct points on r, not u. C a point on s, not u; such that lines AC and BC are not on x. D is s.

12. ABC + AD + BD + CD

L a plane. r a line in L not on x. A, B and C are three distinct non-collinear points in L, not on r; such that none of the lines AB, AC or BC are on x. D is r.

13. AB + AC + AD + BC + BD + CD

L a line. A, B, C, and D distinct points on L.

14. AB + AC + AD + BC + CD

L a line. A, C and u distinct points on L. B and D are u.

15. AB + AD + BC + CD

L a line. u and v distinct points on L. A and C are u. B and D are v.

16. AB + AC + AD + BC

L a plane. r and s distinct lines in L that intersect in point u; r on x and s not on x. B and C distinct points on r, not u. D is a point not on r or s such that BD and CD are not on x. A is s.

17. AB + AC + AD

L a line. A and u distinct points on L. B, C and D are u

18. AB + AC + CD

L a plane. r and s distinct lines in L that intersect in point u; r on x and s not on x. C is a point on r, not u. D is u. B is a point not on r or s. A is s

19. AB + CD

L a plane. r and s distinct lines in L that lie on x. A and B distinct points on r, not x, and C and D distinct points on s, not x.

Addendum:
I have been unable to reconstruct the theorem I "proved" linking the logical expression for a control scheme to a geometric realization of it, but what I recall was that I found an interpretation of the terms in the logical complement of Q with an identification of the flats which realized the scheme.

Very pretty result, but not quite true, which is why I said "proved". Ernie Brickell and someone at Bell Labs whose name I can't recall at the moment, although I think it was Josh something, showed using matroid theory there were shared secret schemes that had no linear (i.e. geometric) realizations. I did not know this at the time I gave the IACR distinguished lecture and claimed more than I had in fact proven. I vaguely recall they had to go to quite a few literals in the control expression before one existed that had no geometric realization.