<<

. 2
( 2)



Prev. page
Next Page Next Chapter

3.8 Cryptographic Protection of Databases


Sharing a Secret without Revealing the Shares
These schemes have a problem. When everyone gets together to reconstruct their
secret, they reveal their shares. This need not be the case. If the shared secret is a pri-
vate key (to a digital signature, for example), then n shareholders can each complete
a partial signature of the document. After the nth partial signature, the document
has been signed with the shared private key and none of the shareholders learns any
other shares. The point is that the secret can be reused, and you don™t need a trusted
processor to handle it. This concept is explored further by Yvo Desmedt and Yair
Frankel [483,484].
Verifiable Secret Sharing
Trent gives Alice, Bob, Carol, and Dave each a share or at least he says he does.
The only way any of them know if they have a valid share is to try to reconstruct the
secret. Maybe Trent sent Bob a bogus share or Bob accidentally received a bad share
through communications error. Verifiable secret sharing allows each of them to
individually verify that they have a valid share, without having to reconstruct the
secret [558,1235].
Secret-Sharing Schemes with Prevention
A secret is divided up among 50 people so that any 10 can get together and recon-
struct 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 [ 1531.
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 recon-
structing 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 [ 10041.

CRYPTOGRAPHIC PROTECTION OF DATABASES
3.8
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 com-
Page 74
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter

CHAPTER Basic Protocols
3


municate with one another, exchange ideas, and invite each other over for cucum-
ber 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 pos-
sible 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 [ 1851, allows statistics to be compiled on encrypted data.

<<

. 2
( 2)