|
|
Security of Trapdoor Permutations under Preimage Leakage
Sedláček, Petr ; Hubáček, Pavel (advisor) ; Göloglu, Faruk (referee)
This thesis explores preimage leakage-resilient trapdoor permutations (PLR-TDPs) and their applications in proofs of storage replication and incompressible encodings. The thesis consists of three chapters covering the trapdoor permutations, formal definition of PLR-TDPs, and analysis of security properties of PLR-TDPs. The first chapter provides an overview of trapdoor permutations (TDPs), their def- initions, and applications in proofs of storage replication. Our results are presented in the second and third chapters. The second chapter formally defines PLR-TDPs and demonstrates their use by constructing a simple incompressible encoding in the random oracle model. The third chapter focuses on the existence of PLR-TDPs. It demonstrates the strong preimage leakage-resilience of fully random TDPs in an idealized model. We are the first to provide a partial formal justification for the conjecture of the preimage leakage-resilience of practical TDPs, such as RSA or Rabin permutations.
|
|
|
Analysis of blockchain used for Bitcoin
Surma, David ; Hartman, David (advisor) ; Hubáček, Pavel (referee)
This thesis deals with the analysis of the blockchain used for Bitcoin. Blockchain is a distributed database of all transactions made with this cryptocurrency. Its public availability represents the possibility of examining the transfer of funds between all users. However, they appear in transactions under anonymous addresses, the number of which is practically unlimited. The main goal of our work is to find a clustering of addresses corresponding to their belonging to real users. In this work, we propose new heuristics that can be used in clustering. The main benefit is a method that uses the properties of transactions created very quickly one after the other. Furthermore, we analyze the problem of the formation of a supercluster containing a disproportionately large number of addresses and propose a way in which the cluster can be appropriately partitioned. 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.
|
|
|
On the Complexity of Search Problems with a Unique Solution
Králová, Veronika ; Hubáček, Pavel (advisor) ; Brzuska, Christopher (referee) ; Bitansky, Nir (referee)
Meggido and Papadimitriou [Theor. Comput. Sci., 1991] introduced the class TFNP of search problems for which a solution always exists and is polynomially verifiable. In this thesis, we study the possibility of reducing different problems into problems in TFNP. The property which is in common for problems, for which we study the reducibility to TFNP, is that all instances of these problems have a unique solution (if there is any solution present). In the first part of this thesis, we study a problem called ARRIVAL, which was intro- duced by Dohrau, Gärtner, Kohler, Matoušek and Welzl [A Journey Through Discrete Mathemathics: A Tribute to Jiří Matoušek, 2017]. ARRIVAL is the following decisional problem: Given a graph in which a train is moving according to prescribed rules does the train arrive to a given vertex? We first improve the result of Dohrau et al. who showed that the problem is in NP ∩ coNP. We show that there exists a unique certificate for being in the language and, thus, prove that it lies in UP ∩ coUP. We also study the search version of the ARRIVAL problem, which asks for the tran- script of number of traversals for each edge. It was known that the search version lies in PLS, which was proven by Karthik C. S. [Inf. Process. Lett., 2017]. We improve this result by showing a reduction from...
|
|
|
Verifiable Delay Functions z Lucasových posloupností
Krňák, Tomáš ; Hubáček, Pavel (advisor) ; Příhoda, Pavel (referee)
Lucas sequences are constant-recursive integer sequences with a long history of appli- cations in cryptography, both in the design of cryptographic schemes and cryptanalysis. In this work, we study the sequential hardness of computing Lucas sequences over an RSA modulus. First, we show that modular Lucas sequences are at least as sequentially hard as the classical delay function given by iterated modular squaring proposed by Rivest, Shamir, and Wagner in the context of time-lock puzzles. Moreover, there is no obvious reduction in the other direction, which suggests that the assumption of sequential hardness of modular Lucas sequences is strictly weaker than that of iterated modular squaring. In other words, the sequential hardness of modular Lucas sequences might hold even in the case of an algorithmic improvement violating the sequential hardness of iterated modular squaring. Second, we demonstrate the feasibility of constructing practically efficient verifiable delay functions based on the sequential hardness of modular Lucas sequences. Our con- struction builds on the work of Pietrzak (ITCS 2019) by leveraging the intrinsic connec- tion between the problem of computing modular Lucas sequences and exponentiation in an appropriate extension field. 1
|
|
| |
|
|
Gröbnerovy báze v kryptografii
Hubáček, Pavel ; Stanovský, David (advisor) ; Šťovíček, Jan (referee)
The thesis focuses on the use of GrÄobner bases in cryptography and especially on applications in cryptanalysis of block ciphers. Some elementary concepts from the theory of GrÄobner bases are introduced together with Buchberger's algorithm, a method for constructing such bases. The principle of solving of poly nomial systems using suitable GrÄobner bases is explained. This is followed by pre sentation of modern algorithms that improve the Buchberger's algorithm. In the last part of the thesis present results achieved by GrÄobner bases are summarised and the notion of algebraic cryptanalysis is introduced. In algebraic cryptanalysis we transform breaking of given cryptosystem into a problem of solving polynomial equations over some nite eld. Examples of polynomial descriptions of block ciphers are provided together with some experimental result on arising polynomial systems.
|
|
|
Effectivity and Limitations of Homomorphic Secret Sharing Schemes
Jančová, Ľubica ; Hubáček, Pavel (advisor) ; Holub, Štěpán (referee)
This thesis focuses on constructions of Homomorphic Secret Sharing (HSS) based on assumptions not known to imply fully homomorphic encryption. The efficiency of these constructions depends on the complexity of the Distributed Discrete Logarithm (DDLog) problem in the corresponding groups. We describe this problem in detail, focusing on the possibility of leveraging preprocessing in prime order groups, and deriving upper bounds on the success probability for the DDLog problem with preprocessing in the generic group model. Further, we present a new HSS construction. We base our construction on the Joye-Libert encryption scheme which we adapt to support an efficient distributed discrete logarithm protocol. Our modified Joye-Libert scheme requires a new set of security assumptions, which we introduce, proving the IND-CPA security of our scheme given these assumptions. 1
|
|
|
Quantum programming languages
Čížková, Josefína ; Mareš, Martin (advisor) ; Hubáček, Pavel (referee)
Quantum programming languages Abstract We describe basic principles and properties of a quantum system and their use for Shor's algorithm. This algorithm promises to factorize integers in better time complexity on a quantum computer simulator. We also describe Shor's algorithm in the programming language Q#, which allows us to simulate a quantum algorithm on a classical computer. Finally, two other quantum programming languages are introduced, Qiskit and QCL, again illustrated by factorization.
|
|
|
Limitations of Incompressible Encodings
Sedláček, Petr ; Hubáček, Pavel (advisor) ; Mareš, Martin (referee)
This thesis studies the limitations of incompressible encodings with information- theoretic security. We demonstrate a flaw in the existing proof of the impossibility of constructing incompressible encodings information-theoretically. Our main contribu- tion is a full proof of impossibility of existence of non-trivial information-theoretically secure incompressible encoding schemes. In the first part of the thesis, we introduce the basics of incompressible encodings and provide the necessary definitions. Next, we present the flaws in the existing argument and provide explicit counterexamples to them. Throughout the rest of the thesis, we gradually construct a complete proof. We start by showing the impossibility under a few additional restrictions on the correctness and structure of the schemes that we subsequently remove one by one. Finally, we present an adversary able to break any non-trivial incompressible encoding scheme. 1
|
guest ::
RSS feed.