Welcome to the resource topic for 2017/1048
Title:
Non-malleable Codes against Lookahead Tampering
Authors: Divya Gupta, Hemanta K. Maji, Mingyuan Wang
Abstract:There are natural cryptographic applications where an adversary only gets to tamper a high- speed data stream on the fly based on her view so far, namely, the lookahead tampering model. Since the adversary can easily substitute transmitted messages with her messages, it is farfetched to insist on strong guarantees like error-correction or, even, manipulation detection. Dziembowski, Pietrzak, and Wichs (ICS–2010) introduced the notion of non-malleable codes that provide a useful message integrity for such scenarios. Intuitively, a non-malleable code ensures that the tampered codeword encodes the original message or a message that is entirely independent of the original message. Our work studies the following tampering model. We encode a message into k>=1 secret shares, and we transmit each share as a separate stream of data. Adversaries can perform lookahead tampering on each share, albeit, independently. We call this k-lookahead model. First, we show a hardness result for the k-lookahead model. To transmit an l-bit message, the cumulative length of the secret shares must be at least kl/(k-1). This result immediately rules out the possibility of a solution with k = 1. Next, we construct a solution for 2-lookahead model such that the total length of the shares is 3l, which is only 1.5x of the optimal encoding as indicated by our hardness result. Prior work considers stronger model of split-state encoding that creates k>=2 secret shares, but protects against adversaries who perform arbitrary (but independent) tampering on each se- cret share. The size of the secret shares of the most efficient 2-split-state encoding is l*log(l)/loglog(l) (Li, ECCC–2018). Even though k-lookahead is a weaker tampering class, our hardness result matches that of k-split-state tampering by Cheraghchi and Guruswami (TCC–2014). However, our explicit constructions above achieve much higher efficiency in encoding.
ePrint: https://eprint.iacr.org/2017/1048
Talk: https://www.youtube.com/watch?v=UWB7sAAOwck
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .