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.     

Secret sharing schemes on access structures with intersection number equal to one

The characterization of ideal access structures and the search for bounds on the optimal information rate are two important problems in secret sharing. These problems are studied in this paper for access structures with intersection number equal to one, that is, structures such that there is at most one participant in the intersection of any two different minimal qualified subsets. The main result in this work is the complete characterization of the ideal access structures with intersection number equal to one. In addition, bounds on the optimal information rate are provided for the non-ideal case.     

Properties and constraints of cheating-immune secret sharing schemes

A secret sharing scheme is a cryptographic protocol by means of which a dealer shares a secret among a set of participants in such a way that it can be subsequently reconstructed by certain qualified subsets. The setting we consider is the following: in a first phase, the dealer gives in a secure way a piece of information, called a share, to each participant. Then, participants belonging to a qualified subset send in a secure way their shares to a trusted party, referred to as a combiner, who computes the secret and sends it back to the participants.Cheating-immune secret sharing schemes are secret sharing schemes in the above setting where dishonest participants, during the reconstruction phase, have no advantage in sending incorrect shares to the combiner (i.e., cheating) as compared to honest participants. More precisely, a coalition of dishonest participants, by using their correct shares and the incorrect secret supplied by the combiner, have no better chance in determining the true secret (that would have been reconstructed if they submitted correct shares) than an honest participant.In this paper we study properties and constraints of cheating-immune secret sharing schemes. We show that a perfect secret sharing scheme cannot be cheating-immune. Then, we prove an upper bound on the number of cheaters tolerated in such schemes. We also repair a previously proposed construction to realize cheating-immune secret sharing schemes. Finally, we discuss some open problems.     

Three-level secret sharing schemes from the twisted cubic

Three-level secret sharing schemes arising from the vector space construction over a finite field F are presented. Compared to the previously known schemes, they allow a larger number of participants with respect to the size of F. The key tool is the twisted cubic of PG(3,F).     

Rearrangements of access structures and their realizations in secret sharing schemes

Firstly, the definitions of the secret sharing schemes (SSS), i.e. perfect SSS, statistical SSS and computational SSS are given in an uniform way, then some new schemes for several familiar rearrangements of access structures with respect to the above three types of SSS are constructed from the old schemes. It proves that the new schemes and the old schemes are of the same security. A method of constructing the SSS which realizes the general access structure by rearranging some basic access structures is developed. The results of this paper can be used to key managements and access controls.     

Ideal secret sharing schemes whose minimal qualified subsets have at most three participants

One of the main open problems in secret sharing is the characterization of the access structures of ideal secret sharing schemes. Brickell and Davenport proved that every one of these ideal access structures is related in a certain way to a unique matroid. Specifically, they are matroid ports. In addition to the search of general results, this difficult open problem has been studied in previous works for several families of access structures. In this paper we do the same for access structures with rank 3, that is, structures whose minimal qualified subsets have at most three participants. We completely characterize and classify the rank-3 access structures that are matroid ports. We prove that all access structures with rank three that are ports of matroids greater than 3 are ideal. After the results in this paper, the only open problem in the characterization of the ideal access structures with rank three is to characterize the rank-3 matroids that can be represented by an ideal secret sharing scheme. A previous version of this paper appeared in Fifth Conference on Security and Cryptography for Networks, SCN 2006, Lecture Notes in Computer Science 4116 (2006) 201–215.     

A preemptive discrete-time priority buffer system with partial buffer sharing

This paper considers a Geo/Geo/1 discrete-time queue with preemptive priority. Both the arrival and service processes are Bernoulli processes. There are two kinds of customers: low-priority and high-priority customers. The high-priority customers have a preemptive priority over low-priority customers. If the total number of customers is equal or more than the threshold (k), the arrival of low-priority customers will be ignored. Hence the system buffer size is finite only for the low-priority customers. A recursive numerical procedure is developed to find the steady-state probabilities. With the aid of recursive equations, we transform the infinite steady-state departure-epoch equations set to a set of (k + 1) × (k + 2)/2 linear equations set based on the embedded Markov Chain technique. Then, this reduced linear equations set is used to compute the steady-state departure-epoch probabilities. The important performance measures of the system are calculated. Finally, the applicability of the solution procedure is shown by a numerical example and the sensitivity of the performance measures to the changes in system parameters is analyzed.     

Hypergraph decomposition and secret sharing

A secret sharing scheme is a protocol by which a dealer distributes a secret among a set of participants in such a way that only qualified sets of them can reconstruct the value of the secret whereas any non-qualified subset of participants obtain no information at all about the value of the secret. Secret sharing schemes have always played a very important role for cryptographic applications and in the construction of higher level cryptographic primitives and protocols.In this paper we investigate the construction of efficient secret sharing schemes by using a technique called hypergraph decomposition, extending in a non-trivial way the previously studied graph decomposition techniques. A major advantage of hypergraph decomposition is that it applies to any access structure, rather than only structures representable as graphs. As a consequence, the application of this technique allows us to obtain secret sharing schemes for several classes of access structures (such as hyperpaths, hypercycles, hyperstars and acyclic hypergraphs) with improved efficiency over previous results. Specifically, for these access structures, we present secret sharing schemes that achieve optimal information rate. Moreover, with respect to the average information rate, our schemes improve on previously known ones.In the course of the formulation of the hypergraph decomposition technique, we also obtain an elementary characterization of the ideal access structures among the hyperstars, which is of independent interest.     

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.     

The complexity and randomness of linear multi-secret sharing schemes with non-threshold structures

In a linear multi-secret sharing scheme with non-threshold structures, several secret values are shared among n participants, and every secret value has a specified access structure. The efficiency of a multi- secret sharing scheme is measured by means of the complexity a and the randomness . Informally, the com- plexity a is the ratio between the maximum of information received by each participant and the minimum of information corresponding to every key. The randomness is the ratio between the amount of information distributed to the set of users U = {1, …, n} and the minimum of information corresponding to every key. In this paper, we discuss a and of any linear multi-secret sharing schemes realized by linear codes with non-threshold structures, and provide two algorithms to make a and to be the minimum, respectively. That is, they are optimal.     

A Flaw in the Use of Minimal Defining Sets for Secret Sharing Schemes

It is shown that in some cases it is possible to reconstruct a block design uniquely from incomplete knowledge of a minimal defining set for . This surprising result has implications for the use of minimal defining sets in secret sharing schemes.     

Bounds for visual cryptography schemes

In this paper, we investigate the best pixel expansion of various models of visual cryptography schemes. In this regard, we consider visual cryptography schemes introduced by Tzeng and Hu (2002) [13]. In such a model, only minimal qualified sets can recover the secret image and the recovered secret image can be darker or lighter than the background. Blundo et al. (2006) [4] introduced a lower bound for the best pixel expansion of this scheme in terms of minimal qualified sets. We present another lower bound for the best pixel expansion of the scheme. As a corollary, we introduce a lower bound, based on an induced matching of hypergraph of qualified sets, for the best pixel expansion of the aforementioned model and the traditional model of visual cryptography scheme realized by basis matrices. Finally, we study access structures based on graphs and we present an upper bound for the smallest pixel expansion in terms of strong chromatic index.     

A secret sharing scheme based on cellular automata

A new secret sharing scheme based on a particular type of discrete delay dynamical systems: memory cellular automata, is proposed. Specifically, such scheme consists of a (k, n)-threshold scheme where the text to be shared is considered as one of the k initial conditions of the memory cellular automata and the n shares to be distributed are n consecutive configurations of the evolution of such cellular automata. It is also proved to be perfect and ideal.     

Linear multi-secret sharing schemes based on multi-party computation

In multi-secret sharing schemes, publishing shares during the process of reconstructing partial secrets may leak some information of the secrets unrecovered yet. By using a multi-party computation (MPC) protocol, we solve this problem for any linear multi-secret sharing scheme (MSSS). We also show that LMSSS usually involve more complicated reconstruction algorithms than “direct sum” schemes, but from the point of reducing share expansion, the former is preferred.     

Stable numerical schemes for a partly convolutional partial integro-differential equation

A model partial integro-differential operator (PIDO) that contains both local and nonlocal diffusion operators is considered in this article. This type of operators come in modeling various scientific and financial engineering problems. In most cases, people use finite difference schemes to generate solutions of such model problems. We compare and analyze stability and accuracy of two such finite difference schemes. We first present a discrete analogue of the PIDO and then approximate the semi-discrete time dependent problem using two different one step methods and show the stability conditions and the accuracy of the schemes. We use the Fourier transforms throughout our analysis.     

Coordination via cost and revenue sharing in manufacturer-retailer channels

The problem of establishing efficiency in a manufacturer-retailer channel (channel coordination) is extensively discussed in the industrial economics, the marketing and the operations research literature. However, studies considering consumer demand to be simultaneously affected by price and non-price variables are scarce. One subset of models investigates efficient contracts with non-linear tariffs, but requires mechanisms which are rarely observed in managerial practice. The other subset analyses channel efficiency effects of alternative royalty payments, but omits to design an efficient contract. We contribute to this literature by investigating a contract of royalty payments that is sufficient for channel coordination. Based on the analysis of the underlying vertical externalities, we show that channel coordination requires cost and revenue sharing via a revenue sharing rate and marketing effort participation rates on both manufacturer and retailer level. Some surprising findings are highlighted: there exists a continuum of efficient contracts. Efficiency requires a retailer’s participation of at least 50% in the manufacturer’s cost of marketing effort. Moreover, the elimination of double marginalisation is not necessary for channel coordination. Manufacturer and retailer can choose an efficient contract via bargaining over the wholesale price. The main challenge for managers will be to create acceptance of new types of royalty payments based on a trustful manufacturer-retailer relationship. We also discuss the cases of the Apple iPhone market launch and of innovative restaurant franchising to further illustrate and underline the relevance of our results.     

Value sharing of meromorphic functions and their derivatives

In this paper, we estimate the size of ρn's in the famous L. Zalcman's lemma. With it, we obtain some uniqueness theorems for meromorphic functions f and f^′ when they share two transcendental meromorphic functions.     

Partial geometric difference sets and partial geometric difference families

The concept of a partial geometric difference set (or $1\frac{1}{2}$-difference set) was introduced by Olmez in 2014. Recently, Nowak, Olmez and Song introduced the notion of a partial geometric difference family, which generalizes both the classical difference family and the partial geometric difference set. It was shown that partial geometric difference sets and partial difference families give rise to partial geometric designs. In this paper, a number of new infinite families of partial geometric difference sets and partial geometric difference families are constructed. From these partial geometric difference sets and difference families, we generate a list of infinite families of partial geometric designs.     

Minimal linear codes from Maiorana-McFarland functions

Minimal linear codes have important applications in secret sharing schemes and secure multi-party computation, etc. In this paper, we study the minimality of a kind of linear codes over $\mathrm{GF}(p)$ from Maiorana-McFarland functions. We first obtain a new sufficient condition for this kind of linear codes to be minimal without analyzing the weights of its codewords, which is a generalization of some works given by Ding et al. in 2015. Using this condition, it is easy to verify that such minimal linear codes satisfy $\frac{w_{\min }}{w_{\max }}\le \frac{p-1}{p}$ for any prime p, where $w_{\min }$ and $w_{\max }$ denote the minimum and maximum nonzero weights in a code, respectively. Then, by selecting the subsets of $\mathrm{GF}{(p)}^s$, we present two new infinite families of minimal linear codes with $\frac{w_{\min }}{w_{\max }}\le \frac{p-1}{p}$ for any prime p. In addition, the weight distributions of the presented linear codes are determined in terms of Krawtchouk polynomials or partial spreads.