A. James Clark School of Engineering
Permanent URI for this communityhttp://hdl.handle.net/1903/1654
The collections in this community comprise faculty research works, as well as graduate theses and dissertations.
Browse
4 results
Search Results
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 Advances in Concrete Cryptanalysis of Lattice Problems and Interactive Signature Schemes(2024) Kippen, Hunter Michael; Dachman-Soled, Dana; Electrical Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)Advanced cryptography that goes beyond what is currently deployed to service our basic internet infrastructure is continuing to see widespread adoption. The enhanced functionality achieved by these schemes frequently yields an increase in complexity. Solely considering the asymptotic security of the underlying computational assumptions is often insufficient to realize practical and secure instantiations.In these cases, determining the risk of any particular deployment involves analyzing the concrete security (the exact length of time it would take to break the encryption) as well as quantifying how concrete security can degrade over time due to any exploitable information leakage. In this dissertation, we examine two such cryptographic primitives where assessing concrete security is paramount. First, we consider the cryptanalysis of lattice problems (used as the basis for current standard quantum resistant cryptosystems). We develop a novel side-channel attack on the FrodoKEM key encapsulation mechanism as submitted to the NIST Post Quantum Cryptography (PQC) standardization process. Our attack involves poisoning the FrodoKEM Key Generation (KeyGen) process using a security exploit in DRAM known as “Rowhammer”. Additionally, we revisit the security of the lattice problem known as Learning with Errors (LWE) in the presence of information leakage. We further enhance the robustness of prior methodology by viewing side information from a geometric perspective. Our approach provides the rigorous promise that, as hints are integrated, the correct solution is a (unique) lattice point contained in an ellipsoidal search space. Second, we study the concrete security of interactive signature schemes (used as part of many Privacy Enhancing Technologies). To this end, we complete a new analysis of the performance of Wagner’s k-list algorithm [CRYPTO ‘02], which has found significant utility in computing forgeries on several interactive signature schemes that implicitly rely on the hardness of the ROS problem formulated by Schnorr [ICICS ‘01].Item Extending The Applicability of Non-Malleable Codes(2019) Kulkarni, Mukul; Dachman-Soled, Dana; Electrical Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)Modern cryptographic systems provide provable security guarantees as long as secret keys of the system remain confidential. However, if adversary learns some bits of information about the secret keys the security of the system can be breached. Side-channel attacks (like power analysis, timing analysis etc.) are one of the most effective tools employed by the adversaries to learn information pertaining to cryptographic secret keys. An adversary can also tamper with secret keys (say flip some bits) and observe the modified behavior of the cryptosystem, thereby leaking information about the secret keys. Dziembowski et al. (JACM 2018) defined the notion of non-malleable codes, a tool to protect memory against tampering. Non-malleable codes ensure that, when a codeword (generated by encoding an underlying message) is modified by some tampering function in a given tampering class, if the decoding of tampered codeword is incorrect then the decoded message is independent of the original message. In this dissertation, we focus on improving different aspects of non-malleable codes. Specifically, (1) we extend the class of tampering functions and present explicit constructions as well as general frameworks for constructing non-malleable codes. While most prior work considered ``compartmentalized" tampering functions, which modify parts of the codeword independently, we consider classes of tampering functions which can tamper with the entire codeword but are restricted in computational complexity. The tampering classes studied in this work include complexity classes $\mathsf{NC}^0$, and $\mathsf{AC}^0$. Also, earlier works focused on constructing non-malleable codes from scratch for different tampering classes, in this work we present a general framework for constructing non-malleable codes based on average-case hard problems for specific tampering families, and we instantiate our framework for various tampering classes including $\mathsf{AC}^0$. (2) The locality of code is the number of codeword blocks required to be accessed in order to decode/update a single block in the underlying message. We improve efficiency and usability by studying the optimal locality of non-malleable codes. We show that locally decodable and updatable non-malleable codes cannot have constant locality. We also give a matching upper bound that improves the locality of previous constructions. (3) We investigate a stronger variant of non-malleable codes called continuous non-malleable codes, which are known to be impossible to construct without computational assumptions. We show that setup assumptions such as common reference string (CRS) are also necessary to construct this stronger primitive. We present construction of continuous non-malleable codes in CRS model from weaker computational assumptions than assumptions used in prior work.Item Common Randomness Principles of Secrecy(2013) Tyagi, Himanshu; Narayan, Prakash; Electrical Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)This dissertation concerns the secure processing of distributed data by multi- ple terminals, using interactive public communication among themselves, in order to accomplish a given computational task. In the setting of a probabilistic multitermi- nal source model in which several terminals observe correlated random signals, we analyze secure distributed data processing protocols that harness the correlation in the data. The specific tasks considered are: computing functions of the data under secrecy requirements; generating secretly shared bits with minimal rate of public communication; and securely sharing bits in presence of a querying eavesdropper. In studying these various secure distributed processing tasks, we adopt a unified approach that entails examining the form of underlying common randomness (CR) that is generated at the terminals during distributed processing. We make the case that the exact form of established CR is linked inherently to the data processing task at hand, and its characterization can lead to a structural understanding of the associated algorithms. An identification of the underlying CR and its decomposi- tion into independent components, each with a different operational significance, is a recurring fundamental theme at the heart of all the proofs in this dissertation. In addition to leading to new theoretical insights, it brings out equivalences between seemingly unrelated problems. Another distinguishing feature of this work is that it considers interactive communication protocols. In fact, understanding the structure of such interactive communication is a key step in proving our results. We make the following contributions. First, we propose a new information theoretic formulation to study secure distributed computing using public communi- cation. The parties observing distributed data are trusted but an eavesdropper has access to the public communication network. We examine distributed communica- tion protocols that allow the trusted parties to accomplish their required computa- tion tasks while giving away negligible information about a specified portion of the data to an eavesdropper with access to the communication. Our theoretical results provide necessary and sufficient conditions that characterize the feasibility of vari- ous secure computing tasks; in many cases of practical importance, these conditions take a simple form and can be verified easily. When secure computing is feasible, we propose new algorithms in special cases. Next, we revisit the problem of generating shared secret keys (SKs). We investigate minimum communication requirements for generating information theo- retically secure SKs of maximum rates from correlated observations using interactive public communication. In particular, our approach allows us to examine the role of interaction in such communication. On the one hand, we find that interaction is not needed when the observed correlated bits are symmetrically correlated and therefore, in this case, simple noninteractive protocols are the most efficient means of generating optimum rate SKs. On the other hand, we illustrate that interactive pro- tocols can require a strictly lower rate of overall communication than noninteractive protocols. Finally, we consider the task of ensuring security against an eavesdropper who makes queries about a portion of the distributed data that the terminals share by communicating over a public network. We introduce an alternative notion of secrecy which requires rendering the task of a querying eavesdropper as onerous as possible. Our main contribution in this part is the development of a new technique for proving converse results for secrecy problems involving CR with interactive communication, which is employed then to obtain an upper bound for the maximum number of queries that can be inflicted on the eavesdropper for any CR and corresponding communication. Surprisingly, there is an equivalence between this notion of secrecy and that of information theoretic security, which leads to new theoretical results for SK generation; for instance, we prove a strong converse for the SK capacity. We conclude by hypothesizing the basic principles of secrecy generation that emerge from the results developed in this dissertation.