|
|
Decoding of Reed-Solomon Codes
Procházka, Dalibor ; Žemlička, Jan (advisor) ; Šťovíček, Jan (referee)
Reed-Solomon codes are a typical example of MDS codes, that are frequently used in practise. In this thesis, we go over three different algorithms of decoding these codes, including the initial view from the original article, as well as the modern approach of currently used algorithm and of another possible efficient algorithm. We compile various sources and unite them under the same notation. We describe in detail the theory be- hind each algorithm, show its correctness, discuss every algorithm's time complexity and demonstrate its steps on simple examples. 1
|
|
|
Cryptosystems based on coding theory
Parýzková, Zuzana ; Žemlička, Jan (advisor) ; Göloglu, Faruk (referee)
Nowadays public-key cryptosystems such as RSA are threatened by quantum comput- ing. Therefore, a post-quantum standardization process was initiated by NIST in 2017. As of today, several cryptosystems have been selected for standardization and several still remain in the process. A cryptosystem based on coding theory - Classic MeEliece - is one of the cryptosystems that might be standardized. This thesis covers McEliece and Niederreiter cryptosystems as well as their rank-metric variants (GGPT cryptosystem). Sidelnikov-Shestakov's attack is explained in detail and an example of the attack is given. Stern's and Overbeck's attacks are discussed as well. Furthermore, a new polynomial-time attack against GGPT without distortion matrix X is given. 1
|
|
|
The image of the internal politics of Wenceslas I between 1230 and 1240 in diplomatic sources
Jeřichová, Jana ; Izdný, Jakub (advisor) ; Žemlička, Josef (referee)
My work deals with internal policy of Wenceslas I between 1230 and 1240, mostly through diplomatic materials. It is devided according to recipients of Wenceslas' charters to several categories - first of all the church, which was the biggest recepient of Wenceslas' charters. Wuthin the church, charters for religious orders which are in the focus of the part decribing the church prevailed. The towns, nonclerical elite, the relationship betweenthe king and Moravian margrave Přemysl and presence of queens in the diplomatic materials are the other focuses of the work. Key words: Wenceslas I, Bohemian kingdom, 13th century, diplomatical sources, internal politics
|
|
|
Application of invertible elements in a zero-knowledge proof
Kučerová, Karolína ; Žemlička, Jan (advisor) ; Příhoda, Pavel (referee)
This work is focused on the description of one verifiable encryption scheme, specifically a zero-knowledge proof of knowledge protocol. Verifiable encryption allows us to prove properties of data without revealing its content. The main goal of the presented method is verification of knowledge of a secret key. This method can be used for group signa- tures, multiple steps secret sharing, key escrow protocols, and many others cryptographic protocols. It is based on the hardness of the Ring-LWE problem and problems of finding solutions to linear relations over some ring. It uses the principle of rejection sampling. The method is build on two closely described cryptographic protocols, Ring-LWE and Fiat-Shamir with aborts. It uses the construction of polynomial rings R = Z[x]/(xn + 1) a Rq = Zq[x]/(xn + 1). 1
|
|
|
Multivariate polynomial commitment schemes
Bžatková, Kateřina ; Hubáček, Pavel (advisor) ; Žemlička, Jan (referee)
This thesis focuses on polynomial commitment schemes - cryptographic protocols that allow committing to a polynomial and, subsequently, proving the correctness of evaluations of the committed polynomial at requested points. As our main results, we present new schemes that enable committing to multivariate polynomials and efficiently proving the correctness of evaluations at multiple points. As the main technical tools for our constructions, we use theorems from abstract algebra related to ideals of polynomial rings and some group-theoretic properties. Compared to the state-of-the-art that inspired our work, our main contribution is the improved communication complexity achieved by our protocol.
|
|
|
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
|
|
|
Structural and categorical description of classes of abelian groups
Dvořák, Josef ; Žemlička, Jan (advisor) ; Modoi, George Ciprian (referee) ; Příhoda, Pavel (referee)
The work presents results concerning the self-smallness and relative smallness properties of products in the category of abelian groups and in Ab5-categories. Criteria of relative smallness of abelian groups and a characterization of self-small products of finitely generated abelian groups are also given. A decomposition theory of UD-categories and in consequence a unified theory of decomposition in categories of S-acts is developed with applications on (auto)compactness proper- ties of S-acts. A structural description of compact objects in two categories of S-acts is provided. The existence of projective covers in categories S − Act and S − Act0 and the issue of perfectness of a monoid with zero are discussed. 1
|
|
|
R-projectivity
Fuková, Kateřina ; Trlifaj, Jan (advisor) ; Žemlička, Jan (referee)
A module over a ring R is R-projective if it is projective relative to R. This module- theoretic notion is dual to the notion of an R-injective module that plays a key role in the classic Baer's Criterion for Injectivity. This Thesis is concerned with the validity of dual version of Baer's Criterion. It also introduces a concept of projectivity in a general category-theoretic setting. DBC is known to hold for all perfect rings. However, DBC either fails or it is undecid- able in ZFC for non-perfect rings. In this Thesis we deal with the subclass of non-perfect rings, which are small, regular, semiartinian and have primitive factors artinian. Trlifaj showed that there is an extension of ZFC in which DBC holds for such rings. Especially, it is enough to consider extension of ZFC in which the weak version of Jensen's Diamond Principle holds. This combinatorial principle is known as the Weak Diamond Principle. Apart from an overview of the properties of rings mentioned above and introduction of the necessary set-theoretic notions, the Thesis also contains a proof of this new result by Trlifaj published in the paper "Weak diamond, weak projectivity, and transfinite extensions of simple artinian rings" in the J. Algebra in 2022. 1
|
|
|
Functional encryption for quadratic functions
Sýkora, Josef ; Žemlička, Jan (advisor) ; Růžička, Pavel (referee)
In this thesis we will be studying functional encryption for quadratic functions. We want to encrypt a message, in form of a vector, z to a plaintext ct and create a secret key skf for a quadratic function f, which will allow us to decrypt ct to f(z), while the ct and skf will not leak any information about z. We will introduce one concrete design. The aim of this thesis will be the preparation of necessary preliminaries, which will allow us to describe the design, and to verify correctness of the algorithms. We will describe Arithmetic Branching Programs. Such objects will help us represent function f. Furthermore, we will introduce Garbling and Partial Garbling schemes. Those will allow us to "randomize"a part of the algorithm. We will also specify an encryption algorithm for linear transformation and use it to describe the main encryption algorithm for quadratic functions. 1
|
|
| |
guest ::
RSS feed.