Secure Multi-Player Protocols: Fundamentals, Generality, and Efficiency
Serge Fehr August 2003 |
Abstract:
While classically cryptography is concerned with the problem of
private communication among two entities, say players, in modern
cryptography multi-player protocols play an important role. And among
these, it is probably fair to say that secret sharing, and its stronger
version verifiable secret sharing (VSS), as well as multi-party
computation (MPC) belong to the most appealing and/or useful ones. The
former two are basic tools to achieve better robustness of cryptographic
schemes against malfunction or misuse by ``decentralizing'' the security from
one single to a whole group of individuals (captured by the term threshold cryptography). The latter allows--at least in principle--to
execute any collaboration among a group of players in a secure
way that guarantees the correctness of the outcome but simultaneously
respects the privacy of the participants.
In this work, we study three aspects of secret sharing, VSS and MPC, which we denote by fundamentals, generality, and efficiency. By fundamentals we mean the quest for understanding why a protocol works and is secure in abstract (and hopefully simple) mathematical terms. By generality we mean generality with respect to the underlying mathematical structure, in other words, minimizing the mathematical axioms required to do some task. And efficiency of course deals with the improvement of protocols with respect to some meaningful complexity measure.
We briefly summarize our main
results. (1) We give a complete characterization of black-box secret
sharing in terms of simple algebraic conditions on the integer sharing
coefficients, and we propose a black-box secret sharing scheme with minimal
expansion factor. Note that, in contrast to the classical field-based secret
sharing schemes, a black-box secret sharing scheme allows to share a secret
sampled from an arbitrary Abelian group and requires only black-box access to
the group operations and to random group elements. Such a scheme may be very
useful in the construction of threshold cryptosystems based on groups with
secret order (like RSA). (2) We show that without loss of efficiency, MPC can
be based on arbitrary finite rings. This is in sharp contrast to the
literature where essentially all MPC protocols require a much stronger
mathematical structure, namely a field. Apart from its theoretical value,
this can lead to efficiency improvements since it allows a greater freedom in
the (mathematical) representation of the task that needs to be securely
executed. (3) We propose a unified treatment of perfectly secure linear VSS
and distributed commitments (a weaker version of the former), and we show
that the security of such a scheme can be reduced to a linear algebra
condition. The security of all known schemes follows as corollaries whose
proofs are pure linear algebra arguments, in contrast to some hybrid
arguments used in the literature. (4) We construct a new unconditionally
secure VSS scheme with minimized reconstruction complexity in the setting of
a dishonest minority. This improves on the reconstruction complexity of the
previously best known scheme without affecting the (asymptotic) complexity of
the sharing phase. In the context of MPC with pre-processing, our
scheme allows to improve the computation phase of earlier protocols without
increasing the complexity of the pre-processing. (5) Finally, we consider
commitment multiplication proofs, which allow to prove a multiplicative
relation among three commitments, and which play a crucial role in
computationally secure MPC. We study a non-interactive solution which
works in a distributed-verifier setting and essentially consists of a
few executions of Pedersen's VSS. We simplify and improve the protocol, and
we point out a (previously overlooked) property which helps to construct
non-interactive proofs of partial knowledge in this setting. This
allows for instance to prove the knowledge of Available as PostScript, PDF. |