Cryptology ePrint Archive: Report 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))$.

Category / Keywords: foundations / Non-malleability, Privacy Amplification, Information-theoretic Key Agreement

Date: received 26 Mar 2018, last revised 9 Jun 2018

Contact author: sruthi sekar1 at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20180609:214136 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]