Paper 2018/293

Privacy Amplification from Non-malleable Codes

Eshan Chattopadhyay and Bhavana Kanukurthi and Sai Lakshmi Bhavana Obbattu and Sruthi Sekar

Abstract

In this paper, we connect two interesting problems in the domain of Information-Theoretic Cryptography: "Non-malleable Codes" and "Privacy Amplification". Non-malleable codes allow for encoding a message in such a manner that any "legal" tampering will either leave the message in the underlying tampered codeword unchanged or unrelated to the original message. In the setting of Privacy Amplification, we have two users that share a weak secret $w$ guaranteed to have some entropy. The goal is to use this secret to agree on a fully hidden, uniformly distributed, key $K$, while communicating on a public channel fully controlled by an adversary. While lot of connections have been known from other gadgets to NMCs, this is one of the first few results to show an application of NMCs to any information-theoretic primitive (other than a natural application to tamper resilient storage). Specifically, we give a general transformation that takes any augmented non-malleable code and builds a privacy amplification protocol. This leads to the following results: (a) Assuming the existence of constant rate two-state augmented non-malleable code with optimal error $2^{-\Omega(\kappa)}$ there exists a $8$-round privacy amplification protocol with optimal entropy loss $O(\log(n) + \kappa)$ and min-entropy requirement $\Omega(\log(n)+ \kappa)$ (where $\kappa$ is the security parameter). In fact, "non-malleable randomness encoders" suffice. (b) Instantiating our construction with the current best known augmented non-malleable code for $2$-split-state family [Li17], we get a $8$-round privacy amplification protocol with entropy loss $O(\log(n)+ \kappa \log (\kappa))$ and min-entropy requirement $\Omega(\log(n) +\kappa\log (\kappa))$.