Cryptology ePrint Archive: Report 2017/1048

Constant-rate Non-malleable Codes in the Split-state Model

Divya Gupta and Hemanta K. Maji and Mingyuan Wang

Abstract: Dziembowski, Pietrzak, and Wichs (ICS–2010) introduced the notion of non-malleable codes as a useful message integrity assurance for scenarios where error-correction or, even, error-detection is impossible. 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. However, if the family of tampering functions is sophisticated enough to include the decoding algorithm itself, then such codes are impossible.

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:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]