|
|
Graph coloring and formal grammars
Elichová, Sára ; Holub, Štěpán (advisor) ; Barto, Libor (referee)
This thesis deals with two equivalent reformulations of the four color problem. The first of them shows the connection between graph coloring and the vector cross product; the se- cond one expands on it and develops a relation to a formal grammar. These reformulations together with the proofs of their equivalence to the four color theorem are the results of two articles motivated by the effort to find a simpler proof of the famous problem, which was proved only by computer. They bring an interesting perspective on the problem of graph coloring and give the possibility to look on it in a new way, which could turn out to be more approachable. This thesis presents the proofs introduced in the source li- terature and adds the steps that are not elaborated in detail by the authors. It aims to formalize some of the ideas and to contribute to the comprehensibility of the proofs. 1
|
|
|
Representing Images by Weighted Finite Automata
Hurtišová, Viktória ; Holub, Štěpán (advisor) ; Žemlička, Jan (referee)
The goal of this thesis is to introduce weighted finite automata (WFA) as a means of representing multi-resolution raster images. We explain the basic concepts of weighted finite automata. Then we describe an encoding algorithm that converts an image into a WFA and a decoding algorithm that can generate back the original image. We then provide our implementation of the encoding and decoding algorithms. 1
|
|
| |
|
| |
|
|
Analysis of the stream cipher QUAD
Čurilla, Marcel ; Holub, Štěpán (advisor) ; Příhoda, Pavel (referee)
Title: Analysis of the stream cipher QUAD Author: Marcel Čurilla Department: Katedra algebry Supervisor: doc. Mgr. Štěpán Holub, Ph.D. Abstract: Stream cipher QUAD was introduced in 2006 on Eurocrypt by Côme Ber- bain, Henri Gilbert a Jacques Patarin cite quad. The authors showed a reduction of this cipher for the problem of solving m quadratic equations of n variables over finite fields known as the MQ problem. For simplicity, they considered only the case of the field GF(2). In this thesis I introduce this stream cipher. I show the proof (reduction) of safety ciphers QUAD for MQ problem over any finite field GF(q). I describe the basic met- hods for the solution of system of quadratic equations over finite fields, linearization and relinearization. I focus on XL algorithm - which is currently the fastest algo- rithm for solving quadratic systems. This algorithm was designed precisely to deal with overdefined quadratic systems. While analyzing the cipher QUAD I show for what instance is a cipher QUAD breakable and vice versa for what instance is the security guaranteed. Keywords: stream cipher, QUAD, MQ problem, algorithm XL, 1
|
|
|
Covering sets in steganography
Vacek, Jan ; Holub, Štěpán (advisor) ; Hojsík, Michal (referee)
Steganography is a science which is interested in communication hiding. This work is focused on the most recent methods related to this topic. Mainly, it is matrix embedding, which uses coding theory, and sum and difference covering sets (SDCS). Rainbow coloring of grid graphs is used to receive even better results. This technique decrease amplitude of performed changes. It makes stegosystems less likely to be detected. Properties which describe behavior of each stegosystem are included for each technique. 1
|
|
|
Squares in integer sequences
Hudcová, Barbora ; Holub, Štěpán (advisor) ; Bulín, Jakub (referee)
This work is based on an article which provides a construction of the first infinite word over a finite alphabet avoiding additive cubes. We construct other words with the same properties and we choose one of them to show the main idea of the proof that this word avoids additive cubes. 1
|
|
| |
|
|
Compressing Pseudorandom sequences
Vald, Denis ; Holub, Štěpán (advisor) ; Růžička, Pavel (referee)
Generators of pseudorandom sequences are widely used objects, not in the least place because of their application in stream ciphers. One of the ways to improve resistance to different types of attack is to use compression on the generated sequence in order to remove redundant information, that might lead to an attack against the generator. In this work we try to explore from a wider perspective the theoretical foundations for compressing pseudorandom sequences created thus far. Using this general view we will examine some known attacks against the PRN generators and look for a way to resist such attacks.
|
|
|
Binary equality words
Hadravová, Jana ; Holub, Štěpán (advisor) ; Stanovský, David (referee)
Binary equality language is a set consisting of all solutions of equation g(w) = h(w), where g, h are arbitrary binary morphisms. Recently, it has been prooved that equality set for each pair of morphisms g, h is generated by at most two words. Structure of binary equality language has been already known in the case that at least one of morphisms g, h is periodic or if their equality set is generated exactly by two words. The main objective of the paper was to find a structure of solutions for morphisms whose equality set is generated by one word. The problem in general case remains unsolved but special result for solutions consisting of just one block for marked morphisms was discovered. Using methods established in this paper (covering by the same pattern to find n-multiple p-overflows and working with the cyclic pair (e, f, z)) it is believed that some more results can be achieved in the near future.
|
guest ::
