On the Dealer's Randomness Required in Secret Sharing Schemes

In this paper we provide upper and lower bounds on the randomness required by the dealer to set up a secret sharing scheme for infinite classes of access structures. Lower bounds are obtained using entropy arguments. Upper bounds derive from a decomposition construction based on combinatorial designs (in particular, t-(v,k,) designs). We prove a general result on the randomness needed to construct a scheme for the cycle Cn; when n is odd our bound is tight. We study the access structures on at most four participants and the connected graphs on five vertices, obtaining exact values for the randomness for all them. Also, we analyze the number of random bits required to construct anonymous threshold schemes, giving upper bounds. (Informally, anonymous threshold schemes are schemes in which the secret can be reconstructed without knowledge of which participants hold which shares.)     

Secret Sharing Schemes with Three or Four Minimal Qualified Subsets

In this paper we study secret sharing schemes whose access structure has three or four minimal qualified subsets. The ideal case is completely characterized and for the non-ideal case we provide bounds on the optimal information rate.AMS Classification 94A62     

Generalised Cumulative Arrays in Secret Sharing

Cumulative arrays have played an important role in the early development of the secret sharing theory. They have not been subject to extensive study so far, as the secret sharing schemes built on them generally result in much larger sizes of shares, when compared with other conventional approaches. Recent works in threshold cryptography show that cumulative arrays may be the appropriate building blocks in non-homomorphic threshold cryptosystems where the conventional secret sharing methods are generally of no use. In this paper we study several extensions of cumulative arrays and show that some of these extensions significantly improve the performance of conventional cumulative arrays. In particular, we derive bounds on generalised cumulative arrays and show that the constructions based on perfect hash families are asymptotically optimal. We also introduce the concept of ramp perfect hash families as a generalisation of perfect hash families for the study of ramp secret sharing schemes and ramp cumulative arrays.     

A General Decomposition Construction for Incomplete Secret Sharing Schemes

A secret sharing scheme for an incomplete access structure (,) is a method of distributing information about a secret among a group of participants in such a way that sets of participants in can reconstruct the secret and sets of participants in can not obtain any new information about the secret. In this paper we present a more precise definition of secret sharing schemes in terms of information theory, and a new decomposition theorem. This theorem generalizes previous decomposition theorems and also works for a more general class of access structures. We demonstrate some applications of the theorem.     

Providing Anonymity in Unconditionally Secure Secret Sharing Schemes

We discuss the concept of anonymity in an unconditionally secure secret sharing scheme, proposing several types of anonymity and situations in which they might arise. We present a foundational framework and provide a range of general constructions of unconditionally secure secret sharing schemes offering various degrees of anonymity.     

Tight Bounds on the Information Rate of Secret Sharing Schemes

A secret sharing scheme is a protocol by means of which a dealer distributes a secret s among a set of participants P in such a way that only qualified subsets of P can reconstruct the value of s whereas any other subset of P, non-qualified to know s, cannot determine anything about the value of the secret.In this paper we provide a general technique to prove upper bounds on the information rate of secret sharing schemes. The information rate is the ratio between the size of the secret and the size of the largest share given to any participant. Most of the recent upper bounds on the information rate obtained in the literature can be seen as corollaries of our result. Moreover, we prove that for any integer d there exists a d-regular graph for which any secret sharing scheme has information rate upper bounded by 2/(d+1). This improves on van Dijk's result dik and matches the corresponding lower bound proved by Stinson in [22].     

Detection of Cheaters in Vector Space Secret Sharing Schemes

A perfect secret sharing scheme is a method of distributing shares of a secret among a set P of participants in such a way that only qualified subsets of P can reconstruct the secret from their shares and non-qualified subsets have absolutely no information on the value of the secret. In a secret sharing scheme, some participants could lie about the value of their shares in order to obtain some illicit benefit. Therefore, the security against cheating is an important issue in the implementation of secret sharing schemes. Two new secret sharing schemes in which cheaters are detected with high probability are presented in this paper. The first one has information rate equal to 1/2 and can be implemented not only in threshold structures, but in a more general family of access structures. We prove that the information rate of this scheme is almost optimal among all schemes with the same security requirements. The second scheme we propose is a threshold scheme in which cheaters are detected with high probability even if they know the secret. The information rate is in this case 1/3 In both schemes, the probability of cheating successfully is a fixed value that is determined by the size of the secret.     

Secret Sharing Schemes with Detection of Cheaters for a General Access Structure

In a secret sharing scheme, some participants can lie about the value of their shares when reconstructing the secret in order to obtain some illicit benefit. We present in this paper two methods to modify any linear secret sharing scheme in order to obtain schemes that are unconditionally secure against that kind of attack. The schemes obtained by the first method are robust, that is, cheaters are detected with high probability even if they know the value of the secret. The second method provides secure schemes, in which cheaters that do not know the secret are detected with high probability. When applied to ideal linear secret sharing schemes, our methods provide robust and secure schemes whose relation between the probability of cheating and the information rate is almost optimal. Besides, those methods make it possible to construct robust and secure schemes for any access structure.     

Minimal Generating Sets for Relative Ideals in Numerical Semigroups of Multiplicity Eight

Abstract

Let S be a numerical semigroup and let I be a relative ideal of S. Let S ? I denote the dual of I and let μ _S (?) represent the size of a minimal generating set. We investigate the inequality μ _S (I)μ _S (S ? I) ≥ μ _S (I + (S ? I)) under the assumption that S has multiplicity 8. We will show that if I is non-principal, then the strict inequality μ _S (I)μ _S (S ? I) > μ _S (I + (S ? I)) always holds.     

Constructions for Anonymous Secret Sharing Schemes Using Combinatorial Designs

In an anonymous secret sharing scheme the secret can be reconstructed without knowledge ofwhich participants hold which shares.In this paper some constructions of anonymous secret sharing schemeswith 2 thresholds by using combinatorial designs are given.Let v(t,w,q)denote the minimum size of the setof shares of a perfect anonymous(t,w)threshold secret sharing scheme with q secrets.In this paper we provethat v(t,w,q)=(q)if t and w are fixed and that the lower bound of the size of the set of shares in[4]is notoptimal under certain condition.     

A Construction for Multisecret Threshold Schemes

A multisecret threshold scheme is a system that protects a number of secrets (or keys) among a group of participants, as follows. Given a set of n participants, there is a secret s _K associated with each k–subset K of these participants. The scheme ensures that s _K can be reconstructed by any group of t participants in K ( ). A lower bound has been established on the amount of information that participants must hold in order to ensure that any set of up to w participants cannot obtain any information about a secret with which they are not associated. In this paper, for parameters t=2 and w=n-k+t-1, we give a construction for multisecret threshold schemes that satisfy this bound.     

Defining Sets and Critical Sets in (0,1)‐Matrices

If D is a partially filled‐in (0, 1)‐matrix with a unique completion to a (0, 1)‐matrix M (with prescribed row and column sums), we say that D is a defining set for M. If the removal of any entry of D destroys this property (i.e. at least two completions become possible), we say that D is a critical set for M. In this note, we show that the complement of a critical set for a (0, 1)‐matrix M is a defining set for M. We also study the possible sizes (number of filled‐in cells) of defining sets for square matrices M with uniform row and column sums, which are also frequency squares. In particular, we show that when the matrix is of even order 2m and the row and column sums are all equal to m, the smallest possible size of a critical set is precisely m². We give the exact structure of critical sets with this property. © 2012 Wiley Periodicals, Inc. J. Combin. Designs 21: 253–266, 2013     

Linear Secret Sharing Schemes and Rearrangements of Access Structures

In this paper we study linear secret sharing schemes by monotone span programs, according to the relation between realizing access structures by linear secret sharing schemes and computing monotone Boolean functions by monotone span programs. We construct some linear secret sharing schemes. Furthermore, we study the rearrangements of access structures that is very important in practice.     

Basic Properties of the (t, n)-Threshold Visual Secret Sharing Scheme with Perfect Reconstruction of Black Pixels

In this paper we consider the (t, n)-threshold visual secret sharing scheme (VSSS) in which black pixels in a secret black-white images is reproduced perfectly as black pixels when we stack arbitrary t shares. This paper provides a new characterization of the (t, n)-threshold visual secret sharing scheme with such a property (hereafter, we call such a VSSS the (t, n)-PBVSSS for short). We use an algebraic method to characterize basis matrices of the (t, n)-PBVSSS in a certain class of matrices. We show that the set of all homogeneous polynomials each element of which yields basis matrices of the (t, n)-PBVSSS becomes a set of lattice points in an (n−t+1)-dimensional linear space. In addition, we prove that the optimal basis matrices in the sense of maximizing the relative difference among all the basis matrices in the class coincides with the basis matrices given by Blundo, Bonis and De Santis [3] for all n≥ t ≥ 2.     

Constructions and Properties of k out of n Visual Secret Sharing Schemes

The idea of visual k out of n secret sharing schemes was introduced in Naor. Explicit constructions for k = 2 and k = n can be found there. For general k out of n schemes bounds have been described.Here, two general k out of n constructions are presented. Their parameters are related to those of maximum size arcs or MDS codes. Further, results on the structure of k out of n schemes, such as bounds on their parameters, are obtained. Finally, the notion of coloured visual secret sharing schemes is introduced and a general construction is given.     

A Representation of a Family of Secret Sharing Matroids

Deciding whether a matroid is secret sharing or not is a well-known open problem. In Ng and Walker [6] it was shown that a matroid decomposes into uniform matroids under strong connectivity. The question then becomes as follows: when is a matroid m with N uniform components secret sharing? When N = 1, m corresponds to a uniform matroid and hence is secret sharing. In this paper we show, by constructing a representation using projective geometry, that all connected matroids with two uniform components are secret sharing     

扩散 Cantor 集的最小Hausdorff 测度

In this paper, we construct a scattered Cantor set having the value 1/2 of log2/log3- dimensional Hausdorff measure. Combining a theorem of Lee and Baek, we can see the value 21 is the minimal Hausdorff measure of the scattered Cantor sets, and our result solves a conjecture of Lee and Baek.     

A Construction of Difference Sets

In this paper, we will give a construction of a family of -difference sets in thegroup , where q is any power of 2, K is any group with and G is an abelian 2-group of order which contains anelementary abelian subgroup of index 2.     

Minimal Blocking Sets in Projective Spaces of Square Order

In this paper minimal m-blocking sets of cardinality at most in projective spaces PG(n,q) of square order q, q 16, are characterized to be (t, 2(m-t-1))-cones for some t with . In particular we will find the smallest m-blocking sets that generate the whole space PG(n,q) for 2m n m.