Search

We examine new ways in which coding theory and cryptography continue to be composed together, and show that the composition of these two fields yield new constructions in the areas of Secure Computation Protocols, Succinct Interactive Arguments, and Locally Decodable Codes. This dissertation is a continuation of several decades of research in composing coding theory and cryptography; examples include secret sharing, encryption schemes, randomness extraction, pseudo-random number generation, and the PCP theorem, to name a few. In Part I of this dissertation, we examine the composition of coding theory with cryptography, explicitly and implicitly. On the explicit side, we construct a new family of linear error-correcting codes, based on algebraic geometric codes, and use this family to construct new correlation extractors (Ishai et al., FOCS 2009). Correlation extractors are two-party secure computation protocols for distilling samples of a leaky correlation (e.g., pre-processed secret shares that have been exposed to side-channel attacks) into secure and fresh shares of another correlation (e.g., shares of oblivious transfer). Our correlation extractors are (nearly) optimal in all parameters. On the implicit side, we use coding theoretic arguments to show the security of succinct interactive arguments (Micali, FOCS 1994). Succinct interactive arguments are a restriction of interactive proofs (Goldwasser, Micali, Rackoff, STOC 1985) for which security only holds against computationally bounded provers (i.e., probabilistic polynomial time), and where the proofs are sub-linear in the size of the statement being proven. Our new succinct interactive arguments are the first public-coin, zero-knowledge arguments with time and space efficient provers: we give two protocols where any NP statement that is verifiable by a time-T space-S RAM program in is provable time O~(T) and space S * polylog(T). In Part II of this dissertation, we examine the composition of cryptography with coding theory, again explicitly and implicitly, focusing specifically on locally decodable codes (Katz and Trevisan, STOC 2000). Locally decodable codes, or LDCs, are error-correcting codes with super-efficient probabilistic decoding procedures that allow for decoding individual symbols of the encoded message, without decoding the entire codeword. On the implicit side, we utilize cryptographic analysis tools to give a conceptually simpler proof of the so-called "Hamming-to-InsDel" compiler (Ostrovsky and Paskin-Cherniavsky, ITS 2015). This compiler transforms any Hamming LDC (i.e., a code that is resilient to bit-flip errors) to another LDC that is resilient to the broad class of insertion-deletion errors, approximately preserving the rate and error-tolerance of the code at the cost of a poly-logarithmic increase in the query complexity. We further extend this compiler to both the private LDC (Ostrovsky, Pandey, and Sahai, ICALP 2007) setting, where the encoder and decoder are assumed to share a secret key unknown to the adversarial channel, and the resource-bounded LDC (Blocki, Kulkarni, and Zhou, ITC 2020) setting, where the adversarial channel is assumed to be resource constrained. On the explicit side, we utilize two cryptographic primitives to give new constructions of alternative notions of LDCs. First, we use cryptographic puzzles (Bitansky et al., ITCS 2016) to construct resource-bounded Hamming LDCs in the standard model without random oracles, answering an open question of Blocki, Kulkarni, and Zhou (ITC 2020); we then naturally extend these LDCs to the InsDel setting via our previously mentioned compiler. Second, we use digital signature schemes to directly construct computationally relaxed LDCs (Blocki et al., ITIT 2021) that are resilient to insertion-deletion errors. Computationally relaxed LDCs allow the decoder to output an extra symbol signifying it does not know the correct output and are only secure against probabilistic polynomial time adversarial channels. To the best of our knowledge, this is the first such LDC (of any type) resilient against insertion-deletion errors that does not rely on the aforementioned compiler.