Cryptography Reference
In-Depth Information
5 generals to launch some missiles, then you can use a system with
17
5
dimensions. This can get a bit arcane, but themathematics
is possible.
×
13
×
4.4 Public-Key Secret Sharing
All of the algorithms in this section share one set of bits, the se-
cret. This secret may be used for anything, but it is probably go-
ing to be used as a key to unscramble some information encrypted
with a secret-key algorithm. The notion of splitting up authority and
responsibility can also be incorporated into public-key algorithms.
In these schemes, the actions for scrambling and unscrambling can
be split and controlled separately. The holder of one key controls
encryption and the holder of the other key controls decryption. If
secret sharing is combined with public-key encryption, one group
must agree to encrypt a message and another group must agree to
decrypt it.
Approaches like this are
often called threshold
decryption or threshold
signatures.
One easy solution is to combine anypublic-keyalgorithmwith
any of the secret sharing solutions. The keys are just collections of
bits and these collections can be split into arbitrary subcollections
using any basic secret splitting solution. This mechanism is perfectly
useful, but it has limitations. If a group of people get together to en-
crypt or decrypt a message, the key must be put together completely.
Once it is assembled, whoever put it together now controls it. The
secret sharing feature is gone.
This approach splits the ability to decrypt a public key message
among a group of
people. Anyone can send a message to the group,
but they all must agree to decrypt it. No information obtained from
decrypting one message can be used to decrypt the next. The system
relies on the strength of the discrete log problem. That is, it assumes
that given
k
x
g, p,
and
g
mod p
,itishardtofind
x
.
Similar techniques can
be used to produce
anonymous digital cash
and secure voting
solutions.
[Bra95b, Bra95a]
The private key consists of
k
values
{x
1
,...,x
k
}
that are dis-
tributed among the
members who will have control over the de-
cryption process. The public key is the value,
k
x
1
x
2
x
k
mod p
a
=
g
1
g
2
...g
,
where the values of
g
i
and
p
are publicly available numbers. The val-
ues of
g
i
may be generators of the group defined modulo
p
but the
algorithm will work with most random values less than
.
Amessage to the group is encrypted by choosing a random value,
p
y
1
mod p, g
y
2
modp,...g
y
k
mod p
y
,andcomputing
g
.Thenthevalue
y
a
is computed and used to generate a secret key for encryp-
tion themessage with an algorithm like AES. Themessage consists of
this encrypted data and the
mod p
y
1
mod p, g
y
2
modp,...g
y
k
mod p
k
values
g
.
