Previous lecture
 		Table of contents
 		Next lecture

Lecture #3:  Secret sharing

Why Maple? I tried to explain again that it would be useful to have a machine to do arithmetic which would not be limited by the size of the numbers. Maple is one such. I then discussed how to use Maple a bit, including the fact that a command line interface was available if people did not want an x-window (for example, if people were using the program remotely).

Mr. Radimirovic came to class and I introduced him.

I then went back and discussed secret sharing. We had seen how to share secrets among 2 people in a group so that:

  1. Any 2 people would know enough to discern the secret.
  2. No 1 person would know enough.
I asked how to extend this. There were some suggestions. I asked that the suggestions be as reasonable and as easy to use as possible, or else people would not use them. We came across the idea of using a second degree polynomial to share a secret (again, here "secret" is synonymous with just a number), subject to these criteria:
  1. Any 3 people would know enough to discern the secret.
  2. No 2 people would know enough.
I had used Maple to compute a collection of points as ordered pairs of integers on a parabola, formatted the output, then printed and cut out these pairs [PDF|PS|TeX]. I asked people to assemble into groups and try to get the secret (the number 123). After a while at least one group got it. The groups were hampered by the fact that their calculators had problems dealing with the numbers, and maybe hampered by the difficulties of solving 3 linear equations in 3 unknowns. This could have been thought through better!

I extended the question, and asked how to share secrets so that it would take, say, 17 people to reconstruct the secret while any group of 16 would not have sufficient information. After a while we decided that a degree 16 polynomial would be good enough. People were worried about the computation involved (I said, "Your silicon slaves [e.g., computers] will do it") and also about the feasibility of carrying along the numbers. So Mr. Radimirovic displayed a smart card. He said that there was some memory and some computational capability in the card. The students learned a little bit about cards.

I told people that what we've been investigating was called "Shamir's Secret Sharing Scheme" and was about 15 to 20 years old. Mr. Radimirovic, an expert on these schemes, said that as far as he knew, every secret sharing scheme was essentially the same as this one.

Then I remarked that we'd seen that mathematically correct policies for sharing secrets could be implemented. A major part of this course would be to examine the contrasts between what some policy makers (e.g., governments, corporations, assertions by any speaker) might say is feasible (keeping records private) and what could be done mathematically. For example, the case of medical record privacy: in Britain, secret sharing is used to secure medical records. Monday's class, I remarked, would be a discussion of medical record privacy. I told them that I would prepare a page of links about the question, and send them e-mail. I did this, the next evening, with the link to the list of references on medical record privacy.

I gave out a homework assignment asking students to decrypt certain messages using the transposition scheme that I showed them in the previous class [PDF|PS|TeX]. I warned them that the messages included certain errors which actually arise in practice.

Previous lecture
 		Table of contents
 		Next lecture