| Previous | Table of Contents | Next |
Secret-Sharing Schemes with Prevention
A secret is divided up among 50 people so that any 10 can get together and reconstruct the secret. That’s easy. But, can we implement the same secret-sharing scheme with the added constraint that 20 people can get together and prevent the others from reconstructing the secret, no matter how many of them there are? As it turns out, we can [153].
The math is complicated, but the basic idea is that everyone gets two shares: a “yes” share and a “no” share. When it comes time to reconstruct the secret, people submit one of their shares. The actual share they submit depends on whether they wish the secret reconstructed. If there are m or more “yes” shares and fewer than n “no” shares, the secret can be reconstructed. Otherwise, it cannot.
Of course, nothing prevents a sufficient number of “yes” people from going off in a corner without the “no” people (assuming they know who they are) and reconstructing the secret. But in a situation where everyone submits their shares into a central computer, this scheme will work.
Secret Sharing with Disenrollment
You’ve set up your secret-sharing system and now you want to fire one of your shareholders. You could set up a new scheme without that person, but that’s time-consuming. There are methods for coping with this system. They allow a new sharing scheme to be activated instantly once one of the participants becomes untrustworthy [1004].
The membership database of an organization is a valuable commodity. On the one hand, you want to distribute the database to all members. You want them to communicate with one another, exchange ideas, and invite each other over for cucumber sandwiches. On the other hand, if you distribute the membership database to everyone, copies are bound to fall into the hands of insurance salesmen and other annoying purveyors of junk mail.
Cryptography can ameliorate this problem. We can encrypt the database so that it is easy to extract the address of a single person but hard to extract a mailing list of all the members.
The scheme, from [550,549], is straightforward. Choose a one-way hash function and a symmetric encryption algorithm. Each record of the database has two fields. The index field is the last name of the member, operated on by the one-way hash function. The data field is the full name and address of the member, encrypted using the last name as the key. Unless you know the last name, you can’t decrypt the data field.
Searching a specific last name is easy. First, hash the last name and look for the hashed value in the index field of the database. If there is a match, then that last name is in the database. If there are several matches, then there are several people in the database with the last name. Finally, for each matching entry, decrypt the full name and address using the last name as the key.
In [550] the authors use this system to protect a dictionary of 6000 Spanish verbs. They report minimal performance degradation due to the encryption. Additional complications in [549] handle searches on multiple indexes, but the idea is the same. The primary problem with this system is that it’s impossible to search for people when you don’t know how to spell their name. You can try variant spellings until you find the correct one, but it isn’t practical to scan through everyone whose name begins with “Sch” when looking for “Schneier.”
This protection isn’t perfect. It is possible for a particularly persistent insurance salesperson to reconstruct the membership database through brute-force by trying every possible last name. If he has a telephone database, he can use it as a list of possible last names. This might take a few weeks of dedicated number crunching, but it can be done. It makes his job harder and, in the world of junk mail, “harder” quickly becomes “too expensive.”
Another approach, in [185], allows statistics to be compiled on encrypted data.
| Previous | Table of Contents | Next |