|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. Thats 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 .
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
Youve 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 thats 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 .
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 cant 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  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  handle searches on multiple indexes, but the idea is the same. The primary problem with this system is that its impossible to search for people when you dont know how to spell their name. You can try variant spellings until you find the correct one, but it isnt practical to scan through everyone whose name begins with Sch when looking for Schneier.
This protection isnt 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 , allows statistics to be compiled on encrypted data.
|Previous||Table of Contents||Next|