In this paper, we treat (k, L, n) ramp secret sharing schemes (SSSs) that can detect impersonation attacks and/or substitution attacks. First, we derive lower bounds on the sizes of the shares and random number used in encoding for given correlation levels, which are measured by the mutual information of shares. We also derive lower bounds on the success probabilities of attacks for given correlation levels and given sizes of shares. Next we propose a strong (k, L, n) ramp SSS against substitution attacks. As far as we know, the proposed scheme is the first strong (k, L, n) ramp SSSs that can detect substitution attacks of at most k-1 shares. Our scheme can be applied to a secret SL uniformly distributed over GF(pm)L, where p is a prime number with p≥L+2. We show that for a certain type of correlation levels, the proposed scheme can achieve the lower bounds on the sizes of the shares and random number, and can reduce the success probability of substitution attacks within nearly L times the lower bound when the number of forged shares is less than k. We also evaluate the success probability of impersonation attack for our schemes. In addition, we give some examples of insecure ramp SSSs to clarify why each component of our scheme is essential to realize the required security.

In secret sharing scheme, Tompa and Woll considered a problem of cheaters who try to make another participant reconstruct an invalid secret. Later, some models of such cheating were formalized and lower bounds of the size of shares were shown in the situation of fixing the minimum successful cheating probability. Under the assumption that cheaters do not know the distributed secret, no efficient scheme is known which can distribute bit strings. In this paper, we propose an efficient scheme for distributing bit strings with an arbitrary access structure. When distributing a random bit string with threshold access structures, the bit length of shares in the proposed scheme is only a few bits longer than the lower bound.

In (k,n) threshold scheme, Tompa and Woll considered a problem of cheaters who try to make another participant reconstruct an invalid secret. Later, some models of such cheating were formalized and lower bounds of the size of share were shown in the situation of fixing the maximum successful cheating probability to ε. Some efficient schemes in which size of share is equal to the lower bound were also proposed. Let |S| be the field size of the secret. Under the assumption that cheaters do not know the distributed secret, these sizes of share of previous schemes which can work for ε > 1/|S| are somewhat larger than the bound. In this paper, we show the bound for this case is really tight by constructing a new scheme. When distributing uniform secret, the bit length of share in the proposed scheme is only 1 bit longer than the known bound. Further, we show a tighter bound of the size of share in case of ε < 1/|S|.

A secret sharing scheme allows a secret to be shared among a set of participants, P, such that only authorized subsets of P can recover the secret, but any unauthorized subset can not recover the secret. It can be used to protect important secret data, such as cryptographic keys, from being lost or destroyed without accidental or malicious exposure. In this paper, we consider secret sharing schemes based on interpolating polynomials. We show that, by simply increasing the number of shares held by each participant, there is a multiple assignment scheme for any monotone access structure such that cheating can be detected with very high probability by any honest participant even the cheaters form a coalition in order to deceive him.