Information Technology Reference
In-Depth Information
Player
Sent Messages
Multiplications
Exponentiations
P
i
(encryption)
O
(
l
+
m
)
O
(
l
+
m
)
O
(1)
S
i
(encryption)
−
O
(
l
)
O
(1)
S
i
(decryption)
O
(
n
)
O
(
n
)
O
(1)
E
i
(decryption)
O
(
n
)
O
(
n
+
m
)
O
(1)
The security of the protocols lies in the diculty of breaking the discrete log-
arithm problem and threshold multi-party computation with computational se-
curity (see [4]). An external adversary has to compromise at least
t
+1 players
in
to reconstruct
d
in order to
be able to decrypt
k
. The distributed storage of
c
2
has two effects: firstly, the
availability of ciphertext and secondly, the restriction of several ciphertext-based
attacks. However, if an adversary is able to force any player in
S
to reconstruct
c
2
and at least
t
+1 FLP in
E
to compute
and publish
c
2
the second advantage disappears. Considering the decryption of
k
, it is obvious that internal adversaries (
P
) do not really have more power
than external ones. Performing ciphertext-based attacks is not possible for up
to
t
players in
S
or
E
S
and
E
(if
P
remains honest).
4Con lu on
We proposed a key escrow system that fulfils the requirements stated in section 1
by using a particular version of distributed ElGamal to achieve several security-
properties (discussed in section 3.1). For a detailed description of our proposal
including more applications we refer to our technical report [8]. An extended
version considering active adversaries can be found in our technical report [6].
References
1. Desmedt, Y., Frankel, Y.: Threshold Cryptosystems. Adv. in Crypt.: CRYPTO'89,
Springer-Verlag (1990) 307-315
2. ElGamal, T.: A Public-Key Cryptosystem and a Signature Scheme Based on Dis-
crete Logarithms. Adv. in Crypt.: CRYPTO'84, Springer-Verlag (1985) 10-18
3. Goldreich, O. et al: How to play any mental game - a completeness theorem for
protocols with honest majority. Proc. 19th ACM STOC (1987) 218-229
4. Hirt, M.: Multi-Party Computation: Ecient Protocols, General Adversaries,
and Voting. Ph.D. thesis. ETH Series in Information Security and Cryptography,
Hartung-Gorre Verlag, Konstanz (2001)
5. Pedersen, T.: A threshold cryptosystem without a trusted party. Adv. in Crypt.:
EUROCRYPT'91, LNCS, Vol.547 (1991) 522-526
6. Schaffer, M.: Hierarchical Key Escrow with Active Adversaries. Technical Report
TR-syssec-05-03, University of Klagenfurt, Austria (2005)
7. Schaffer, M.: Tree-shared Generation of a Secret Value. Technical Report TR-syssec-
05-01, University of Klagenfurt, Austria (2005)
8. Schaffer, M., Schartner, P.: Hierarchical Key Escrow with Passive Adversaries.
Technical Report TR-syssec-05-02, University of Klagenfurt, Austria (2005)
9. Shamir, A.: How to share a secret. Comm. of the ACM, Vol.11 (1979) 612-613
