Multiparty Computations
Information-Theoretically Secure Against an Adaptive Adversary Stefan Dziembowski January 2001 |

## Abstract:
In this thesis we study a problem of doing Verifiable Secret
Sharing (VSS) and Multiparty Computations in a model where private channels
between the players and a broadcast channel is available. The adversary is
active, adaptive and has an unbounded computing power. The thesis is based on
two papers [1,2].
In [1] we assume that the adversary can corrupt any
set from a given We then show an impossibility result indicating that a similar equivalence does not hold for Multiparty Computation (MPC): we show that even if protocols are given black-box access for free to an idealized secret sharing scheme secure for the access structure in question, it is not possible to handle all relevant access structures efficiently, not even if the adversary is passive and static. In other words, general MPC can only be black-box reduced efficiently to secret sharing if extra properties of the secret sharing scheme used (such as linearity) are assumed.
The
protocols of [2] assume that we work against a Another contribution of [2] is an attack against a Weak Secret Sharing Protocol (WSS) of [3]. The attack exploits the fact that the adversary is adaptive. We present this attack here and discuss other problems caused by the adaptiveness. All protocols in the thesis are formally specified and the proofs of their security are given. - [1]
- Ronald Cramer, Ivan Damgård, Stefan Dziembowski, Martin Hirt, and Tal Rabin. Efficient multiparty computations with dishonest minority. In Advances in Cryptology -- Eurocrypt '99, volume 1592 of Lecture Notes in Computer Science, pages 311-326, 1999.
- [2]
- Ronald Cramer, Ivan Damgård, and Stefan Dziembowski. On the complexity of verifiable secret sharing and multiparty computation. In Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, pages 25-334, May 2000.
- [3]
- Tal Rabin and Michael Ben-Or. Verifiable secret sharing and multiparty protocols with honest majority (extended abstract). In Proceedings of the Twenty First Annual ACM Symposium on Theory of Computing, pages 73-85, Seattle, Washington, 15-17 May 1989.
Available as |

Last modified: 2004-07-07 by webmaster.