Paper 2018/293

Privacy Amplification from Non-malleable Codes

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


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.

Available format(s)
Publication info
Preprint. MINOR revision.
Non-malleabilityPrivacy AmplificationInformation-theoretic Key Agreement
Contact author(s)
sruthi sekar1 @ gmail com
2019-03-12: last of 6 revisions
2018-03-28: received
See all versions
Short URL
Creative Commons Attribution


      author = {Eshan Chattopadhyay and Bhavana Kanukurthi and Sai Lakshmi Bhavana Obbattu and Sruthi Sekar},
      title = {Privacy Amplification from Non-malleable Codes},
      howpublished = {Cryptology ePrint Archive, Paper 2018/293},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.