Paper 2018/542

Continuously Non-Malleable Codes in the Split-State Model from Minimal Assumptions

Rafail Ostrovsky, Giuseppe Persiano, Daniele Venturi, and Ivan Visconti


At ICS 2010, Dziembowski, Pietrzak and Wichs introduced the notion of *non-malleable codes*, a weaker form of error-correcting codes guaranteeing that the decoding of a tampered codeword either corresponds to the original message or to an unrelated value. The last few years established non-malleable codes as one of the recently invented cryptographic primitives with the highest impact and potential, with very challenging open problems and applications. In this work, we focus on so-called *continuously* non-malleable codes in the split-state model, as proposed by Faust et al. (TCC 2014), where a codeword is made of two shares and an adaptive adversary makes a polynomial number of attempts in order to tamper the target codeword, where each attempt is allowed to modify the two shares independently (yet arbitrarily). Achieving continuous non-malleability in the split-state model has been so far very hard. Indeed, the only known constructions require strong setup assumptions (i.e., the existence of a common reference string) and strong complexity-theoretic assumptions (i.e., the existence of non-interactive zero-knowledge proofs and collision-resistant hash functions). As our main result, we construct a continuously non-malleable code in the split-state model without setup assumptions, requiring only one-to-one one-way functions (i.e., essentially optimal computational assumptions). Our result introduces several new ideas that make progress towards understanding continuous non-malleability, and shows interesting connections with protocol-design and proof-approach techniques used in other contexts (e.g., look-ahead simulation in zero-knowledge proofs, non-malleable commitments, and leakage resilience).

Available format(s)
Publication info
Published by the IACR in CRYPTO 2018
continuously non-malleable codessplit-state tamperingplain modelminimal assumptions
Contact author(s)
rafail @ cs ucla edu
giuper @ gmail com
venturi @ di uniroma1 it
ivan visconti @ gmail com
2018-06-04: received
Short URL
Creative Commons Attribution


      author = {Rafail Ostrovsky and Giuseppe Persiano and Daniele Venturi and Ivan Visconti},
      title = {Continuously Non-Malleable Codes in the Split-State Model from Minimal Assumptions},
      howpublished = {Cryptology ePrint Archive, Paper 2018/542},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.