|
|
Edwards curves and elliptic function fields
Beran, Adam ; Drápal, Aleš (advisor) ; Žemlička, Jan (referee)
In this thesis, we study twisted Edwards curves using the theory of algebraic function fields. After summarizing the basic theory, we focus on the structure of the function field for curves that are given by an equation of the form x2 2 = f(x1), where f is a monic polynomial of degree four. We show that twisted Edwards curves correspond to a special case when f(x1) = g(x2 1), where g is a quadratic polynomial with two distinct nonzero roots. We describe the basic properties of twisted Edwards curves, with special attention given to possible places at infinity. Next, we derive formulas for the point addition, which is achieved by using the relation between points on the curve, places of degree one and elements of the Picard group. Furthermore, we summarize how the point addition can be interpreted geometrically, and outline several alternative coordinate systems based on projective coordinates. Finally, we present two examples of twisted Edwards curves that are nowadays being used in cryptographic applications. 1
|
|
|
Secure multi-party computation modulo p^k
Struk, Martin ; Žemlička, Jan (advisor) ; Příhoda, Pavel (referee)
The thesis deals with a subfield of cryptography called secure multi-party computation which is a technique that allows multiple parties to work together to compute a single function while preserving the privacy of it's inputs. More specifically, the thesis deals with secure multi-party computation over the ring of integers modulo pk . The thesis begins with an introduction of the general principle of secure multi-party protocols, followed by the construction of the necessary theoretical groundwork over commutative rings, wich will be needed to describe and understand a specific protocol in the last section of the thesis. 1
|
|
|
MDS matrices
Vlášková, Šárka ; Žemlička, Jan (advisor) ; Patáková, Zuzana (referee)
MDS matrices are widely used in coding theory and cryptography (e.g. in diffusion layers of block ciphers or hash functions), but the construction of MDS matrices is not at all trivial, especially when we require some other suitable properties (involution, efficiency of implementation). That is why we will deal with the construction of MDS matrices (with other properties) in this thesis. We will show a construction of MDS matrices based on Cauchy matrices and on Vandermonde matrices. Then we will present an algorithm for testing whether a given matrix is MDS. And finally, we will show a construction of MDS matrices based on Companion matrices, which is very convenient for lightweight cryptography. 1
|
|
|
Classification of finite dimensional modules over string algebras
Macháč, Ondřej ; Šťovíček, Jan (advisor) ; Žemlička, Jan (referee)
In this thesis we classify indecomposable finite dimensional modules over string alge- bras. In the introductory part we define string algebras and string modules and band modules. In the third chapter we prove the classification theorem and define functors used. In the fourth and fifth chapter we verify assumptions on the functors regarding string modules or band modules, respectively. In the last chapter we show that these functors are sufficient and we finish proofs of all the remaining assumptions of the main theorem. At last we show examples of classification. 1
|
|
|
Kan extensions and adjoint functors
Otrubů, Mavis ; Šaroch, Jan (advisor) ; Žemlička, Jan (referee)
This thesis is devoted to Kan extensions. First, we provide needed definitions and prove a theorem which gives us an existence condition for a Kan extensions. The proof of this theorem also contains a guide to constructing Kan extensions. The main goal is to present a result which puts Kan extensions and adjoint functors in relation. We also connect this theorem to global Kan extensions. We apply these abstract results in the last chapter, where we formulate and solve a particular problem concerning adjoint functors between the categories of G-sets. 1
|
|
|
AKS primality test and its variants
Ondo, Tomáš ; Žemlička, Jan (advisor) ; Pavlů, Jiří (referee)
In this thesis, the first polynomial deterministic primality test named AKS algori- thm is described. The thesis is focused on the time complexity of the algorithm. Several drawbacks which make this algorithm unsuitable for generating large prime numbers are described. Improvements derived from empirical data are summed up. These improve- ments are not proven, so they do not yield a deterministic test. The thesis continues with a comparison of the runtime of concrete implementations. The thesis also contains a variant of the AKS test, the Bernstein variant, which has a better time complexity. The execution of these algorithms is shown in examples. 1
|
|
|
Art gallery problem
Smolíková, Natálie ; Patáková, Zuzana (advisor) ; Žemlička, Jan (referee)
In this thesis, we study a classical problem in computational geometry, the Art Gallery Problem. The Art Gallery Problem originates from the question of what is the minimum number of guards required to see the entire gallery. The main goal of this paper is to provide proofs that ⌊n 3 ⌋ guards are sufficient for a simple polygon, and that ⌊n 4 ⌋ guards are sufficient for an orthogonal polygon. Our proof of the orthogonal version is a correction of Jorge Urrutia's proof. We also study the optimality of the results and the placement of guards. 1
|
|
|
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
|
|
|
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
|
guest ::
RSS feed.