Laszlo Csirmaz

Laszlo Csirmaz

Let $N$ be a finite set of cardinality $n$, and $a\in N$. A submodular function $f$ on $N$ with $f(a)=1$ is defined to be $a$-reduced if, for any decomposition $f=g+h$ into submodular functions where $h$ does not depend on $a$, it follows that $h$ is identically zero. The maximal possible value of $f$ on the remaining singletons defines a quantity $λ$ that characterizes the degree to which one variable can constrain the value of another; geometrically, it also limits the possible elongation of the associated submodular base polytope. We construct an example demonstrating that $λ$ can be as large as $Ω(n/\log n)$. Furthermore, we establish a doubly exponential upper bound on $λ$. The problem of narrowing the gap between these bounds remains open.

Laszlo Csirmaz, František Matúš, Carles Padró

Bipartite secret sharing schemes have a bipartite access structure in which the set of participants is divided into two parts and all participants in the same part play an equivalent role. Such a bipartite scheme can be described by a \emph{staircase}: the collection of its minimal points. The complexity of a scheme is the maximal share size relative to the secret size; and the $κ$-complexity of an access structure is the best lower bound provided by the entropy method. An access structure is $κ$-ideal if it has $κ$-complexity 1. Motivated by the abundance of open problems in this area, the main results can be summarized as follows. First, a new characterization of $κ$-ideal multipartite access structures is given which offers a straightforward and simple approach to describe ideal bipartite and tripartite access structures. Second, the $κ$-complexity is determined for a range of bipartite access structures, including those determined by two points, staircases with equal widths and heights, and staircases with all heights 1. Third, matching linear schemes are presented for some non-ideal cases, including staircases where all heights are 1 and all widths are equal. Finally, finding the Shannon complexity of a bipartite access structure can be considered as a discrete submodular optimization problem. An interesting and intriguing continuous version is defined which might give further insight to the large-scale behavior of these optimization problems.

Laszlo Csirmaz

Real continuous submodular functions, as a generalization of the corresponding discrete notion to the continuous domain, gained considerable attention recently. The analog notion for entropy functions requires additional properties: a real function defined on the non-negative orthant of $\mathbb R^n$ is entropy-like (EL) if it is submodular, takes zero at zero, non-decreasing, and has the Diminishing Returns property. Motivated by problems concerning the Shannon complexity of multipartite secret sharing, a special case of the following general optimization problem is considered: find the minimal cost of those EL functions which satisfy certain constraints. In our special case the cost of an EL function is the maximal value of the $n$ partial derivatives at zero. Another possibility could be the supremum of the function range. The constraints are specified by a smooth bounded surface $S$ cutting off a downward closed subset. An EL function is feasible if at the internal points of $S$ the left and right partial derivatives of the function differ by at least one. A general lower bound for the minimal cost is given in terms of the normals of the surface $S$. The bound is tight when $S$ is linear. In the two-dimensional case the same bound is tight for convex or concave $S$. It is shown that the optimal EL function is not necessarily unique. The paper concludes with several open problems.

Laszlo Csirmaz

An important parameter in a secret sharing scheme is the number of minimal qualified sets. Given this number, the universal access structure is the richest possible structure, namely the one in which there are one or more participants in every possible Boolean combination of the minimal qualified sets. Every access structure is a substructure of the universal structure for the same number of minimal qualified subsets, thus universal access structures have the highest complexity given the number of minimal qualified sets. We show that the complexity of the universal structure with $n$ minimal qualified sets is between $n/\log_2 n$ and $n/2.7182$ asymptotically.

Laszlo Csirmaz, Gábor Tardos

In an on-line secret sharing scheme the dealer assigns shares in the order the participants show up, knowing only those qualified subsets whose all members she has seen. We assume that the overall access structure is known and only the order of the participants is unknown. On-line secret sharing is a useful primitive when the set of participants grows in time, and redistributing the secret is too expensive. In this paper we start the investigation of unconditionally secure on-line secret sharing schemes. The complexity of a secret sharing scheme is the size of the largest share a single participant can receive over the size of the secret. The infimum of this amount in the on-line or off-line setting is the on-line or off-line complexity of the access structure, respectively. For paths on at most five vertices and cycles on at most six vertices the on-line and offline complexities are equal, while for other paths and cycles these values differ. We show that the gap between these values can be arbitrarily large even for graph based access structures. We present a general on-line secret sharing scheme that we call first-fit. Its complexity is the maximal degree of the access structure. We show, however, that this on-line scheme is never optimal: the on-line complexity is always strictly less than the maximal degree. On the other hand, we give examples where the first-fit scheme is almost optimal, namely, the on-line complexity can be arbitrarily close to the maximal degree. The performance ratio is the ratio of the on-line and off-line complexities of the same access structure. We show that for graphs the performance ratio is smaller than the number of vertices, and for an infinite family of graphs the performance ratio is at least constant times the square root of the number of vertices.

Laszlo Csirmaz

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.

Laszlo Csirmaz

We prove that for $d>1$ the best information ratio of the perfect secret sharing scheme based on the edge set of the $d$-dimensional cube is exactly $d/2$. Using the technique developed, we also prove that the information ratio of the infinite $d$-dimensional lattice is $d$.