Paper 2017/1097

Non-malleable Randomness Encoders and their Applications

Bhavana Kanukurthi, Sai Lakshmi Bhavana Obbattu, and Sruthi Sekar

Abstract

Non-malleable Codes (NMCs), introduced by Dziembowski, Peitrzak and Wichs (ITCS 2010), serve the purpose of preventing "related tampering" of encoded messages. The most popular tampering model considered is the $2$-split-state model where a codeword consists of 2 states, each of which can be tampered independently. While NMCs in the $2$-split state model provide the strongest security guarantee, despite much research in the area we only know how to build them with poor rate ($\Omega(\frac{1}{logn})$, where $n$ is the codeword length). However, in many applications of NMCs one only needs to be able to encode randomness i.e., security is not required to hold for arbitrary, adversarially chosen messages. For example, in applications of NMCs to tamper-resilient security, the messages that are encoded are typically randomly generated secret keys. To exploit this, in this work, we introduce the notion of "Non-malleable Randomness Encoders" (NMREs) as a relaxation of NMCs in the following sense: NMREs output a random message along with its corresponding non-malleable encoding. Our main result is the construction of a $2$-split state, rate-$\frac{1}{2}$ NMRE. While NMREs are interesting in their own right and can be directly used in applications such as in the construction of tamper-resilient cryptographic primitives, we also show how to use them, in a black-box manner, to build a $3$-split-state (standard) NMCs with rate $\frac{1}{3}$. This improves both the number of states, as well as the rate, of existing constant-rate NMCs.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
Information theoretic cryptographynon-malleablility
Contact author(s)
sruthi sekar1 @ gmail com
bhavana kanukurthi @ gmail com
oslbhavana @ gmail com
History
2017-12-08: revised
2017-11-11: received
See all versions
Short URL
https://ia.cr/2017/1097
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/1097,
      author = {Bhavana Kanukurthi and Sai Lakshmi Bhavana Obbattu and Sruthi Sekar},
      title = {Non-malleable Randomness Encoders and their Applications},
      howpublished = {Cryptology ePrint Archive, Paper 2017/1097},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/1097}},
      url = {https://eprint.iacr.org/2017/1097}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.