|
|
On impossibility of elementary integration
Zelina, Michael ; Pražák, Dalibor (advisor) ; Kazda, Alexandr (referee)
This work is devoted to studying of problem of (non)existence an elementary pri- mitive function of a given function. In the first place, we introduce the structure of a differential field and then we find a suitable way of formalizing the concept of the elementary function. This tools opens up the possibility to formulate and prove the crucial theorem which says what form an elemental primitive function must necessarily have if it exists. Then we use it to find the conditions for the existence of an ele- mentary integrals of two functions in a special but still quite general form. By using these conditions, we will show the nonelementarity of a number of more or less known integrals. 3
|
|
|
Key dependent message security
Hostáková, Kristina ; Hojsík, Michal (advisor) ; Kazda, Alexandr (referee)
In this work, we deal with cryptosystems which are provably secure even if we encrypt a key-dependent message. These cryptosystems are called KDM-secure. First, we define KDM-security and discuss its relationship with other kinds of security, especially IND-CPA-security. Thereafter, we construct the public- key and the symmetric-key encryption scheme of Applebaum et al. (CRYPTO 2009) and we prove KDM-security of these cryprosystems with respect to the set of affine functions. The security of our cryptosystems is based on the LWE problem and the LPN problem as its special case. We study these problems and their variants. Moreover, we give a brief introduction to lattices and hard lattice problems because there exist reductions from hard lattice problems to LWE. 1
|
|
|
Homomorphic encryption schemes
Titěrová, Anežka ; Kazda, Alexandr (advisor) ; Hojsík, Michal (referee)
Title: Homomorphic encryption schemes Author: Anežka Titěrová Department: Department of Algebra Supervisor: RNDr. Alexandr Kazda, Department of Algebra Abstract: Rivest et al. posed in 1978 the cryptographic problem how to correctly compute arbitrary functions over encrypted data without direct decrypting. This problem is solved by using of a fully homomorphic encryp- tion scheme, which was discovered and first described by Craig Gentry in 2009. This work gives a summary of contemporary knowledge in this field. The attention will be restricted to a general overview how to construct the fully homomorphic encryption scheme with respect to the information security. The results will be applied in an implementation of a somewhat homomorphic encryption scheme as a computer program. Fully homomorphic encryption schemes have abundant applications, especi- ally in secure cloud computing. Nevertheless, the greatest challenge for scien- tists is finding out more efficient algorithm because existing implementations are not as effective and fast as required for everyday use. Keywords: homomorphic encryption, fully homomorphic encryption scheme, lattice cryptography, logic circuit
|
|
|
Constraint Satisfaction Problem and Universal Algebra
Kazda, Alexandr ; Barto, Libor (advisor) ; Růžička, Pavel (referee) ; Valeriote, Matt (referee)
The thesis consists of a collection of my contributions to universal algebra. Motivated by the Constraint Satisfaction Problem (CSP), we study the algebras of polymorphisms of relational structures. We begin by showing by an algebraic argument (and a bit of calculus) that random relational structures' CSP is almost always NP-complete. We then study digraphs with a Maltsev polymorphism, and conclude that such digraphs must also have a majority polymorphism. Next, we show how to use absorption tech- niques to prove that congruence modular reflexive digraphs must have an NU operation. We close our work by giving an algebraic proof of a result (first obtained by graph theorists) that 3-conservative relational structures with only unary and binary relations either define NP-complete CSP, or CSP for them can be solved by the local consistency algorithm. 1
|
|
|
Model building using CSP
Peterová, Alena ; Stanovský, David (advisor) ; Kazda, Alexandr (referee)
In the present work, we study algorithms for building finite models of sets of first-order axioms with the aim of proposing and implementing a new method, based on translation onto constraint satisfaction problem (CSP). In the theoretical part, we describe the standard MACE-style method, based on translating problems onto SAT, and advanced techniques that improve the effectiveness of this method: clause splitting, term definitions and static symmetry reduction. Next, we propose an alternative method, which translates problems onto CSP in a similar way. In addition, we have newly proposed a static symmetry reduction technique for binary functions. Next, we describe an implementation of the alternative method using a CSP-modelling language MiniZinc and a CSP-solver Gecode. Finally, we compare performance of our model finder against state-of-the-art representatives of standard methods, systems Paradox and Mace4.
|
|
| |
|
|
Symbolické reprezentace kompaktních prostorů
Kazda, Alexandr
Title: Symbolic representations of compact spaces Author: Alexandr Kazda Department: Department of Algebra Supervisor: Prof. RNDr. Petr Kůrka, CSc. Supervisor's e-mail address: kurka@cts.cuni.cz Abstract: The thesis concerns itself with Möbius number systems. These systems represent points using sequences of Möbius transformations. We are mainly inter- ested in representing the unit circle (which is equivalent to representing R ∪ {∞}). The main aim of the thesis is to improve already known tools for proving that a given subshift-iterative system pair is in fact a Möbius number system. We also study the existence problem: How to describe iterative systems resp. subshifts for which there exists a subshift resp. iterative system such that the resulting pair forms a Möbius number system. While we were unable to provide a complete answer to this question, we present both positive and negative partial results. As Möbius number systems are also subshifts, we can ask when a given Möbius number system is sofic. We give this problem a short treatment at the end of our thesis. Keywords: Möbius transformation, numeral system, subshift
|
|
| |
|
| |
|
| |
guest ::
RSS feed.