Constant-rate Non-malleable Codes and their Applications

Abstract

Non-malleable codes(NMC) introduced by Dziembowski, Pietrzak and Wichs in ITCS 2010, provide powerful security guarantees where error-correcting codes can not provide any guarantee: a decoding of tampered codeword is either the same or completely independent of the underlying message. One of the most important families of tampering functions is the t-splitstate family, where, the adversary tampers each of the t blocks (called state) of a codeword, independently. In this thesis, we construct the first explicit constant-rate and constant-state non-malleable code. In particular, we construct an efficient non-malleable code in the t-splitstate model, for t = 4, that achieves a constant rate of 1 3+ζ , for any constant ζ > 0 and error 2 −Ω(`/logc+1`) , where ` is the length of the message and c > 0 is an arbitrary constant. We then focus on the fascinating problem of privacy amplification introduced by Bennett et.al in 1988. A privacy amplification(PA) protocol allows two parties, Alice and Bob, who a-priori share a weak secret w, to agree on a uniform secret key, in the presence of a computationally unbounded adversary Eve. Specifically, we show how to construct a constant round privacy amplification protocol from any augmented split-state non-malleable code. Existentially, this gives us another primitive (in addition to optimal non-malleable extractors) whose optimal construction would result in a privacy amplification protocol with optimal entropy loss and min-entropy requirement. Instantiating our code with the NMC due to Li (STOC 2017), gives us an 8-round privacy amplification protocol with entropy loss O(log(n) +κ log(κ)) and min-entropy requirement Ω(log(n) + κ log(κ)), where κ is the security parameter and n is the length of the shared weak secret. In fact, for our result, even the weaker primitive of Non-malleable Randomness Encoders suffice. We view this result as an exciting connection between two of the most fascinating and well-studied information theoretic primitives, non-malleable codes and privacy amplification.