|
|
Compact modules over nonsingular rings
Kálnai, Peter ; Žemlička, Jan (advisor) ; Breaz, Simion (referee) ; Příhoda, Pavel (referee)
This doctoral thesis provides several new results in which we leverage the inner structure of non-singular rings, in particular of self-injective von Neumann regular rings. First, we describe categorical and set-theoretical conditions under which all products of compact objects remain compact, where the notion of compactness is relativized with respect to a fixed subclass of objects. A special instance when such closure property holds are the classic module categories over rings of our interest. Moreover, we show that a potential counterexample for Köthe's Conjecture might be in the form of a countable local subring of a suitable simple self-injective von Neumann regular ring. 1
|
|
|
Generalized integral property
Hrúzová, Jana ; Žemlička, Jan (advisor) ; Příhoda, Pavel (referee)
This thesis is based on an article C. Boura and A. Canteaut, Another View of the Division Property, which is focused on division property of sets from Fn 2 . In this thesis we introduce important definitions and propositions about boolean function, polynomials and Reed-Muller codes at the beginning. Then we define parity set of a set from Fn 2 , which helps us to simplify the division property. We also show how sets, which satisfy division property of certain order, look like. From that we could follow how the division property propagate through the substitution-permutation network. 1
|
|
|
Cryptoanalysis of a Post-quantum Cryptography Algorithm
Štumpf, Daniel ; Hojsík, Michal (advisor) ; Příhoda, Pavel (referee)
National Institute of Standards and Technology (NIST) is currently running a stan- dardization process for a post-quantum cryptography primitives. Depending on the al- gorithms building blocks these primitives can be divided into five categories. In the first part of this thesis we described all five categories and compared their characteristics. The most important aspect of the schemes for NIST is security against both classical and quantum adversaries. We chose one of the five categories (namely, we picked lattice- based cryptosystems) for further cryptanalysis. As we think that the security analysis of some of the second round candidates in the NIST standardization project is not suffi- ciently well described in their specification documents and some known attacks are not considered at all, we provide a unified security analysis of these schemes. We described two currently known attacks (primal and dual attacks) against lattice-based schemes, estimated cost of these attacks against the lattice-based candidates in the second round of the NIST standardization project and compared these values with the security claimed by these candidates. In most cases our estimations matches those published in the speci- fication documents and therefore we conclude that the security estimates claimed by the candidates are...
|
|
|
Short invertible elements in cyclotomic rings
Kroutil, Jaroslav ; Žemlička, Jan (advisor) ; Příhoda, Pavel (referee)
This bachelor's thesis is based on an article about the criterion for invertibility of elements in special- chosen cyclotomic rings. In this thesis, we start with defining important terms and statements from algebra that we need. Then we will deal with the existence of infinitely many prime numbers which satisfy conditions that are used for irreducible decomposition of cyclotomic polynomials. Based on this polynomials we define cyclotomic rings and at the end of this thesis we prove invertibility of elements from this rings depending on the size of their norm.
|
|
|
Cubic and biquadratic reciprocity
Staško, Samuel ; Příhoda, Pavel (advisor) ; Krásenský, Jakub (referee)
The main motivation for studying cubic and biquadratic reciprocity is to de- cide, whether the congruences x3 ≡ a (p) or x4 ≡ a (p), where a ∈ Z, p prime, have any integer solution. The core of this thesis will be to prove the laws of cubic and biquadratic reciprocity through gradually built theory in the rings of Eisen- stein and Gaussian integers. In addition, for both of these theorems, we will take a closer look at the special cases, in which they cannot be used. This will lead us to the derivation of the supplement to the law of cubic (or biquadratic) re- ciprocity. Finally, we will show how these results can be applied to the problem of solvability of mentioned congruences. 1
|
|
|
Algorithms for factorization of integers of particular form
Lorenc, Filip ; Příhoda, Pavel (advisor) ; Růžička, Pavel (referee)
This bachelor thesis deals with three factorization algorithms - Pollard p-1 method, Williams p+1 method and elliptic curve method ECM. This work aims to describe these algorithms theoretically and then compare them on real inputs. For each algorithm we describe its basic and extended version and then we derive their time complexity. In the first chapter we define B-powersmooth and B-smooth number and we state their approximation. The second, third and fourth chapter is about description of algorithms and in the last chapter we compare their effectiveness and performance. A part of the work contains basic theory about elliptic curves, which is necessary in ECM. There is also included a program containing all these algorithms.
|
|
|
LWE and provably secure key exchange schemes
Václavek, Jan ; Příhoda, Pavel (advisor) ; Žemlička, Jan (referee)
The threat of large-scale quantum computers motivates cryptographers to base cryptosystems on problems believed to be resistant against quantum computers. In this thesis, we focus on the LWE problem which is believed to be resistant against quantum computers. First, we describe lattices which are closely related to the LWE problem. We introduce basic notions, describe lattice problems and solve exercises related to the covering radius of lattice. After that, we introduce the LWE problem and its variants. We prove reductions from two lattice problems to certain variant of the LWE problem. We define the notion of statistical distance and prove some lemmata about it which we need within reductions. Moreover, we show concrete application of the LWE problem. We describe a scheme for key exchange and briefly prove its security under the assumption that the LWE problem is hard. 1
|
|
|
Proving security of hash functions
Zpěváček, Marek ; Příhoda, Pavel (advisor) ; Žemlička, Jan (referee)
This thesis focuses on proof of reduction from approximate SBP to SIS. The proof was already accomplished by Mikl'os Ajtai in 1996 in his groun- dbreaking work, however his proof lacks level of detail. The reduction is worst-case to average-case and no reduction of this type was known prior to the Ajtai's one. That is the reason why we found appropriate to return to the proof and provide it in more detailed form. Furthermore, the complexity of basic lattice problems is summarized. Based on these complexities and proven reduction, it is possible to define collision-resistant hash functions. This work is also briefly focused on such functions. 1
|
|
|
Attacks on RSA based on lattice reduction
Vaněček, Jaromír ; Příhoda, Pavel (advisor) ; Jedlička, Přemysl (referee)
This thesis aims to describe in detail the Coppersmith's algorithm for fin- ding small solutions to polynomial congruences which is based on lattice basis reduction. This algorithm is a cornerstone of several attacks on the most wi- despread asymmetric cryptosystem RSA, therefore, next aim of the thesis is a description of selected attacks. As an important and current example, we can mention so-called ROCA attack which factorizes RSA modulus whenever the pri- mes are specifically crafted. At the end of the thesis, we implement both the Coppersmith's algorithm and the ROCA and several measurements and experi- ments are done. From the resulting data, one can deduce how the running time of the algorithm is affected by different parameters or what are the ideal values for these parameters in various situations. 1
|
|
|
Application of Multilinear Forms in Cryptography
Rabas, Tomáš ; Žemlička, Jan (advisor) ; Příhoda, Pavel (referee)
We describe the theoretical concept of multilinear maps and its practical real- ization using new construction - Garg-Gentry-Halevi (GGH) Graded Encoding Scheme. In this construction, which is based on ideal lattices, we justify its assumptions and clarify some algebraic inaccuracies, especially the inversibility of the randomly chosen z from commutative ring Rq. We also present applica- tion of theoretical concept and its practical realization GGH to one-round N-way Diffie-Hellman key exchange.
|
guest ::
