UC San Diego

Despite having evolved as two distinct research areas, cryptography and coding theory have matured in parallel, deeply influencing each other leading to a long and successful intertwined history. This thesis explores further the connection between the two fields by demonstrating how borrowing appropriate tools from coding theory can have significant implications to cryptography. Concretely, we present three results, all motivated by cryptographic applications. First, we prove that CCA- security, the standard security goal for public- key encryption, is implied by Lossy Trapdoor Functions (LTDFs) with minimal lossiness. LTDFs, introduced by Peikert and Waters (STOC 2008), have been extremely successful in cryptography. In a surprising application of LTDFs, Peikert and Waters show how to build CCA-secure encryption generically from LTDFs that lose a (1- 1=[omega](log n)) fraction of their input bits. We drastically lower the lossiness required, showing that any LTDF that loses only a noticeable fraction of a single bit suffices. The key idea behind our result is the use of Reed-Solomon codes to appropriately instantiate a recent CCA-secure construction by Rosen and Segev (TCC 2009). Second, we present powerful and general sample preserving search to decision reductions for the Learning With Errors (LWE) problem, introduced by Regev (STOC 2005), and used to substantially expand the scope of lattice based cryptography. Such reductions are of paramount importance in cryptography, bridging the gap between constructions, which require hard decisional problems, and hardness assumptions, which rely on search problems. Our proof draws upon recently developed techniques that generalize the list-decoding algorithm of Goldreich and Levin (STOC 89) to Hadamard codes over larger alphabets. In our last result, we use Learning Parity with Noise (LPN), a problem closely related to that of decoding random linear codes, to construct a simple and efficient 3-round symmetric authentication protocol that is secure against active attacks. Symmetric authentication has recently attracted widespread interest due to the existence of lightweight protocols amenable to implementation on simple architectures, such as Raid tags. Compared to existing LPN -based protocols, ours achieves a better security- efficiency tradeoff leading to smaller communication complexity and key sizes for the same level of security