In a secret sharing scheme, a secret s is divided into multiple shares and distributed among n participants. As more shares are collected, the mutual information between the secret and the shares increases monotonically. In the perfect case, the best known explicit lower bound on the share size is given by $\frac{{{2^k} - 1}}{k} \cdot H(s)$, where H(s) is the entropy of the secret and k is the largest integer such that n ≥ 2k+k−2. This paper considers the non-perfect case, in which each share reveals at most a $\frac{1}{L}$ fraction of the secret's entropy, for an integer L > 1. A prior result in this setting provides a lower bound of $\frac{{{2^k} - 1}}{{kL}} \cdot H(s)$, under the condition n ≥ 2k+k+L−3. We provide a new lower bound that approaches the perfect-case bound, namely $\frac{{{2^k} - 2 + 1/L}}{k} \cdot H(s)$, which holds under the condition n ≥ 2k+k+2L−4. The proof generalizes perfect-case techniques by increasing the number of participants by 2(L−1). These results refine our understanding of the trade-off between share size and information leakage in non-perfect secret sharing. In particular, we construct non-perfect access structures that nearly attain the perfect lower bound with fewer participants than previous non-perfect bounds, thus complementing and extending prior work.

Non-interactive secure multiparty computation is a method to share and compute a private function$f$among$n$parties holding private inputs xi with 1$n$in the information theoretical setting. Each party locally computes a message from a share of$f$and send it to a referee in parallel. The referee obtains the output f (xi,… , xn) while keeping$f$and xi private other than what can be inferred from the output. The communication complexity is evaluated by the maximum length of shares and messages. In the previous work, several kinds of function families, upper and lower bounds have been improved and the only gaps remaining are for the group products and the Abelian programs (including symmetric functions). This paper improves the communication complexity of both function families towards the optimum by deriving a new lower bound for the group products that matches the previous upper bound (up to a constant factor) and the first asymptotically optimal upper bound for the Abelian programs.

This paper studies the communication complexity of sharing and computing a private function f among n parties holding private inputs xiwith 1 ≤ i ≤ n in the information theoretical setting. Each party locally computes a message from a share of f and send it to a referee in parallel. The referee obtains the output f (x1,…,xn) while keeping f and xiprivate other than what can be inferred from the output. The communication complexity is evaluated by the maximum length of shares and messages. First, a lower bound on the communication complexity is presented. In particular, the length of the message is lower bounded by a restricted f. Second, the lower bound increases as the robustness level becomes larger, indicating a tradeoff between efficiency and robustness. For well-known families of functions, the lower bounds are instantiated, some of which matches the latest upper bounds up to a constant factor.

The wiretap channel is a setting where one aims to obtain information-theoretic security of communicated data under the sole assumption that the channel from a sender Alice to an eavesdropper Eve is “noisier” than that from Alice to a receiver Bob. However, in practice, the difference between the two channels in terms of noise may be much smaller because of the wide spread application of high-performance communication technologies. Thus, establishing a wiretap channel over real channels is a challenging task. In this paper, we report a wiretap channel in the form of a “protocol” (a so-called virtual wiretap channel) realized by using a highly precise wireless clock-synchronization technology called the wireless two-way interferometry (abbreviated as Wi-Wi). Wi-Wi technology has already been implemented in wireless communication devices, and it measures the clock time difference and signal propagation time in a situation where the precisions of both values are mutually affected. That is, Alice or Bob can induce a noise on Eve's clock time difference measurement by physically introducing noise in the signal propagation time between Alice and Bob. We analyzed the proposed wiretap channel referred to as the Wi-Wi wiretap channel experimentally, and estimated its parameters (e.g., the error probabilities). We confirmed that the Wi-Wi wiretap channel works well as a virtual wiretap channel by simulating and experimentally demonstrating a well-known, provably secure, optimal wiretap code over it. The results show that Wi-Wi wiretap channel can serve as a physical layer security, useful for synchronized Internet of Things (IoT) devises.

A secret sharing scheme is said to be d-multiplicative if the scheme allows the players to multiply shared d secrets by locally converting their shares into an additive sharing of the product. This paper considers the most general setting where d secrets are independently shared by different adversary structures (hybrid) and a partial information can be leaked (non-perfect) and presents a necessary and sufficient condition for d-multiplication to be possible. In particular, even for the extreme case that the i-th secret is known by all but the i-th player who has partial information on the secret (e.g., all but one bit), d-multiplication is impossible.

A secret-sharing scheme is d-multiplicative if it allows the players to multiply d (rather than two) shared secrets (without recovering them) by locally converting their shares into an additive sharing of the product. In this work, the d-multiplicative secret-sharing (MSS) is extended to a hybrid MSS (HMSS), which is mainly designed for sharing d secrets against different access structures. A necessary and sufficient condition for n-player d-HMSS schemes to exist is presented. The condition is necessary for arbitrary (possibly inefficient or even nonlinear) secret-sharing schemes.

An important problem in secret sharing schemes is minimizing the share size. For (k, n)-threshold schemes and (k, L, n)-ramp schemes, constructions that minimize the share size are known. This paper presents optimal constructions for a more general class of access structures in which subsets with the same cardinality have the same amount of information about the secret. We refer to schemes with such uniform access structures as uniform secret sharing. We first derive a tight lower bound for share entropy and then present an optimal construction. Our lower bound exceeds that previously reported. The optimal construction encodes the secret value using one or more ramp schemes.

A d-multiplicative secret sharing (d-MSS) scheme allows the players to multiply d shared secrets without recovering the secrets by converting their shares locally into an additive sharing of the product. It has been proved that the d-MSS among n players is possible if and only if no d unauthorized sets of players cover the whole set of players (type Qd). Although this result implies some limitations on SS in the context of MPC, the d-multiplicative property is still useful for simplifying complex tasks of MPC by computing the product of d field elements directly and non-interactively without any setup. This paper aims to improve the usefulness of the d-MSS by enhancing the security against malicious adversaries. First, we introduce the notion of verifiably multiplicative SS, verifiably MSS for short, which is mainly formalized for detecting malicious behaviors. Informally, an SS scheme is verifiably d-multiplicative if the scheme is d-multiplicative and further enables the players to locally generate a share of a proof that the summed value is correct (i.e., the product of d shared secrets). Secondly, we prove that there is no error-free verifiably MSS scheme whose decoder of the proof is additive, and that by accepting an error probability that can be chosen arbitrarily, there exists a verifiably d-MSS scheme realizing a given access structure if and only if the access structure is of type Qd. In the proposed construction, each share of a proof consists of only two field elements. This result means that we can efficiently achieve the optimal resiliency of the standard d-MSS even against malicious adversaries. We note that by allowing a general class of decoders that includes a linear one, there is an error-free verifiably d-MSS scheme if the access structure is of type Qd+1. Finally, we generalize the d-multiplicative property to a d-or-less version where the number d' of multiplied secrets with d' ≤ d is not known in advance. We show that a d-or-less MSS scheme can be constructed from any d-MSS scheme of the same access structure with a constant overhead, and the feasibility of (verifiably) d-MSS implies that of (verifiably) d-or-less MSS.

Secure multi-party computation (MPC) enables multiple players to cooperatively evaluate various functions in the presence of adversaries. In this paper, we consider non-interactive MPC (NIMPC) against honest-but-curious adversaries in the information-theoretic setting, which was introduced by Beimel et al. at CRYPTO 2014. Their main focus is to realize stronger security while completely avoiding interaction, and succeeded to show that every function admits a fully robust NIMPC protocol. In this paper, we further develop the study of NIMPC. We first present a simple lower bound on the communication complexity derived from the correctness requirement of NIMPC. Secondly, we present an efficient NIMPC protocol for indicator functions, which is an important building block of NIMPC protocols. An NIMPC protocol for arbitrary functions is also constructed from the proposed NIMPC for indicator functions by using the generic compiler introduced by Beimel et al. in CRYPTO 2014. The communication complexities of NIMPC protocols presented in this paper are much more efficient than the previous ones. In fact, the gap between the lower and upper bounds of the communication complexity is reduced from exponential in the input length to quadratic . Finally, we show some improvements on the efficiency in the so-called offline-online model. Specifically, for some sets of functions, the exponential amount of offline communication reduces the online communication to almost optimum amount in the standard model.

There are two types of threshold ramp secret sharing (TRSS) schemes: Linear function ramp and nonlinear function ramp. A linear (resp. nonlinear) function TRSS scheme reveals information of the secret linearly (resp. nonlinearly). There are many studies on the linear ones and various secure and efficient constructions have been proposed. In contrast, the notion of the nonlinear function scheme was recently introduced, and any previous construction is either insecure or inefficient. This paper first points out defects of the previous insecure construction, and then presents the first secure and efficient construction. The proposed construction can achieves H(Vi) ≪ H(S) while in the previous secure construction H(Vi) = H(S) where H(Vi) and H(S) are the entropies of each share and the secret, respectively.