Many researchers studied computationally-secure (verifiable) secret sharing schemes which distribute multiple secrets with a bulletin board. However, the security definition is ambiguous in many of the past articles. In this paper, we first review existing schemes based on formal definitions of indistinguishability of secrets, verifiability of consistency, and cheater-detectability. And then, we propose a new secret sharing scheme which is the first scheme with indistinguishability of secrets, verifiability, and cheater-detectability, and allows to share secrets with arbitrary access structures. Further, our scheme is provably secure under well known computational assumptions.

This paper presents a non-interactive verifiable secret sharing scheme (VSS) tolerating a dishonest majority based on data pre-distributed by a trusted authority. As an application of this VSS scheme we present very efficient unconditionally secure protocols for performing multiplication of shares based on pre-distributed data which generalize two-party computations based on linear pre-distributed bit commitments. The main results of this paper are a non-interactive VSS, a simplified multiplication protocol for shared values based on pre-distributed random products, and non-interactive zero knowledge proofs for arbitrary polynomial relations. The security of the schemes is proved using the UC framework.

We propose efficient secret sharing schemes realizing general access structures. Our proposed schemes are perfect secret sharing schemes and include Shamir's (k, n)-threshold schemes as a special case. Furthermore, we show that a verifiable secret sharing scheme for general access structures is realized by one of the proposed schemes.

We present a simple solution to secretly sharing a factoring witness (for given N) in a publicly-verifiable manner. Compared to the previous PVSS schemes to secretly sharing a factoring witness, the scheme enjoys the following properties: (1) the formal proofs of security can be given; (2) it is designed to be conceptually simpler; (3) it needs fewer communicated bits and, if not-so low exponent RSA (e.g., e > 219+1) is used in the previous schemes, fewer computations; (4) no general multi-party computation is required in the preparation phase.

This paper presents a non-interactive and optimally resilient distributed multiplication scheme. By non-interactive we mean that the players need to use outgoing communication channels only once without the need to synchronize with the other players as long as no disruption occurs. Our protocol withstands corrupt players up to less than the half of the players, so it provides optimal resiliency. Furthermore, the shared secrets are secure even against infinitely powerful adversaries. The security is proven under the intractability assumption of the discrete logarithm problem. Those properties are achieved by using an information theoretically secure non-interactive verifiable secret sharing as a kind of non-interactive proof system between a single prover and distributed verifiers. Compared to a former interactive solution in the same setting, the cost is an increase in local computation and communication complexity that is determined by the factor of the threshold used in the verifiable secret sharing.