Search

Title: Kerdock codes and around Author: Kateřina Teplá Department: Department of algebra Supervisor: prof. RNDr. Aleš Drápal, CSc., DSc., Department of algebra Abstract: Kerdock codes form a family of nonlinear codes, that contains more codewords than any known linear code with the same parameters. The main goal of this thesis is a connection of Kerdock codes with other areas of mathematics, mainly orthogonal geometry, combinatorics and cryptogra- phy. It describes theory of symplectic and quadratic forms on vector spaces of characteristic 2 and its relationship to Kerdock codes. Then it is pro- ven, that codewords of Kerdock code of constant weight form combinatorial 3-design. Finally usage of Kerdock codes in construction of Boolean bent functions and t-resilient functions, that are basis of many cryptographic pri- mitives, is analysed. Keywords: Kerdock code, Kerdock set, t-design, resilient function 1

Low-density parity-check (LDPC) codes are linear error correcting codes which are capable of performing near channel capacity. Furthermore, they admit efficient decoding algorithms that provide near optimum performance. Their main disadvantage is that most LDPC codes have relatively complex encoders. In this thesis, we begin by giving a detailed discussion of the sum-product decoding algorithm, we then study the performance of LDPC codes on the binary erasure channel under sum-product decoding to obtain criteria for the design of codes that allow reliable transmission at rates arbitrarily close to channel capacity. Using these criteria we show how such codes are designed. We then present experimental results and compare them with theoretical predictions. Finally, we provide an overview of several approaches to solving the complex encoder problem.

This work deals with three different constructions of the extended binary Golay code G24. The first construction is based on a projective plane of order four. In terms of it Steiner system (5, 8, 24) is built. Linear span of its blocks forms a linear binary [24, 12, 8] code C. Every binary [24, 12, 8] code is isomorphic to C which is known as extended binary Golay code G24. The second construction uses so-called Miracle Octad Generator (MOG). All MOG-words of weight eight form Steiner system (5, 8, 24). The third construction uses impartial combinatorial game Mogul. In terms of its P-positions one can create a linear binary [24, 12, 8] code. The fact that is is also a lexikographic code is useful for parametres estimate. 1

In the presented work we define a class of error-correcting codes based on incidence vectors of projective geometries, including the necessary basis of coding theory and projective geometries. A detailed calculation is performed to show the dimension of these codes. In conclusion we concern ourselves with majority decoding. This work is a summary of the results of some known authors engaged in this field. We continue on some of these results and we present evidence of some of the statements, which have been proven differently by other authors.

The thesis focuses on an algebraic description of S-boxes by the special type of quadratic equations, defined as biaffine equations. Biaffine equations satisfying S-boxes of higher order may not even exist. However, the special type of S-boxes en- ables to find such equations also for S-boxes of higher order. The S-box in the block cipher Rijndael, composed of the inverse function and the affine transformation, is an example of such special type of S-boxes. The thesis proves that a number of biaffine equations satisfying an S-box of this type does not depend on the affine function. The thesis also proves that for every S-box of order n formed by the in- verse function there exist at least 3n − 1 biaffine equations satisfying this S-box. 1

Title: Even triangulations and Abelian groups Author: Michal Hrbek Department: Department of Algebra Supervisor: prof. RNDr. Aleš Drápal CSc., DSc. Abstract: This thesis takes interest in spherical Eulerian triangulations and the algebraic structure defined on its vertices corresponding with the latin bitrade equivalent to the triangulation. First, we introduce needed results about the properties of the triangulations and their embeddings into Abelian groups. Then we get concerned with a particular kind of almost 6-homogenous triangulations. The text presents several examples, then the groups of the simplest sequence of triangulations are explicitly described. In order to investigate more complicated cases, we introduce a recursive formula for defining relations of the groups and we show an example of its usage with modular arithmetic. The thesis is completed by discussing computed data. Keywords: latin bitrade, eulerian triangulation, Abelian group 1

Title: Frobenius primality tests Author: Jan Hora Department: Department of algebra Supervisor: prof. RNDr. Aleš Drápal, CSc. Dsc. Supervisor's e-mail address: drapal@karlin.mff.cuni.cz Abstract: In the present work we study Extended Quadratic Frobenius primality test. We study its functionality, error probability and taken time. We will define ring R(n, c), in which the test works. We will describe its structure depending up primality of tested number n, and algorithm of Frobenius test. We will show, that test succeeds anytime the tested number n is prime. We will study the upper bound for error probability of the test. We will show that test fails iff certain elements of set R(n, c) are chosen, Set of that elements will be denoted G(n, c). We will find conditions that G(n, c) must fulfil, and with them we will discover, that Frobenius test eroor probability is at most 1 24 . We will analyse individual parts of algorithm and discover, that one cyclus of Frobenius test can be done with approximately 2 log n multiplications in Zn. Finaly the teoretical estimates will be compared with practical results. Keywords: primality test, Frobenius automorfism, cyklic group, roots of one 1

In this thesis, we study some properties of MDS codes and we mainly focus on the MDS codes conjecture. In the first chapter we define MDS codes, show some examples and basic properties of MDS codes, for example a link between MDS codes and Latin squares or rectangles. Afterwards we state the MDS codes conjecture and prove it in several cases. In the third chapter we can observe the relationship between MDS codes and narcs in projective geometries. Finally we present those known cases, for which the MDS conjecture holds.

In the present work we study a security of the AES cipher. We concern in a mathematical representation of a block cipher and how to use it to algebraic attacks. We show a summary of known algorithms which are useful for these attacks. We show how to convert problem of solving the system of polynomial equations to SAT problem and we describe how SAT solvers work.

In the rst part of this work we study the complexity of solving nonlinear quasigroup equations for di erent classes of quasigroups. In particular we study the application of principle of central quasigroups on the blocks of congruence. We show that these quasigroups can be shapeless and therefore we gain counterexample to the hypothesis which was stated by D. Gligoroski. In the second part of this work we apply previous results on the concrete quasigroups of the type Edon-R-I,II and we deduce the complexity of the corresponding algorithm for inverting the hash function Edon-R.

In the present work we study a class of generalised inner states of the cipher RC4, the so-called persistent states. The RC4 stream cipher is the most widely used software-based stream cipher and the existence of such a state would be a significant weakness of the cipher. We describe the Tabular model and using the model we prove the periodicity of these states. Then we study a new type of relationship between the tabular model and the equivalences on linearly ordered sets and we prove the regularity of the matrix determined by such an equivalence. Afterwards we apply the obtained result to the theory of persistent states and we prove that there exists no reachable persistent k-state for k equal to 2, 3, 4 in the specific case. Moreover, we present some new unreachable persistent states. Finally, we indicate the cryptanalytical significance of the persistent states.

In this work we study the number field sieve algorithm. Our main focus is on its theoretical background. We present all important theorems which are needed for a full understanding of the algorithm. We also describe the most widely used implementation of the parts of the algorithm and we discuss in which situation they should be used. At the end we show results from measurements of sieving phase on the implementation which was written for our Department of Algebra.

In this work, we study some properties of an in nite matrix, which consists of quasigroup elements. This matrix is generated from a certain sequence X using left iterated translations. We suppose that the sequence X is periodic and we examine how the periods of the rows of our matrix behave for various types of quasigroups. We show that for central quasigroups the periods increase at most linearly. Further, we try to apply our result to the stream cipher Edon-80.

Public-key cryptographic schemes based on the complexity of solving multivariate quadratic equations over a finite field represent an alternative to widely used schemes relying on the complexity of factorization or on the discrete logarithm. Such a scheme was proposed by D. Gligoroski et al. [8]. Keys in this scheme are constructed using a special kind of quasigroups, the socalled quadratic quasigroups. In this paper we try and describe the quadratic quasigroups and classify them according to their properties. Finally, we present a theory which can be used to generate such quasigroups.

Modern steganography is a relatively new discipline with many applications in information security. Contrary to the cryptography which is trying to make a message unreadable to third party using cryptographic algorithms, the aim of steganography is to hide a communication between parties. Applications of error-correcting codes and covering functions markedly increases abilities and security of steganographic algorithms. This thesis is attended to steganography using error-correcting codes which has the best results nowadays regarding embedding efficiency. New constructions will help us to work with non-linear codes and providing new steganographic algorithms. We will see that these algorithms have a better ability to hide communication, resp. a message in a digital medium. Further improvements can be made using applications of general q-ary codes. Many new questions are coming out with that which need to be answered. Several comparisons are showing that the area of steganography is in a beginning and we will be participants of such a progress as cryptography experienced in the last two decades.

Xazev praee: Reed-Solomonovy kody a jejich aplikaco Autor: Pavel Iloral Katcdra (ustav): Katedra Algebry Vedouci bakalafsko prace: Doc. RNDr. Ales Drapal. CSc. c-nia.il vedoiiciho: drapar^karlin.mil', cuni.cz Abstrakt: Prace podava ucelenon definici klasiekyeh Reed-Solomonovych kodn, vcetne potfobuyeh zakladu tcxjric1 k()du. Je dokazana cykliciiost RS kodn delky q - I . Na cyklienosti jsou pak zalozeny tri inx'zontovane dekcklovac'i algoritmy fPetersonnv, Rorlrkain])-Mas.seyuv a Enklidi'iv dekodova.ci algoritmns), vcetne. dukazfi existcniee feseni. V ])oslodni ka])itole uvadiin nckolik a.]>likaci RS kodu, vcetne nejznainejyiho standardu CIRC' pouzivancho na Imdebnich CD. Klieova alova: .s;nnoo])ravny k(5d.1'X'C, Reed-Solomon. Pcterstm, Berlekanip-Massey. Euklid. CIRC1 Title: Rood-Solomon codes and applications Author: Pavel llora.1 Department: Department of Algebra Supervisor: Doc. HXDr. Ales Drapal, CSc. Supervisor's e-mail address: drapal (fkarlin.nirl.ouni.c/ Alislracl: This work presents compact definition of classic Heed-Solomon codes with necessary elements of coding theory. The ryclicity of RS codes of length q - 1 is prooved and there are comletely described three decoding algorithms (Peterson's, Berlekamp-Ma,ssoy and Euclid decoding algorithm) based on RS cyclirity. I also in- troduce a few RS...