szavak kombinatorikája, kriptográfia, titokmegosztás
Keywords in English
combinatorics on words, cryptography, secret sharing
Discipline
Mathematics (Council of Physical Sciences)
100 %
Ortelius classification: Combinatorial analysis
Panel
Mathematics and Computing Science
Department or equivalent
Department of Computer Algebra (Eötvös Loránd University)
Starting date
2012-02-01
Closing date
2015-01-31
Funding (in million HUF)
13.983
FTE (full time equivalent)
2.10
state
closed project
Summary in Hungarian
A matematika különböző területeinek találkozása gyakran érdekes problémákat és megoldásokat szül. A kriptográfiának első pillantásra nem sok köze van a kombinatorikához, mivel a hagyományos kriptográfiában elsősorban számelméleti, algebrai vagy statisztikai ötleteket használnak. Azonban számos kombinatorikai módszernek és struktúrának lehet fontos szerepe az elméleti kriptográfia különböző területein. A projekt keretén belül tisztán kombinatorikai és kriptográfiai problémák vizsgálatán túl a fő cél ilyen metszéspontok felfedezése és kiaknázása.
Az első témakör a szavak kombinatorikája, amin belül egy speciális kombinatorikus rekonstrukciós feladat és általánosításai állnak a középpontban a keletkező struktúrák kombinatorikai jellemzésével együtt.
A ''második K'' esetében elsősorban titokmegosztási sémák vizsgálata a cél, melyek számos kriptográfiai eljárás alapvető komponensét képezik. A vizsgálatok tárgyai olyan keveset vizsgált területek, mint az úgynevezett rámpa rendszerek, valamint a végtelen konstrukciók.
Végül, de nem utolsó sorban kombinatorikai eszközök kriptográfiai alkalmazási területeit vizsgálom, úgy mint titokmegosztás gráfokon, speciális gráf-fedések jellemzése, illetve matroideméleti módszerek.
Summary
The meeting of different fields of mathematics often arises interesting problems and solutions. For the first sight cryptography has not much connection to combinatorics, since traditional cryptographic techniques primarily include number theoretical, algebraic or statistical ideas. However there are several combinatorial methods and structures that play an important role in theoretical cryptography. Within this project in addition to examine purely combinatorial and cryptographic problems the main goal is to discover and apply such intersections.
The first topic is combinatorics on words where a special combinatorial reconstruction problem and its generalizations are in focus as well as the combinatorial analysis of the resulting structures.
For the ``second C'', I will study secret sharing schemes primarily, which is a basic component of several cryptographic methods. The research will focus on relatively undiscovered areas, such as ramp schemes and infinite constructions.
And last but not least I will study the application areas of combinatorial tools in cryptography, like secret sharing on graphs, characterization of special graph-coverings and methods from matroid theory.
Final report
Results in Hungarian
Kutatásaim eredményei alapvetően három témakörbe sorolhatóak. Tisztán kombinatorika témában mátrixok különböző részmátrixokból való rekonstruálásával, valamint a keletkező struktúra jellemzésével foglalkoztam. Kriptográfia témában egyrészt kevés résztvevős, kriptográfiailag biztonságos algoritmusok kidolgozásával foglalkoztam, szavazási és árverési protokollokat dolgoztam ki. Másrészt nyílt hálózatokat használó biztonságos adatmegosztással foglalkoztam. Végül, de nem utolsó sorban kombinatorikai módszerek kriptográfiai alkalmazásait vizsgáltam, úgymint gráfalapú titokmegosztásokra vonatkozó eredmények általánosítása, valamint hipergráfok particionálása és kapcsolata a titokmegosztással.
Results in English
The results of my research can be partitioned into three main topics. Pure combinatorial results are the reconstruction of matrices from its different submatrices and the description of the underlying structure. From the crytography point of view, on one hand, I designed cryptographically secure algorithms on few participants, like boardroom voting and auctioning schemes. On the other hand, I worked on secure data sharing methods using open communication channels. Last but not least, I studied the application areas of combinatorial tools in cryptographic problems, like generalization of graph-based secret sharing, hypergraph-partitions and its connection to secret sharing.
Ligeti Péter: Matrix posets and automorphisms, Japanese-Hungarian Symposium
Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, 2013
