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 out of given
secrets, without revealing which ones. We also construct a non-interactive
distributed-verifier proof of *circuit satisfiability*, which--in
principle--allows to prove *anything* that can be proven without giving
away the proof.