Non-malleable codes from additive combinatorics

Non-malleable codes provide a useful and meaningful security guarantee in situations where traditional errorcorrection (and even error-detection) is impossible; for example, when the attacker can completely overwrite the encoded message. Informally, a code is non-malleable if the message contained in a modified codeword is either the original message, or a completely unrelated value. Although such codes do not exist if the family of "tampering functions" F is completely unrestricted, they are known to exist for many broad tampering families F . One such natural family is the family of tampering functions in the so called split-state model. Here the message m is encoded into two shares L and R , and the attacker is allowed to arbitrarily tamper with L and R individually . The split-state tampering arises in many realistic applications, such as the design of non-malleable secret sharing schemes , motivating the question of designing efficient non-malleable codes in this model.

Authors

• Divesh Aggarwal
• Yevgeniy Dodis
• Shachar Lovett

Keywords

No keywords are indexed for this paper.