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: Non-malleable Codes give us the following property: their codewords cannot be tampered into codewords of related messages. Privacy Amplification allows parties to convert their weak shared secret into a fully hidden, uniformly distributed secret key, while communicating on a fully tamperable public channel. In this work, 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 solve the long-standing open problem of building constant round privacy amplification with optimal entropy loss. Instantiating our code with the current best known NMC gives us an $8$-round privacy amplification protocol with entropy loss $O(\log(n)+ \kappa \log (\kappa))$ and min-entropy requirement $\Omega(\log(n) +\kappa\log (\kappa))$, where $\kappa$ 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 our result as an exciting connection between two of the most fascinating and well-studied information theoretic primitives, non-malleable codes and privacy amplification.

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

Date: received 26 Mar 2018, last revised 12 Mar 2019

Contact author: sruthi sekar1 at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20190312:094113 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]