Theses and Dissertations from UMD
Permanent URI for this communityhttp://hdl.handle.net/1903/2
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 give thesis/dissertation in DRUM
More information is available at Theses and Dissertations at University of Maryland Libraries.
Browse
6 results
Search Results
Item RESILIENT AND EFFICIENT CONSENSUS UNDER UNKNOWN NETWORK CONDITIONS(2023) Blum, Erica 3645 SE Woodstock, Portland, OR, 97202; Katz, Jonathan; Computer Science; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)Large-scale distributed services need to provide high throughput and low latency without sacrificing resilience. In particular, even if some servers crash or malfunction, the system as a whole should remain consistent. This challenge has been studied extensively in distributed computing and cryptography in the form of consensus algorithms. A consensus algorithm is an interactive protocol that allows honest (non-faulty) nodes to agree on a shared output in the presence of Byzantine (faulty) nodes, who may behave arbitrarily. Consensus algorithms have a long history in distributed computing, and are now receiving even more attention in the context of blockchain systems.Consensus has frequently been studied in the context of two contrasting network models. In the synchronous network model, any message sent by an honest party will be delivered within a fixed bound; this bound is known to all parties and may be used as a protocol parameter. In the asynchronous network model, messages may be delayed for arbitrary lengths of time. For certain consensus problems and settings, the optimal fault tolerance is higher in the synchronous model than the asynchronous model (all else being equal). For example, assuming a public key infrastructure (PKI), the fundamental problem of Byzantine agreement (BA) for n parties is feasible for t < n/2 faults in the synchronous model, compared to only t < n/3 in the asynchronous model. On the other hand, synchronous consensus protocols can become stuck or even lose consistency if delays exceed the fixed bound. In this dissertation, we consider a novel network-agnostic notion of security. Our central contribution is a suite of consensus protocols that achieve precisely defined security guarantees when run in either a synchronous or asynchronous network model, even when the parties are unaware of the network’s true status. In addition, we provide matching impossibility results characterizing the best-possible security guarantees for this setting. We conclude by exploring a natural extension to network-agnostic security, in which protocols must remain secure in a setting where the underlying network status is not only unknown, but may switch between synchrony and asynchrony during a single protocol execution.Item IMPROVING THE ROUND COMPLEXITY OF IDEAL-CIPHER CONSTRUCTIONS(2017) Thiruvengadam, Aishwarya; Katz, Jonathan; Computer Science; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)Block ciphers are an essential ingredient of modern cryptography. They are widely used as building blocks in many cryptographic constructions such as encryption schemes, hash functions etc. The security of block ciphers is not currently known to reduce to well-studied, easily formulated, computational problems. Nevertheless, modern block-cipher constructions are far from ad-hoc, and a strong theory for their design has been developed. Two classical paradigms for block cipher design are the Feistel network and the key-alternating cipher (which is encompassed by the popular substitution-permutation network). Both of these paradigms that are iterated structures that involve applications of random-looking functions/permutations over many rounds. An important area of research is to understand the provable security guarantees offered by these classical design paradigms for block cipher constructions. This can be done using a security notion called indifferentiability which formalizes what it means for a block cipher to be ideal. In particular, this notion allows us to assert the structural robustness of a block cipher design. In this thesis, we apply the indifferentiability notion to the two classical paradigms mentioned above and improve upon the previously known round complexity in both cases. Specifically, we make the following two contributions: (1) We show that a 10-round Feistel network behaves as an ideal block cipher when the keyed round functions are built using a random oracle. (2) We show that a 5-round key-alternating cipher (also known as the iterated Even-Mansour construction) with identical round keys behaves as an ideal block cipher when the round permutations are independent, public random permutations.Item A Group-Based Ring Oscillator Physical Unclonable Function(2012) Yin, Chi-En; Qu, Gang; Electrical Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)Silicon Physical Unclonable Function (PUF) is a physical structure of the chip which has functional characteristics that are hard to predict before fabrication but are expected to be unique after fabrication. This is caused by the random fabrication variations. The secret characteristics can only be extracted through physical measurement and will vanish immediately when the chip is powered down. PUF promises a securer means for cryptographic key generation and storage among many other security applications. However, there are still many practical challenges to cost effectively build secure and reliable PUF secrecy. This dissertation proposes new architectures for ring oscillator (RO) PUFs to answer these challenges. First, our temperature-aware cooperative (TAC) RO PUF can utilize certain ROs that were otherwise discarded due to their instability. Second, our novel group-based algorithm can generate secrecy higher than the theoretical upper bound of the conventional pairwise comparisons approach. Third, we build the first regression-based entropy distiller that can turn the PUF secrecy statistically random and robust, meeting the NIST standards. Fourth, we develop a unique Kendall syndrome coding (KSC) that makes the PUF secrecy error resilient against potential environmental fluctuations. Each of these methods can improve the hardware efficiency of the RO PUF implementation by 1.5X to 8X while improving the security and reliability of the PUF secrecy.Item On Fairness in Secure Computation(2010) Gordon, Samuel Dov; Katz, Jonathan; Computer Science; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)Secure computation is a fundamental problem in modern cryptography in which multiple parties join to compute a function of their private inputs without revealing anything beyond the output of the function. A series of very strong results in the 1980's demonstrated that any polynomial-time function can be computed while guaranteeing essentially every desired security property. The only exception is the fairness property, which states that no player should receive their output from the computation unless all players receive their output. While it was shown that fairness can be achieved whenever a majority of players are honest, it was also shown that fairness is impossible to achieve in general when half or more of the players are dishonest. Indeed, it was proven that even boolean XOR cannot be computed fairly by two parties The fairness property is both natural and important, and as such it was one of the first questions addressed in modern cryptography (in the context of signature exchange). One contribution of this thesis is to survey the many approaches that have been used to guarantee different notions of partial fairness. We then revisit the topic of fairness within a modern security framework for secure computation. We demonstrate that, despite the strong impossibility result mentioned above, certain interesting functions can be computed fairly, even when half (or more) of the parties are malicious. We also provide a new notion of partial fairness, demonstrate feasibility of achieving this notion for a large class of functions, and show impossibility for certain functions outside this class. We consider fairness in the presence of rational adversaries, and, finally, we further study the difficulty of achieving fairness by exploring how much external help is necessary for enabling fair secure computation.Item Expressiveness of Definitions and Efficiency of Constructions in Computational Cryptography(2007-08-05) Horvitz, David Omer; Gligor, Virgil D; Katz, Jonathan; Computer Science; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)The computational treatment of cryptography, and indeed any scientific treatment of a problem, is marked by its definitional side and by it constructive side. Results in this thesis better our understanding of both: on one side, they characterize the extent to which computational definitions capture the security of the basic task of symmetric encryption; on the other, they provide explicit bounds on the efficiency of commitment and secure two-party computation constructions. Specifically: - We relate the formal and computational treatments of symmetric encryption, obtaining a precise characterization of computational schemes whose computational semantics imply their formal semantics. We prove that this characterization is strictly weaker than previously-identified notions, and show how it may be realized in a simpler, more efficient manner. - We provide lower-bounds on the number of times a one-way permutation needs to be invoked (as a "black-box") in order to construct statistically-binding commitments. Our bounds are tight for the case of perfectly-binding schemes. - We show that the secure computation of any two-party functionality can be performed in an optimal two rounds of communication even in a setting that accounts for concurrent execution with other protocols (i.e., the Universal Composability framework). Here, we rely on the assumption that parties have access to a common reference string; some sort of setup is known to be necessary.Item Lookup Protocols and Techniques for Anonymity(2006-08-18) Morselli, Ruggero; Katz, Jonathan; Bhattacharjee, Bobby; Computer Science; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)This dissertation covers two topics of interest for network applications: lookup protocols, a basic building block for distributed systems, and ring signatures, a powerful primitive for anonymous communication. In the first part of this work, we review lookup protocols, distributed algorithms that allow users to publish a document as well as to look up a published document that matches a given name. Our first major contribution is to design Local Minima Search (LMS), a new efficient lookup protocol for a model in which a node is physically connected to a few other nodes and may only communicate directly with them. Our second major contribution is the formulation of a new model in which we allow an arbitrary number of misbehaving nodes, but we assume a restriction on their network addresses. We then design a new lookup protocol for this setting. In the second part of this dissertation, we present our work on ring signatures, a variant of digital signatures, which enables a user to sign a message so that a set of possible signers is identified, without revealing which member of that set actually generated the signature. Our first contribution on this topic is new definitions of security which address attacks not taken into account by previous work. As our second contribution, we design the first provably secure ring signature schemes in the standard model.