Publications of Csirmaz, L.

On the impossibility of graph secret sharing

A perfect secret sharing scheme based on a graph G is a randomized distribution of a secret among the vertices of the graph so that the secret can be recovered from the information assigned to vertices at the endpoints of any edge, while the total information assigned to an independent set of vertices is independent (in statistical sense) of the secret itself. The efficiency of a scheme is measured by the amount of information the most heavilyloaded vertex receives divided by the amount of information in the secret itself. The (worst case) information ratio of G is the infimum of this number. We calculate the best lower bound on the information ratio for an infinite family of graphs the celebrated entropy method can give. We argue that all existing constructions for secret sharing schemes are special cases of the generalized vector space construction. We give direct constructions of this type for the first two members of the family, and show that for the other members no construction exists which would match the bound yielded by the entropy method.

Csirmaz L, Ligeti P. On an infinite family of graphs with information ratio $2-1/k$. Computing. Archives for Scientific ComputingComputing. Archives for Scientific Computing. 2009;85(1-2):127-36.

On an infinite family of graphs with information ratio $2-1/k$

In this paper we consider the secret sharing problem on special access structures with minimal qualified subsets of size two, i.e. secret sharing on graphs. This means that the participants are the vertices of the graph and the qualified subsets are the subsets of V(G) spanning at least one edge. The information ratio of a graph G is denoted by R(G) and is defined as the ratio of the greatest size of the shares a vertex has to remember and of the size of the secret. Since the determination of the exact information ratio is a non-trivial problem even for small graphs (i.e. for V(G) = 6), every construction can be of particular interest. Let k be the maximal degree in G. In this paper we prove that R(G) = 2 − 1/k for every graph G with the following properties: (A) every vertex has at most one neighbour of degree one; (B) vertices of degree at least 3 are not connected by an edge; (C) the girth of the graph is at least 6. We prove this by using polyhedral combinatorics arguments and the entropy method.

Secret sharing on infinite graphs

We extend the notion of perfect secret sharing scheme for access structures with infinitely many participants. In particular we investigate cases when the participants are the vertices of an (infinite) graph, and the minimal qualified sets are the edges. The (worst case) information ratio of an access structure is the largest lower bound on the amount of information some participant must remember for each bit in the secret -- just the inverse of the information rate. We determine this value for several infinite graphs: infinite path, two-dimensional square and honeycomb lattices; and give upper and lower bounds on the ratio for the triangular lattice.It is also shown that the information ratio is not necessarily local, i.e. all finite spanned subgraphs have strictly smaller ratio than the whole graph.We conclude the paper with open problems concerning secret sharing on infinite sets.

Secret sharing on the infinite ladder

The notion of perfect secret sharing scheme has been extended to encompass infinite access structures, in particular infinite graphs, in [2]. The participants are the vertices of the graph G and the edges are the minimal qualified subsets. The information ratio of G is the largest lower bound on the amount of information by secret bits some vertex must receive in each scheme realizing this access structure. We show that this value is 7/4 for the infinite ladder, solving an open problem from [2]. We give bounds for other infinite graphs as well.

Secret sharing on trees: problem solved

We determine the worst case information rate for all secret sharing schemes based on trees. It is the inverse of 2-1/c, where c is the size of the maximal core in the tree. A core is a connected subset of the vertices so that every vertex in the core has a neighbor outside thecore. The upper bound comes from an application of the entropy method [2, 3], while thelower bound is achieved by a construction using Stinson's decomposition theorem [7].It is shown that 2-1/c is also the fractional cover number of the tree where the edges of the tree are covered by stars, and the vertex cover should be minimized, cf [5]. We also give an O(n^2) algorithm which finds an optimal cover on any tree, and thus a perfect secretsharing scheme with optimal rate.

A simple algorithm with no simple verification

The correctness of a simple sorting algorithm is presented, which algorithm is "evidently wrong" at the first sight. It is conjectured that the algorithm has no straightforward, transparent verification. The paper is a nice example for the usage of the Floyd-Hoare-Naur verification method.

The perimeter of rounded convex planar sets

A convex set is inscribed into a rectangle with sides a and 1/a so that the convex set has points on all four sides of the rectangle. By "rounding" we mean the composition of two orthogonal linear transformations parallel to the edges of the rectangle, which makes a unit square out of the rectangle. The transformation also applied to the convex set, which now has the same area, and is inscribed into a square. One would expect this transformation to decrease the perimeter. Interestingly this is not always the case. For each a we determine the largest and smallest possible increase of the perimeter. We also look at the case when the inscribed convex set is a triangle.

Secret sharing schemes on graphs

Given a graph G, a perfect secret sharing scheme based on G is a method to distribute a secret data among the vertices of G, the participants, so that a subset of participants can recover the secret if they contain an edge of G, otherwise they can obtain no information regarding the key. The average information rate is the ratio of the size of the secret and the average size of the share a participant must remember. The information rate of G is the supremum of the information rates realizable by perfect secret sharing schemes.Based on the entropy-theoretical arguments due to Capocelli et al, and extending the results of M. van Dijk, we construct a graph on n vertices with average information rate below 4/log n. We obtain this result by determining, up to a constant factor, the average information rate of the d-dimensional cube.

Subpixel image processing

On a grayscale image there are more than three hundred patches of diameter from ten up to thirty pixels. We determinethe center and radius of the pathces with subpixel precision. We use a new geometrical approach, namely the curvatureof the convolution surface at local maxima to measure how good the filter is. The paper introduces this new method andthe mathematical background. It concludes with ideas for furher research.Egy szürke skálájú képen mintegy háromszáz, nagyjából kör alakú, 10 és 30 pixel közötti átmérõjû folt középpontját és sugarát kell lehetõ legnagyobb pontossággal meghatározni. A feladat nehézségét az jelenti, hogyellentétben a képfeldolgozásban szokásos pixeles pontossággal, ennél egy nagyságrenddel nagyobbra van szükség. A megoldásban különbözõ paraméterû szûrõkkel készitett konvolúciók geometriai tulajdonságait használjuk fel; nevezetesen az illeszkedés jóságát a felület lokális maximumában mért görbülete adja meg. A cikkben az újfajta megközelités elemeit és azok matematikai hátterét ismertetjük.

Secret sharing on the d-dimensional cube

We prove that for d > 1 the information rate of the perfect secret sharingscheme based on the edge set of the d-dimensional cube is exactly 2=d.Using the technique developed, we also prove that the information rate ofthe in nite d-dimensional lattice is 1=d.

Zero Knowledge Proofs

An intruduction to zero knowledge protocols. We start with the sock pairing protocol, and touch resettable zero knowledge.

Csirmaz L, Katona GO. Geometrical Cryptography. In: Workshop on Coding and Cryptopgraphy. Cee; 2003. p. 101-11.

A communication protocol

We were interested in designing a communication protocol which can be used to tranfer files between personal computers. We have made a cable which connects the parallel ports, and is able to transfer 2 bits in either direction (instructions in the paper). Using this facility as a primitive, we designed protocols to establish the connection, and protocols to transfer data from one machine to the other. Our protocols did not use any timing, are stable, and extremely reliable.

Csirmaz L. Elliptikus görbén alapuló titkosírás. In: Proceedings of NetworkShop 2002. Eger: Eszterházy Károly Fõiskola; 2002.

Elliptikus görbén alapuló titkosírás

There is a hard-to-solve mathematical problem behind all public key cryptography system.For example, RSA uses the fact that while it is relatively simple to decide whether a number of several hundred digits is composite or not, it is beyond hope to find its prime factors. The so-called discrete logarithm problem is behind the Diffie--Hellman method. This problem can be phrased as follows: given the base and the result of an exponentiation, find the exponent. Here exponentiation is, of course, repeated multiplication, but for the multiplication we always take the remainder when dividing by a given large prime number. The problem can be worded in a more general settings. Given some kind of operation, called multiplication, among several (say 10100or so) objects. Choose a base g, an exponent n, and compute y=gn. The task is to determine the exponent n, given y and g only. Elliptic curves present a mathematical way to come up with such a multiplication. It can be defined easily, computed fast, and only the general, ineffective algorithms are known for the induced discrete logarithm problem. Elliptic curves arise in algebraic geometry, maybe the most beautiful and the hardest part of mathematics. These curves are generalisations of the ones known from secondary school, such as circle, ellipse, parabola and hyperbola. The unit circle, for example, consists of all points with co-ordinates (x,y) satisfying x2+y2=1. The locus of points with y2=x3+ax+b is a typical elliptic curve. On its points we could define a multiplication, which then can be used for a public key cryptographic system as indicated above.

Csirmaz L. Connected Graph Games. Studia Scientiarum Mathematicarum Hungarica. 2002;(39):129-36.

Connected Graph Games

Two players claim alternately edges of the complete graph on n vertices. The winner is the one who makes the spanned subgraph with the claimed edges connected. We determine, for each n, who wins the game. The avoidance version is also considered, where the player who is forced to make the spanned subgraph to be connected, loses the game.

Az elektronikus pénztárca elmélete és gyakorlata

Az elektronikus pénz az Atalantai olimpia szinhelyén, 1996-ban debütált. Azóta elsõsorban Nyugateurópában egyre inkább terjed. A hitelkártya és a kézpénz elõnyeit egyesiti, ráadásul az alkalmazott kriptográfiai eljárásoknak köszönhetõen sokkal biztonságosabb. A hitelkártyával ellentétben az elektronikus pénztárca lehetõvé tesz off-line és kis összegü fizetéseket (például italautomata vagy helyi közlekedés) is, valamint mindkét félnek biztonságos interneten keresztüli fizetéseket.A világon leginkább elterjedt Digicash valamint Visa Cash rendszereken keresztül mutatjuk be a digitális pénzzel szembeni kivánalmakat, és hogy a megoldhatatlannak tünõ feladatokat milyen kriptográfiai módszerekkel sikerült mégis megoldani: * Hogyan készülnek az elektronikus pénzérmék a pénzverdében? * Miért nem baj, hogy ezeket az érméket lehet másolni? * Mi történik fizetéskor? * Milyen biztositékokat nyújt a rendszer az eladónak és milyet a vevõnek? * Mi a helyzet Magyarországon?

Recursive functions of one variable

“The excess function, defined on nonnegative integers, gives, for each n, the excess over the largest perfect square below n, i.e. n − [pn]2. If f maps natural numbers to natural numbers, and takes all possible values, then the inverse of f is also defined, and at place n takes i if i is the smallest argument for which f(i) = n. We prove the following nice theorem of J. Robinson. Consider the smallest set S of functions from natural numbers into natural numbers with the following properties: (i) the identity, the successor and the excess functions are in S, (ii) S is closed under composition and taking inverse. Then S is the set of recursive functions of one variable.”

Program correctness on finite fields

An asserted program is presented whose correctness is provable by the Floyd-Hoare-Naur method in each finite field separately, which, however, admits no universal derivation, i.e. one which would work on all but finitely many finite fields of a given characteristic. Also, it is proved in general that if "executing a program twice with the same input, the outputs agree" is a provable property, then the output of the program is first order definable from the input.

The dealer's random bits in perfect secret sharing schemes

A secret sharing scheme permits a secret to be shared among participants of an n-element group in such a way that only qualified subsets of participants can recover the secret. If any non-qualified subset has absolutely no information on the secret, then the scheme is called perfect. The share in a scheme is the information what a participant must remember. It was known that in any perfect secret sharing scheme realizing a certain collection of qualified sets over n participant, at least one participant must use at least O(n/log n) random bits for each bit in the secret. Here we present a collection of qualified sets so that the total number of random bits used by all the participants, i.e. the dealer's random bits is at least O(n^2/log n) for each bit in the secret.

Csirmaz L. The size of a share must be large. In: Advances in cryptology---EUROCRYPT '94 (Perugia). 950: Springer; 1995. p. 13-22. (Lecture Notes in Comput. Sci.).
Csirmaz L. DIMACS technical report, 90-25. [S.l.]: DIMACS, Center for Discrete Mathematics and Theoretical Computer Science; 1990.
Csirmaz L. DIMACS technical report, 90-28. [S.l.]: DIMACS, Center for Discrete Mathematics and Theoretical Computer Science; 1990.
Csirmaz L. DIMACS technical report, 90-29. [S.l.]: DIMACS, Center for Discrete Mathematics and Theoretical Computer Science; 1990.
Csirmaz L. Nonstandard logics of programs. In: Algebra, combinatorics and logic in computer science, Vol. I, II.; 1983. p. 285-94.
Csirmaz L. Nonstandard runs and program verification. Bulletin of Sect. of Logic, Polish Acad. Sci.. 1981;(10):68-74.
Csirmaz L. Theorems and problems about nonstandard dynamic logic. Proceeding of Work- shop on Algorithms, Technical Univ. of Poznan. 1981:17-9.
Csirmaz L. Remarks on Floyd–Hoare derivability. Bulletin of Sect. of Logic Polish Academy of Sci.. 1980;(9):131-5.
Csirmaz L. On definability in Peano arithmetic. Polish Acad. Sci. Inst. Philos. Sociol. Bull. Sect. Logic. 1979;8(3):148-53.