International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Interactive Non-malleable Codes

Nils Fleischhacker
Vipul Goyal
Abhishek Jain
Anat Paskin-Cherniavsky
Slava Radune
DOI: 10.1007/978-3-030-36033-7_9
Search ePrint
Search Google
Abstract: Non-malleable codes (NMC) introduced by Dziembowski et al. [ICS’10] allow one to encode “passive” data in such a manner that when a codeword is tampered, the original data either remains completely intact or is essentially destroyed.In this work, we initiate the study of interactive non-malleable codes (INMCs) that allow for encoding “active communication” rather than passive data. An INMC allows two parties to engage in an interactive protocol such that an adversary who is able to tamper with the protocol messages either leaves the original transcript intact (i.e., the parties are able to reconstruct the original transcript) or the transcript is completely destroyed and replaced with an unrelated one.We formalize a tampering model for interactive protocols and put forward the notion of INMCs. Since constructing INMCs for general adversaries is impossible (as in the case of non-malleable codes), we construct INMCs for several specific classes of tampering functions. These include bounded state, split state, and fragmented sliding window tampering functions. We also obtain lower bounds for threshold tampering functions via a connection to interactive coding. All of our results are unconditional.
  title={Interactive Non-malleable Codes},
  booktitle={Theory of Cryptography},
  series={Lecture Notes in Computer Science},
  author={Nils Fleischhacker and Vipul Goyal and Abhishek Jain and Anat Paskin-Cherniavsky and Slava Radune},