New era in cryptology is broadly dated to mid seventieth. In the same time we count the most fruitful period of a Semigroup theory seminar whose leading person was Professor Š. Schwarz. His non-trivial contribution to the Coding theory, Number theory and Finite fields is know all over the world. This was a very good bases for some of his graduate students and co-workers to be forwarded to study different problems arising from cryptology, especially from an algebraic point of view. In 1984 we started to teach a course "Secret communication in computer networks" for postgraduate study (PhD) at the former EF SVŠT as the first in former Czechoslovakia. This course was attended by many experts of the whole ČSSR for more than 4 years. In the same year O. Grošek wrote the first Lecture Notes for these students. In 1985 O. Grošek (EF SVŠT) and K. Nemoga (MÚ SAV) decided to establish a new seminar CRYPTO. It was established in 1986 in cooperation with other people, like P. Volauf from KM EF SVŠT, Š. Porubský, O. Štrauch, I. Žembery, M. Laššák and S. Jakubec from MÚ SAV, P. Farkaš from KTL EF SVŠT and J. Vyskoč from VS SAV. CRYPTO - seminar was attended by experts from MFF UK, MÚ SAV, KM EF SVŠT and other scientific institutions. We were mainly reading a journal CRYPTOLOGIA, published in Indiana, USA. In that time, for us, this was the only one available journal in the field. CRYPTO - seminar temporarily ended in November 1989. Since the same year we started a cooperation with one of the best known centers all over the world in that time, namely in Lincoln, Nebraska.
In 1990 we opened a course Ciphering for all students of MFF UK and FEI STU. Publishing house GRADA has published the first monography of this area in Slovak in 1992: Šifrovanie - metódy, algoritmy, prax, written by O. Grošek and Š. Porubský. (As far as we know, before there was written in ČSR only one publication by Jaromír Lichtner Šifrování: úvod do kryptografie chemické, grafické, čtyřidceti šifrovými klíči. Alojz Srdce Pub. 1939.)
In February 1993 our seminar started to work again at the Department of Mathematics FEI STU under new circumstances. Great challenge for founders had also been an offer for cooperation from the former director of Central Security Agency of the Ministry of Interior, Ing. Eduard Puffler. In the school year 1996/97 the seminar was not public because of specific tasks solved for MV SR.
In 1995 has begun a course Ciphering for regular students, and there were set off the first Bachelor's projects and Diploma Theses in this area. These projects include both practical and theoretical problems of cryptology. Since the same year we have graduate students in the field of 25-11-9 Applied Informatics, and also (since 1997) 11-14-9 Applied Mathematics.
Cryptology is unquestionably counted as one of the most attractive theories in both Applied Mathematics and Computer Science. Hence it is not surprising that there is a very close cooperation between our Department of Mathematics and Department of Computer Science and Engineering.
Since 2000/01 at the Department of Mathematics, and in cooperation with the Department of Computer Science and Engineering, we have the first Masters degree students in the field of Security of Information Technologies. All of these activities allowed FEI STU in Bratislava to be the leading institution in Slovakia in the area of Applied Informatics, including Computer Security. There is a large cooperation with governmental institutions, eg. Ministry of Interior (7 finished technical reports), Ministry of Defense (1 finished technical report), and National Bank of Slovakia (7 realized special seminars). Some parts of research projects may belong to the area of Applied Informatics and comprises problems lying within the scope of different parts of Computer Science, Cryptology, Algebra, Informatics, and other parts of Discrete Mathematics. Given areas are getting closer, emphasize each other, interlace. Clearly, the borderline problems emerged. It seems that combining the methods characteristic for particular areas should be the approach how to solve them, i.e. to take a look at the problems from different points of view. To be a part of a solution of real problems, beginning 1996 we are participating in grants from Computer Science. From our Department, in all projects have participated O. Grošek and L. Satko. Gradually they were followed by Š. Porubský, K. Nemoga, H. Lichardová, M. Adámyová - Šimovcová, M. Vojvoda and M. Greško.
Next we are introducing principal results of research projects in the field of cryptology where we contributed.
This research project belonged to the area of pure mathematics. There were mathematicians working in algebra, cryptology and combinatorics participating in it. The program covered wide spectrum of problems. More specifically we were studying various generalizations of a notion of ideal in semigroups, and possibility of their utilization in coding theory, cryptology and formal languages. In this program we cooperated with several universities, eg. University of Nebraska, Simon Fraser University, McMaster University, University of Hawai, Computer and Automation Institute in Budapest, University of Tel Aviv, Milton Keynees University. The notion of A-ideal has its impetus in three notions as the notion of difference sets on groups (Bruck), mild ideals (Putcha) and quasy-zero (Ries). This notion has also been used in papers concerned with formal languages and cryptology, namely for so called access structures. The main result was in description of such structures especially in the case when difference sets do not exist. Our contributions described also a possibility of using Walsh-Hadamard transform to charcterize finite semigroups and groups as well as an application of these results in design of so called S-boxes. Another problem arising from cryptanalysis of Markov block ciphers was to show to what extent it is possible to reconstruct a Markov Chain with finitely many states from a given (observed) finite but sufficiently large part of a trajectory. Here, by a reconstruction we mean finding as many as possible transition probability matrices leading to an estimated final probability distribution. This problem was solved with respect of the quasi-norm max pij of transient matrices belonging to a primitive idempotent.
We presented our results on 23 international conferences, including "A SEMIGROUP MEETING".This was the name of an International conference held on May 29-31, 1994 on the occasion of 80 years of Professor Štefan Schwarz. Organizing and Programm Committee (K.H. Hofmann, Š. Porubský, L. N. Shevrin, L. Satko and O. Grošek), decided to introduce participants of the conference an outline of branches of mathematics, where the jubilee has mainly contributed. Of course, results related to cryptology were included too.
Another event was a visit of famous mathematician Paul Erdös from Hungarian Academy of Sciences. During his stay, Sep. 23-29, 1994 he gave a lecture "Problems in Combinatorics and Number theory". At the same time P. Horák solved together with Erdös one of his colouring problerms.
Department of Mathematics joined this project in the last year of its duration only. Our contribution consisted of study of DES-like cryptosystems, and the study of so called bent-like functions on quasi-groups, a very perspective construction which has been involved by us, and referred in the USA and Greece. We also started in giving special classes for extra talented students interested in the field, and getting on in projects of breaking practically DES and McEliece cryptosystems. Further, in designing an on-line cryptosystem based on IDEA and Blowfish as well as to design an applicable electronic cash model at least in a local network. Moreover we organized a Summer School on Cryptanalysis in Liptovský Mikuláš. There were presented nowadays methods to break stream ciphers. The conference was organized in cooperation with MÚ SAV and Military Technical Institute in Liptovský Mikuláš.
We presented our results on 6 international conferences.
Main goals in the area of Cryptology and Discrete Structures were to study methods of finding suitable Boolean functions for DES-like cryptosystems, algorithms for finding strong primes on the basis of Pockhlington lemma, acceptable by all short exponents up to 1024 bits, and Complexity Theory of RSG based on Luby - Rackoff lemma. We took advantage of a close cooperation with the Department of Mathematics, Institute of Chemical Technology, Prague, CZ; Computer Science Department., University of Nebraska, Lincoln, USA and Computer Science Department, De Montfort University, Milton Keynees, GB. During this project, members of the research team participated domestic and international conferences with their own contributions.
We analyzed a collision attack, applied to the modified GOST algorithm, and proved that if non-bijective S-boxes
are used in the algorithm then it is feasible to break it when a weak key is in use.
Studying a specific random number generator we proved that the approach to this type of generators by U. Maurer
is different to that of Luby - Rackoff, serving a new sight in classification of random sequences. We also focused
to RSA alorithm and proved that approximately 3% of randomly generated 512 bits long strong primes can be used
with arbitrary short exponent, s = 2k+1, 0
Studying stream ciphers we did cryptanalysis of one clock-controlled running key generator, and found explicit
equations for this generator. Computer simulation has shown a large linear complexity and long period of the
produced keystream sequence. The generator is resistant to fast correlation attacks but fails to presented
known plaintext attack.
We presented our results on 22 international conferences.
In September 1998 we have started, in cooperation with Ministry of Interior and National Bank of Slovakia,
special seminars for people working in financial e-banking and related areas. By the end of 2000 there were
seven of them. Number of participants varies from 15 to 30, and during this period they got more than 1200 pages
of lecture notes. Details are available on our web-page
Studying stream ciphers we did cryptanalysis of one clock-controlled running key generator, and found explicit equations for this generator. Computer simulation has shown a large linear complexity and long period of the produced keystream sequence. The generator is resistant to fast correlation attacks but fails to presented known plaintext attack.
We presented our results on 22 international conferences.
In September 1998 we have started, in cooperation with Ministry of Interior and National Bank of Slovakia, special seminars for people working in financial e-banking and related areas. By the end of 2000 there were seven of them. Number of participants varies from 15 to 30, and during this period they got more than 1200 pages of lecture notes. Details are available on our web-page (http://www.elf.stuba.sk/Katedry/KM/crypto).
Targets of this project can be divided into several parts. On the basis of so called A-ideals we would like to design a new generation of S-boxes, a main nonlinear part of any iterated DES-like cryptosystem. Further, we are trying to distinguish S-boxes by a new criteria, namely via all groups of order 16. Concretely, Pieprzyk suggested to study mod 16 linear behavior of DES S-boxes. Using our experience in the semigroup theory, translations and morphism of such structures we would like to study this kind of attack in general. As concerning stream ciphers, we will study several constructions of pseudorandom sequences with good non-linearity, difference parameters, correlation immunity and spectral properties. We would like to involve students to the theory via specialized seminars, semester projects and diploma theses. Following this we are heading them towards trying to repeat some successful attacks on DES-like cryptosystems using parallel programing and special sophisticated sorting algorithms. The expected contribution is both of theoretical and practical character and will serve to the further development of cryptology. We are focusing on problems belonging nowadays to the centre of interest in the field.
Up to these days we presented our results on 17 international conferences. O. Grošek was an invited speaker at CITEDI-IPN, Tijuana, Mexico where he gave two lectures for graduate students, and at University Autonomia de Baja California in Ensenada, Mexico a plenary lecture.
Partial results are as follows:
In June 2001, we are organizing an International conference TATRACRYPT '01
A list of people working in the field beyond the borders is nearly endless. Thus, continuing in our CRYPTO seminar, organizing workshops participating by leading experts in the field, and ourselves participating at foreign conferences we would like to be both informed, and inform researchers about our recent results. Moreover, since there are many particular problems which might be solved by students, some particular results are gained also by semester and diploma projects, too. Up to these days 3 people finished their Ph.D thesis, and 15 Master thesis related to cryptology has been finished too. Members of our CRYPTO group has published 41 scientific papers, and 23 other papers related to cryptology . At present we have 8 graduate students.
Written by O. Grošek and L. Satko, May 31, 2001.