Information Technology Reference
In-Depth Information
where
c
1
and shares of
c
2
are archived. Finally, a possibly tree-structured set
E
of escrow agencies exists, where each instance owns a (recursively generated)
share of the private key
d
.
The tree-based access structure can be achieved by recursively using thresh-
old cryptography. In order to be able to perform encryptions and decryptions
in a distributed way, we need the concepts of secure multi-party computation
(MPC) based on threshold security firstly introduced in [3]. There, any publicly
known mathematical formula with secret inputs can be computed by a qualified
set of instances (so called players) without revealing any information about the
secrets but giving them enough power to compute and reconstruct the output.
Basic solutions in this research field provide addition and multiplication of shared
secrets as well as public constants (scalars). Due to the fact, that multiplication
of two shared secrets is not very practical, we reduce our requirements to the
exclusive usage of addition and multiplication with scalars. To provide a better
understanding of our approach, the given protocols are only resistant against
passive adversaries who always stand to the rules (for considerations with active
adversaries we refer to our technical report [6]). Multi-party computation based
on threshold security requires secret sharing in several stages, which is also re-
quired for availability reasons of the ciphertext. This heads to the output of the
distributed encryption process which remains shared over
. While performing a
distributed decryption, the private key also always remains recursively shared by
using ElGamal threshold decryption (likely proposed in [1]). Different from [1]
we propose
d
to be tree-shared on the one hand and a very strong requirement
on the other hand: decryptions are only allowed to be performed over shares of
the ciphertext. As far as monitored instances are honest we can hamper several
ciphertext-based attacks up to a particular grade.
S
2 Fundamentals
Due to the usage of the ElGamal cryptosystem and its system parameters
p
and
q
, every computational step in this paper is either reduced modulo
q
(within ex-
ponents) or modulo
p
(within bases). For sake of simplicity we use a multi-pseudo
code that we developed especially for representing multi-party protocols. In order
to run such a protocol in pseudo-code representation the participating input and
output-players with the corresponding input and output-values (within brack-
ets) have to be specified. Every direct successor of the root of the tree is called
first-level-player (FLP). Although we shortly describe the used fundamentals,
we assume the reader to be familiar with the basic ElGamal cryptosystem [2] as
well as the paradigm of secure multi-party computation [4] and secret sharing
[9] respectively.
2.1 Shamir's Secret Sharing and Reconstruction
A secret value
s
of group
ZZ
q
is shared among a set of
n
players by using
Shamir's secret sharing [9] with threshold
t
(short:
s
→
(
s
1
,...,s
n
)). For unique
