UMD Theses and Dissertations
Permanent URI for this collectionhttp://hdl.handle.net/1903/3
New submissions to the thesis/dissertation collections are added automatically as they are received from the Graduate School. Currently, the Graduate School deposits all theses and dissertations from a given semester after the official graduation date. This means that there may be up to a 4 month delay in the appearance of a given thesis/dissertation in DRUM.
More information is available at Theses and Dissertations at University of Maryland Libraries.
Browse
430 results
Search Results
Item Practical Cryptography for Blockchains: Secure Protocols with Minimal Trust(2024) Glaeser, Noemi; Katz, Jonathan; Malavolta, Giulio; Computer Science; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)In 2008, Satoshi Nakamoto introduced Bitcoin, the first digital currency without a trusted authority whose security is maintained by a decentralized blockchain. Since then, a plethora of decentralized applications have been proposed utilizing blockchains as a public bulletin board. This growing popularity has put pressure on the ecosystem to prioritize scalability at the expense of trustlessness and decentralization. This work explores the role cryptography has to play in the blockchain ecosystem to improve performance while maintaining minimal trust and strong security guarantees. I discuss a new paradigm for scalability, called naysayer proofs, which sits between optimistic and zero-knowledge approaches. Next, I cover two on-chain applications: First, I show how to improve the security of a class of coin mixing protocols by giving a formal security treatment of the construction paradigm and patching the security of an existing, insecure protocol. Second, I show how to construct practical on-chain protocols for a large class ofelections and auctions which simultaneously offer fairness and non-interactivity without relying on a trusted third party. Finally, I look to the edges of the blockchain and formalize new design requirements for the problem of backing up high-value but rarely-used secret keys, such as those used to secure the reserves of a cryptocurrency exchange, and develop a protocol which efficiently meets these new challenges. All of these works will be deployed in practice or have seen interest from practitioners. These examples show that advanced cryptography has the potential to meaningfully nudge the blockchain ecosystem towards increased security and reduced trust.Item HOPF ALGEBRA OF MULTIPLE POLYLOGARITHMS AND ASSOCIATED MIXED HODGE STRUCTURES(2024) Li, Haoran; Zickert, Christian K; Mathematics; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)This thesis constructs a variation of mixed Hodge structures based on multiple polylogarithms, and attempts to build candidate complexes for computing motivic cohomology. Firstly, we consider Hopf algebras with generators representing multiple polylogarithms. By quotienting products and functional relations, we get Lie coalgebras whose Chevalley-Eilenberg complexes are conjectured to compute rational and integral motivic cohomologies. We also associate one-forms to multiple polylogarithms, which exhibit combinatorial properties that are easy to work with. Next, we introduce a variation matrix which describes a variation of mixed Hodge structures encoded by multiple polylogarithms. Its corresponding connection form is composed of the one-forms associated to the multiple polylogarithms. Lastly, to ensure the well-definedness of the Hodge structures, we must compute the monodromies of multiple polylogarithms, for which we provide an explicit formula, extending the previous work done for multiple logarithms, a subfamily of multiple polylogarithms.Item Eventually Stable Quadratic Polynomials over Q(i)(2024) McDermott, Jermain; Washington, Lawrence C; Mathematics; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)Let $f$ be a polynomial or a rational function over a field $K$. Arithmetic dynamics studies the algebraic and number-theoretic properties of its iterates $f^n:=f \circ f \circ ... \circ f$.\\ A basic question is, if $f$ is a polynomial, are these iterates irreducible or not? We wish to know what can happen when considering iterates of a quadratic $f= x^2+r\in K[x]$. The most interesting case is when $r=\frac{1}{c}$, which we will focus on, and discuss criteria for irreducibility, i.e. \emph{stability} of all iterates. We also wish to prove that if 0 is not periodic under $f$, then the number of factors of $f^n$ is bounded by a constant independent of $n$, i.e. $f$ is \emph{eventually stable}. This thesis is an extension to $\Qi$ of the paper \cite{evstb}, which considered $f$ over $\mathbb{Q}$. This thesis involves a mixture of ideas from number theory and arithmetic geometry. We also show how eventual stability of iterates ties into the density of prime divisors of sequences.Item Langlands-Kottwitz Method on Moduli Spaces of Global Shtukas(2024) Song, Shin Eui; Haines, Thomas; Mathematics; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)We apply the approach of Scholze to compute the trace of Hecke operator twisted by some power of Frobenius on the cohomology of the moduli spaces of global shtukas in the case of bad reduction. We find a formula that involves orbital integrals and twisted orbital integrals which can be compared with the Arthur-Selberg trace formula. This extends the results of Ngo and Ngo Dac on counting points of moduli spaces of global shtukas over finite fields. The main problem lies in finding a suitable compactly supported locally constant function that will be plugged into the twisted orbital integrals. Following Scholze, we construct locally constant functions called the test functions by using deformation spaces of bounded local shtukas. Then we establish certain local-global compatibility to express the trace on the nearby cycle sheaves on the moduli space of global shtukas to the trace on the deformation spaces.Item Metastable Distributions for Semi-Markov Processes(2024) Mohammed Imtiyas, Ishfaaq Ahamed; Koralov, Leonid; Mathematics; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)In this work, we consider semi-Markov processes whose transition times and transitionprobabilities depend on a small parameter ε. Understanding the asymptotic behavior of such processes is needed in order to study the asymptotics of various randomly perturbed dynamical and stochastic systems. The long-time behavior of a semi-Markov process Xε t depends on how the point (1/ε, t(ε)) approaches infinity. We introduce the notion of complete asymptotic regularity (a certain asymptotic condition on transition probabilities and transition times), originally developed for parameter-dependent Markov chains, which ensures the existence of the metastable distribution for each initial point and a given time scale t(ε). The result may be viewed as a generalization of the ergodic theorem to the case of parameter-dependent semi-Markov processes.Item Polynomials with Equal Images over Number Fields(2024) Hirsh, Jordan; Washington, Lawrence C; Mathematics; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)Chapman and Ponomarenko [1] characterized when two polynomials f, g ∈ Q[x] have thesame image f(Z) = f(Z). We extend this result to rings of integers in number fields. In particular, if K is a finite extension of Q and O is the ring of algebraic integers in K, we characterize when polynomials f, g ∈ K[x] satisfy f(O) = g(O). As part of our proof, we give a variant of Hilbert’s irreducibility theorem.Item GOOD POSITION BRAIDS, TRANSVERSAL SLICES AND AFFINE SPRINGER FIBERS(2024) Duan, Chengze; Haines, Thomas TH; Mathematics; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)In the study of Iwahori-Hecke algebras, Geck and Pfeiffer introduced good elements inCoxeter groups. These elements played a crucial role in the work of He and Lusztig on generalizing Steinberg’s cross-sections and Steinberg slices. This work yields the transversal slices for basic unipotent conjugacy classes in a reductive group G. We improve this result by introducing some more general braid elements called good position braids. We use them to construct transversal slices for any unipotent conjugacy classes in G. On the other hand, these good position braids also correspond to affine Springer fibers via root valuation strata. The correspondence leads to a reformulation of the dimension formula of affine Springer fibers. We also expect these braid elements to help with a conjecture of Goresky, Kottwitz and MacPherson on the cohomology of affine Springer fibers.Item SYMMETRIC-KEY CRYPTOGRAPHY AND QUERY COMPLEXITY IN THE QUANTUM WORLD(2024) Bai, Chen; Katz, Jonathan; Alagic, Gorjan; Electrical Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)Quantum computers are likely to have a significant impact on cryptography. Many commonly used cryptosystems will be completely broken once large quantum computers are available. Since quantum computers can solve the factoring problem in polynomial time, the security of RSA would not hold against quantum computers. For symmetric-key cryptosystems, the primary quantum attack is key recovery via Grover search, which provides a quadratic speedup. One way to address this is to double the key length. However, recent results have shown that doubling the key length may not be sufficient in all cases. Therefore, it is crucial to understand the security of various symmetric-key constructions against quantum attackers. In this thesis, we give the first proof of post-quantum security for certain symmetric primitives. We begin with a fundamental block cipher, the Even-Mansour cipher, and the tweakable Even-Mansour construction. Our research shows that both are secure in a realistic quantum attack model. For example, we prove that 2^{n/3} quantum queries are necessary to break the Even-Mansour cipher. We also consider the practical applications that our work implies. Using our framework, we derive post-quantum security proofs for three concrete symmetric-key schemes: Elephant (an Authenticated Encryption (AE) finalist of NIST’s lightweight cryptography standardization effort), Chaskey (an ISO-standardized Message Authentication Code), and Minalpher (an AE second-round candidate of the CAESAR competition). In addition, we consider the two-sided permutation inversion problem in the quantum query model. In this problem, given an image y and quantum oracle access to a permutation P (and its inverse oracle), the goal is to find its pre-image x such that P(x)=y. We prove an optimal lower bound \Omega(\sqrt{2^n}) for this problem against an adaptive quantum adversary. Moreover, we apply our lower bound above to show that a natural encryption scheme constructed from random permutations is secure against quantum attacks.Item CYCLOTOMIC Z2-EXTENSION OF REAL QUADRATIC FIELDS WITH CYCLIC IWASAWA MODULE(2024) Avila Artavia, Josue David; Ramachandran, Niranjan; Mathematics; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)For a number field K and a prime p, let K∞ denote the cyclotomic Zp-extension of K, andAn denote the p-primary part of the class group of its n-th layer Kn. Greenberg conjectured that for a totally real field, the order of An becomes constant for sufficiently large n. Motivated by the work of Mouhib and Movahhedi, we focus on the case where p = 2 and K is a real quadratic field such that the Iwasawa module X∞ = lim←An is cyclic. They determined all such fields and proved that Greenberg’s conjecture holds for some cases. In this dissertation, we provide new examples of infinite families of real quadratic fields satisfying Greenberg’s conjecture which were not covered completely in the work of Mouhib and Movahhedi. To achieve this, we use the theory of binary quadratic forms and biquadratic extensions to determine a fundamental system of units and the class number of the first few layers of the cyclotomic Z2-extension. Additionally, in certain cases, we can determine the size of the module X∞ and the level of the cyclotomic tower where the size of An becomes constant.Item Motivic Homotopy Theory and Synthetic Spectra(2024) Dziedzic, Charles Richard; Ramachandran, Niranjan; Mathematics; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)Motivic homotopy studies the application of techniques from homotopy theory to algebraic geometry, using A1 as the analogue of the unit interval. Voevodsky found early success in using his constructions to prove Milnor’s conjecture and the Bloch-Kato conjecture. An interesting and deep theory arises when constructing the unstable and stable motivic categories, and it has developed into its own field of study. We begin with a survey of these constructions, detailing the equivalences between the different model used in the construction of H(S) and SH(S). Here, we draw connections between all the constructions one might encounter across the literature, and provide explicit statements on their equivalence. Stable homotopy theorists have also found utility in motivic homotopy, using the stable mo- tivic homotopy category SH to advance computations of the stable homotopy groups of spheres, such as in the work of Isaksen-Wang-Xu. Other work by Bachmann-Kong-Wang-Xu has made great progress in our understanding of motivic homotopy theory. Synthetic spectra are a construction of Pstragrowski which represent a ‘return to form’ ofsome sort, as they are constructed entirely in the ∞−category of spectra. However, they give rise to a natural bigrading and a strong connection to motivic homotopy; one of the main results is an equivalence of ∞−categories with cellular motivic spaces over C, SpCcell. We build up enough of the general theory to establish the connection with motivic homotopy and comment on recent applications.