Motivated by several applications like non-malleable secret sharing schemes, one of the fundamental research directions in the field of non-malleable code construction considers encoding the message into k separate states, where k>=2, such that each state is tampered independently by an arbitrary function. The decoding procedure in this k-split-state model, on the other hand, relies on aggregating the information stored across all the k states. The general goal is to reduce the number of states k, thus, protecting from stronger tampering functions, and, simultaneously, achieve high encoding rate, i.e., the ratio of the message-length to the cumulative size of all the k encoded states.
The ideal result for this line of inquiry will be a 2-split-state non-malleable code with rate (close to) 1/2, the upper-bound to maximum achievable rate. The current state-of-the-art construction, following a sequence of highly influential works guided by this goal, achieves rate 1/ log l (Li, STOC–2017), where l is the length of the encoded message. Our work contributes to this research effort by constructing the first constant-rate (≈ 1/3) non-malleable code in the 3-split-state model, which is only half of the upper-bound on the maximal achievable rate in this model. We start with a construction of the construction of Kanukurthi et al. (TCC--2017) for the 4-split-state model and reduce one state by leveraging a unique characteristic of the (rate-0) non-malleable code for 2-states provided by Aggarwal, Dodis, and Lovett (STOC--2014).
We also study the construction of non-malleable codes in the streaming version of the k-split-state model, i.e., the tampering function of each state encounters the state as a stream, and it tampers each bit of the state based only on the part of the state seen thus far. We show that similar to the general k-split-state model, the maximum achievable rate of a non-malleable code is at most 1 - 1/k in the streaming version as well. We construct the first constant-rate (~ 1/3) non-malleable code in the 2-split-state streaming model, which is only a factor-(3/2) smaller than the upper-bound on the maximum rate.
Category / Keywords: foundations / Non-malleable Codes, Split State, Constant Rate Date: received 24 Oct 2017, last revised 14 Feb 2018 Contact author: hmaji at purdue edu Available format(s): PDF | BibTeX Citation Version: 20180215:032123 (All versions of this report) Short URL: ia.cr/2017/1048