BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Laszlo Csirmaz

Laszlo Csirmaz appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Information Theorymath.ITCryptography and Securitymath.COmath.OC

Catalog footprint

What is connected

9works
5topics
2close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

9 published item(s)

preprint2022arXiv

Algebra of Data Reconciliation

With distributed computing and mobile applications becoming ever more prevalent, synchronizing diverging replicas of the same data is a common problem. Reconciliation -- bringing two replicas of the same data structure as close as possible without overriding local changes -- is investigated in an algebraic model. Our approach is to consider two sequences of simple commands that describe the changes in the replicas compared to the original structure, and then determine the maximal subsequences of each that can be propagated to the other. The proposed command set is shown to be functionally complete, and an update detection algorithm is presented which produces a command sequence transforming the original data structure into the replica while traversing both simultaneously. Syntactical characterization is provided in terms of a rewriting system for semantically equivalent command sequences. Algebraic properties of sequence pairs that are applicable to the same data structure are investigated. Based on these results the reconciliation problem is shown to have a unique maximal solution. In addition, syntactical properties of the maximal solution allow for an efficient algorithm that produces it.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

An optimization problem for continuous submodular functions

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.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Secret sharing and duality

Secret sharing is an important building block in cryptography. All explicitly defined secret sharing schemes with known exact complexity bounds are multi-linear, thus are closely related to linear codes. The dual of such a linear scheme, in the sense of duality of linear codes, gives another scheme for the dual access structure. These schemes have the same complexity, namely the largest share size relative to the secret size is the same. It is a long-standing open problem whether this fact is true in general: the complexity of any access structure is the same as the complexity of its dual. We give an almost answer to this question. An almost perfect scheme allows negligible errors, both in the recovery and in the independence. There exists an almost perfect ideal scheme on 174 participants whose complexity is strictly smaller than that of its dual.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Book inequalities

Information theoretical inequalities have strong ties with polymatroids and their representability. A polymatroid is entropic if its rank function is given by the Shannon entropy of the subsets of some discrete random variables. The book is a special iterated adhesive extension of a polymatroid with the property that entropic polymatroids have $n$-page book extensions over an arbitrary spine. We prove that every polymatroid has an $n$-page book extension over a single element and over an all-but-one-element spine. Consequently, for polymatroids on four elements, only book extensions over a two-element spine should be considered. F. Matúš proved that the Zhang-Yeung inequalities characterize polymatroids on four elements which have such a 2-page book extension. The $n$-page book inequalities, defined in this paper, are conjectured to characterize polymatroids on four elements which have $n$-page book extensions over a two-element spine. We prove that the condition is necessary; consequently every book inequality is an information inequality on four random variables. Using computer-aided multiobjective optimization, the sufficiency of the condition is verified up to 9-page book extensions.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

On-line secret sharing

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.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

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.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Using multiobjective optimization to map the entropy region of four random variables

Presently the only available method of exploring the 15-dimensional entropy region formed by the entropies of four random variables is the one of Zhang and Yeung from 1998. It is argued that their method is equivalent to solving linear multiobjective optimization problems. Benson's outer approximation algorithm is a fundamental tool for solving these optimization problems. An improved version of Benson's algorithm is described which requires solving one scalar linear program in each iteration rather than two or three as in previous versions. During the algorithm design special care was taken for numerical stability. The implemented algorithm was used to check previous statements about the entropy region, and to gain new information on that region. The experimental results demonstrate the viability of the method for determining the extremal set of medium size, numerically ill-posed optimization problems. With growing problem size two limitations of Benson's algorithm have been observed: the inefficiency of the scalar LP solver on one hand and the unexpectedly large number of intermediate vertices on the other.

0 citations0 reviewsNo code linkedOpen access