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.

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 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.

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.

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.

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?

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.