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.     

Theorems of large deviations in the multivariate invariance principle

Let B be a real separable Banach space with norm |ß|_B, X, X₁, X₂, … be a sequence of centered independent identically distributed random variables taking values in B. Let s_n = s_n(t), 0 ≤ t ≤ 1 be the random broken line such that s_n(0) = 0, s_n(k/n) = n^−1/2 Σ_i=1^k X_i for n = 1, 2, … and k = 1, …, n. Denote |s_n|_B = sup_{0 ≤ t ≤ 1} |s_n(t)|_B and assume that w(t), 0 ≤ t ≤ 1 is the Wiener process such that covariances of w(1) and X are equal. We show that under appropriate conditions P(|s_n|_B > r) = P(|w|_B > r)(1 + o(1)) and give estimates of the remainder term. The results are new already in the case of B having finite dimension.     

The inducibility of complete bipartite graphs

For any s ≥ 1 and t ≥ (^S₂), we prove that among all graphs with n vertices the graph that contains the maximal number of induced copies of K_{t, t+s} for any fixed s ≥ 1 and t ≥ (^s₂) is K_{(n/2)+α(n/2)-α} for some function α = o(n). We show that this is not valid for t < (^s₂). Analogous results for complete multipartite graphs are also obtained.     

On a class of nonlinear integral equations

In this paper we consider abstract equations of the typeK _ν ν +ν =w ₀, in a closed convex subset of a separable Hilbert spaceH. For eachv in the closed convex subset,K _v :H →H is a bounded linear map. As an application of our abstract result we obtain an existence result for nonlinear integral equations of the typeν(s)+ν(s)∫ ₀ ¹ k(s,t)ν(t)dt =W ₀(s) in the spaceL ² [0,1].     

Coloring 4‐cycle systems

An m‐cycle system of order n is a partition of the edges of the complete graph K_n into m‐cycles. We investigate k‐colorings of 4‐cycle systems in which no 4‐cycle is monochromatic. For any k ≥ 3, we construct a k‐chromatic 4‐cycle system. We also show that for any k ge; 2, there exists an integer w_k such that for all admissible n ≥ w_k, there is a k‐chromatic 4‐cycle system of order n. © 2005 Wiley Periodicals, Inc. J Combin Designs     

Detection and identification of cheaters in (<Emphasis Type="Italic">t</Emphasis>, <Emphasis Type="Italic">n</Emphasis>) secret sharing scheme

In a (t, n) secret sharing scheme, a secret s is divided into n shares and shared among a set of n shareholders by a mutually trusted dealer in such a way that any t or more than t shares will be able to reconstruct this secret; but fewer than t shares cannot know any information about the secret. When shareholders present their shares in the secret reconstruction phase, dishonest shareholder(s) (i.e. cheater(s)) can always exclusively derive the secret by presenting faked share(s) and thus the other honest shareholders get nothing but a faked secret. Cheater detection and identification are very important to achieve fair reconstruction of a secret. In this paper, we consider the situation that there are more than t shareholders participated in the secret reconstruction. Since there are more than t shares (i.e. it only requires t shares) for reconstructing the secret, the redundant shares can be used for cheater detection and identification. Our proposed scheme uses the shares generated by the dealer to reconstruct the secret and, at the same time, to detect and identify cheaters. We have included discussion on three attacks of cheaters and bounds of detectability and identifiability of our proposed scheme under these three attacks. Our proposed scheme is an extension of Shamir’s secret sharing scheme.      

The diameter of randomly perturbed digraphs and some applications

The central observation of this paper is that if εn random arcs are added to any n‐node strongly connected digraph with bounded degree then the resulting graph has diameter 𝒪(lnn) with high probability. We apply this to smoothed analysis of algorithms and property testing. Smoothed Analysis: Recognizing strongly connected digraphs is a basic computational task in graph theory. Even for digraphs with bounded degree, it is NL‐complete. By XORing an arbitrary bounded degree digraph with a sparse random digraph R ∼ 𝔻_n,ε/n we obtain a “smoothed” instance. We show that, with high probability, a log‐space algorithm will correctly determine if a smoothed instance is strongly connected. We also show that if NL ⫅̸ almost‐L then no heuristic can recognize similarly perturbed instances of (s,t)‐connectivity. Property Testing: A digraph is called k‐linked if, for every choice of 2k distinct vertices s₁,…,s_k,t₁,…,t_k, the graph contains k vertex disjoint paths joining s_r to t_r for r = 1,…,k. Recognizing k‐linked digraphs is NP‐complete for k ≥ 2. We describe a polynomial time algorithm for bounded degree digraphs, which accepts k‐linked graphs with high probability, and rejects all graphs that are at least εn arcs away from being k‐linked. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2007     

GENERALISED MAXIMAL INDEPENDENCE AND CLIQUE NUMBERS OF GRAPHS

Abstract

A set B of vertices of a graph G = (V,E) is a k-maximal independent set (kMIS) if B is independent but for all ?-subsets X of B, where ? ? k—1, and all (? + 1)-subsets Y of V—B, the set (B—X) u Y is dependent. A set S of vertices of C is a k-maximal clique (kMc) of G iff S is a kMIS of [Gbar]. Let β_k, (G) (w_k(G) respectively) denote the smallest cardinality of a kMIS (kMC) of G—obviously β_k(G) = w_k([Gbar]). For the sequence m₁ ? m₂ ?…? m_n = r of positive integers, necessary and sufficient conditions are found for a graph G to exist such that w_k(G) = m_k for k = 1,2,…,n and w(G) = r (equivalently, β_k(G) = m_k for k = 1,2,…,n and β(G) = r). Define s_k(?,m) to be the largest integer such that for every graph G with at most s_k(?,m) vertices, β_k(G) ? ? or w_k(G) ? m. Exact values for s_k(?,m) if k ≥ 2 and upper and lower bounds for s₁(?,m) are de termined.     

On the number of cycles of given length of a free word in several random permutations

Let w ≠ 1 be a free word in the symbols g₁,…, g_k and their inverses (i.e., an element of the free group F_k). For any s₁,…, s_k, in the group s_n of all permutation of n objects, we denote by w(s₁,…,s_k) ? S_n the permutation obtained by replacing g₁,…, g_k with s₁,…, s_k in the expression of w. Let X (s₁,…, s_k) denote the number of cycles of length L of w(s₁,…, s_k). For fixed w and L, we show that X, viewed as a random variable on S_n^k, has (for n →∞) a Poisson-type limit distribution, which can be computed precisely. © 1994 John Wiley & Sons, Inc.     

Resonant destabilization of a floating homogeneous ice layer

We show that a homogeneous elastic ice layer of finite thickness and infinite horizontal extension floating on the surface of a homogeneous water layer of finite depth possesses a countable unbounded set of of resonant frequencies. The water is assumed to be compressible, the viscous effects are neglected in the model. Responses of this water-ice system to spatially localized harmonic in time perturbations with the resonant frequencies grow at least as ?t\sqrt{t} in the two-dimensional (2-D) case and at least as lnt in the three-dimensional (3-D) case, when time t?￥.t\to\infty. The analysis is based on treating the 3-D linear stability problem by applying the Laplace-Fourier transform and reducing the consideration to the 2-D case. The dispersion relation for the 2-D problem D(k,w) = 0,{D}(k,\omega) = 0, obtained previously by Brevdo and Il'ichev [10], is treated analytically and also computed numerically. Here k is a wavenumber, and w\omega is a frequency. It is proved that the system D(k,w) = 0, D_k(k,w) = 0{D}(k,\omega) = 0, {D}_k(k,\omega) = 0 possesses a countable unbounded set of roots (k, w) = (0,w_n), n ? \Bbb Z(k, \omega) = (0,\omega_n), n\in\Bbb Z with Im w_n = 0.\rm{Im}\ \omega_n = 0. Then the analysis of Brevdo [6], [7], [8], [9], which showed the existence of resonances in a homogeneous elastic waveguide, is applied to show that similar resonances exist in the present water-ice model. We propose a resonant mechanism for ice-breaking. It is based on destabilizing the floating ice layer by applying localized harmonic perturbations, with a moderate amplitude and at a resonant frequency.     

PRIMITIVITY IN NEAR-RINGS WITH LOCALIZED DISTRIBUTIVITY CONDITIONS

Abstract

Let K, S, T be subsets of a near-ring R. Then K is (S, T)-distributive if: s(k ₁ + k ₂)t = sk ₁ t + sk ₂ t, for each k ₁, k ₂ ε K, s ε S, t ε T; and K is (S, T)-d.g. on X if K is (S, X)-distributive and T is contained in the additive subgroup generated by X. This paper considers υ-primitivity and the associated ?_υ radicals under various such conditions, particularly where S, T, and K are powers of R. Natural examples which illustrate and delimit the theory are given.     

Edge-colored complete graphs with precisely colored subgraphs

Letf(s, t; k) be the largest value ofm such that it is possible tok-color the edges of the complete graphK _m so that everyK _s ⊆K _m has exactlyt colors occuring on its edges. The main object of this paper is to describe the behavior of the functionf(s,t;k), usually thinking ofs andt fixed, and lettingk become large. Dedicated to Paul Erdős on his seventieth birthday     

Gruppen secret sharing or how to share several secrets if you must?

Each member of an n-person team has a secret, say a password. The k out of n gruppen secret sharing requires that any group of k members should be able to recover the secrets of the other n ? k members, while any group of k ? 1 or less members should have no information on the secret of other team member even if other secrets leak out. We prove that when all secrets are chosen independently and have size s, then each team member must have a share of size at least (n ? k)s, and we present a scheme which achieves this bound when s is large enough. This result shows a significant saving over n independent applications of Shamir’s k out of n ? 1 threshold schemes which assigns shares of size (n ? 1)s to each team member independently of k. We also show how to set up such a scheme without any trusted dealer, and how the secrets can be recovered, possibly multiple times, without leaking information. We also discuss how our scheme fits to the much-investigated multiple secret sharing methods.     

On t-Dimension over Strong Mori Domains

In this note we prove that if R is a strong Mori domain with t-dim R = n and with countably many prime v-ideals, then there is a chain of rings between R and R^w R1=R belong to R2……belong to Rn lohtuin in R^w such that each R, is also a strong Mori domain and t-dim Rk=n - k ＋ 1 for k = 1,2,..., n.     

On a geometrical method of construction of maximal t-linearly independent sets

The problem of constructing a maximal t-linearly independent set in V(r; s) (called a maximal L_t(r, s)-set in this paper) is a very important one (called a packing problem) concerning a fractional factorial design and an error correcting code where V(r; s) is an r-dimensional vector space over a Galois field GF(s) and s is a prime or a prime power. But it is very difficult to solve it and attempts made by several research workers have been successful only in special cases.In this paper, we introduce the concept of a {Σ_α=1^kw_α, m; t, s}-min · hyper with weight (w₁, w₂,…, w_k) and using this concept and the structure of a finite projective geometry PG(n ? 1, s), we shall give a geometrical method of constructing a maximal L_t(t + r, s)-set with length t + r + n for any integers r, n, and s such that n ? 3, n ? 1 ? r₀ ? n + s ? 2 and r₁ ? 1, where r = (r₁ + 1)v_n?1 ? r₀ and $\text{v}{}_{\mathrm{n}}\text{=}\text{(s}{}^{\mathrm{n}}\text{? 1)}\text{(s ? 1)}$.     

On maximal (k,t)-sets

Summary This investigation was originally motivated by the problem of determining the maximum number of points in finiten-dimensional projective spacePG(n, s) based on the Galois fieldGF(s) of orders=p ^h (wherep andh are positive integers andp is the prime characteristic of the field), such that not of these chosen points are linearly dependent. A set ofk distinct points inPG(n, s), not linearly dependent, is called a (k, t)-set fork ₁ >k. The maximum value ofk is denoted bym _t (n+1, s). The purpose of this paper is to find new upper bounds for some values ofn, s andt. These bounds are of importance in the experimental design and information theory problems.     

Subdivisions of large complete bipartite graphs and long induced paths in k‐connected graphs

It is proved that for every positive integers k, r and s there exists an integer n = n(k,r,s) such that every k‐connected graph of order at least n contains either an induced path of length s or a subdivision of the complete bipartite graph K_k,r. © 2004 Wiley Periodicals, Inc. J Graph Theory 45: 270–274, 2004     

ON THE NORMALITY OF MONOMIAL IDEALS OF MIXED PRODUCTS

Let R = K[x, y] be a polynomial ring in two disjoint sets of variables x, y over a field K. We study ideals of mixed products L = I_kJ_r + I_sJ_t such that k + r = s + t, where I_k (resp. J_r ) denotes the ideal of R generated by the square-free monomials of degree k (resp. r) in the x (resp. y ) variables. Our main result is a characterization of when a given ideal L of mixed products is normal.

     

Optimal (<Emphasis Type="Italic">k</Emphasis>, <Emphasis Type="Italic">n</Emphasis>) visual cryptographic schemes for general <Emphasis Type="Italic">k</Emphasis>

In (k, n) visual cryptographic schemes (VCS), a secret image is encrypted into n pages of cipher text, each printed on a transparency sheet, which are distributed among n participants. The image can be visually decoded if any k(≥2) of these sheets are stacked on top of one another, while this is not possible by stacking any k − 1 or fewer sheets. We employ a Kronecker algebra to obtain necessary and sufficient conditions for the existence of a (k, n) VCS with a prior specification of relative contrasts that quantify the clarity of the recovered image. The connection of these conditions with an L ₁-norm formulation as well as a convenient linear programming formulation is explored. These are employed to settle certain conjectures on contrast optimal VCS for the cases k = 4 and 5. Furthermore, for k = 3, we show how block designs can be used to construct VCS which achieve optimality with respect to the average and minimum relative contrasts but require much smaller pixel expansions than the existing ones.     

Partitioning complete multipartite graphs by monochromatic trees

The tree partition number of an r‐edge‐colored graph G, denoted by t_r(G), is the minimum number k such that whenever the edges of G are colored with r colors, the vertices of G can be covered by at most k vertex‐disjoint monochromatic trees. We determine t₂(K(n₁, n₂,…, n_k)) of the complete k‐partite graph K(n₁, n₂,…, n_k). In particular, we prove that t₂(K(n, m)) = ? (m‐2)/2ⁿ? + 2, where 1 ≤ n ≤ m. © 2004 Wiley Periodicals, Inc. J Graph Theory 48: 133–141, 2005