Exploring the Composition of Coding Theory and Cryptography through Secure Computation, Succinct Arguments, and Local Codes

    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.