Information Technology Reference
In-Depth Information
reconstruction of
s
we have to interpolate at least
t
+ 1 shares using the formula
of Lagrange:
s
=
i
=1
=
j
=1
i
)
−
1
is the weight
of
s
i
corresponding to
s
. One big disadvantage of Shamir's secret sharing is the
fact that incorrect shares head to the reconstruction of a wrong secret. Although
we can never prevent from active misbehaviour of participating instances, it is
possible to detect them up to a particular grade (for more information see [4]).
λ
s
0
,i
,where
λ
s
s
i
·
j
·
(
j
−
0
,i
2.2 ElGamal Cryptosystem
Assuming the discrete-logarithm-based key generation has already taken place
resulting in the public key
e
and the private key
d
the encryption of a session
key
k
canbedonebycomputing
c
1
=
g
α
and
c
2
=
k
e
α
,where
α
·
∈
R
ZZ
q
.The
c
−d
1
decryption can be done by computing
k
=
c
2
·
.
2.3 Fair Tree-Shared Generation of a Private Key
In this paper we need a fair distributed generation of a (secret) value. We use
a simplified version of the key generation protocol based on discrete logarithms
proposed in [5]. The protocol in [5] is useful to generate a private key with-
out reconstructing it. However, we need a fair tree-structured generation of the
private key. Moreover, we need substitutability for every FLP within
in case
of absence which can be realized by recursively sharing computations over the
corresponding sub-trees. For lack of space we are forced to refer to our technical
report [7].
E
3 Distributed Computation of the ElGamal Cryptosystem
Based on our strict requirement not using multiplication of two shared secrets
we now try to split the ElGamal encryption and decryption function into several
parts respectively so that it can be performed by different sets of players without
revealing information about the session key
k
, the private key
d
, the ciphertext-
part
c
2
and randomness
α
up to a particular grade. We consider the ElGamal
cryptosystem as one common multi-party computation where the computation-
stage consists of three sub-stages: session key generation, encryption- and de-
cryption.Weassume,that
d
is already shared over
E
and players in
P
already
know
e
.
Input.
Each player
P
i
in
P
generates and shares two secret random values
k
i
→
(
k
i
1
,...,k
il
)and
α
i
→
(
α
i
1
,...,α
il
)over
P
.
Computation (Session Key Generation).
Each player in
P
i
combines the
received share-shares to a share of
k
[5]:
k
i
=
j
=1
k
ji
·
λ
k
i
0
,j
.
Computation (Encryption).
All players in
compute the encryption
over the shares of
k
,
α
and the constant
e
α
resulting in
c
2
that remains shared
P
and
S
