Cryptography Reference
In-Depth Information
This mechanism, first proposed by Taher Elgamal, is very similar in
spirit to Diffie-Hellman key exchange.
The message can be decrypted by distributing the
k
values to
y
i
)
x
i
mod p
the group. Each person computes
(
g
and returns this
value to the group leader who multiplies them together.
y
a
=
y
1
y
2
)
x
1
(
)
x
2
...
n
)
x
n
mod p
(
.
The same set of keys can also generate digital signatures for the
group with a modified version of the digital signatures used with the
Diffie-Hellman-style public key system. Here are the steps:
g
g
(
g
1. The signers and the signature verifier agree on a challenge
value,
.Thisisusuallygeneratedbyhashingthedocumentbe-
ing signed. It could also be created by the verifier on the fly as a
true challenge.
c
2. Each member of the group chooses a random witness,
w
i
and
w
i
i
computes
g
mod p
.
3. Each member of the group computes
r
i
=
cx
i
+
w
i
and
r
i
mod p
g
.
4. The group discards the values of
w
i
and gathers together the
rest of the values in a big collection to serve as the signa-
ture. These values are:
{r
1
=
cx
1
+
w
1
,...r
k
=
cx
k
+
w
k
}
,
r
1
r
k
mod p}
{g
1
modp,...,g
,andtheproductof:
w
1
w
k
k
g
1
modp,...,g
mod p.
r
1
1
a
(
−
c)
g
5. Anyone who wants to check the signature can compute
r
k
mod p
... g
and make sure it is the same as the product of
w
1
w
k
k
g
1
modp,...,g
mod p
.
Similar solutions can be found using RSA-style encryption sys-
tems. In fact, some of the more sophisticated versions allows RSA
keys to be created without either side knowing the factorization.
[BF97, GRJK00, BBWBG98, CM98, WS99, FMY98]
4.5 Steganographic File Systems and Secret
Sharing
Secret sharing algorithms split information into a number of parts so
that the information can only be recovered if some or perhaps all of
the parts are available. The same basic algebra can also be used by
onepersontohidetheirdatasoonlythepersonwhoknowstheright
