Cryptology ePrint Archive: Report 2018/517

Upper and Lower Bounds for Continuous Non-Malleable Codes

Dana Dachman-Soled and Mukul Kulkarni

Abstract: Recently, Faust et al. (TCC'14) introduced the notion of continuous non-malleable codes (CNMC), which provides stronger security guarantees than standard non-malleable codes, by allowing an adversary to tamper with the codeword in continuous way instead of one-time tampering. They also showed that CNMC with information theoretic security cannot be constructed in 2-split-state tampering model, and presented a construction of the same in CRS (common reference string) model using collision-resistant hash functions and non-interactive zero-knowledge proofs.

In this work, we ask if it is possible to construct CNMC from weaker assumptions. We answer this question by presenting lower as well as upper bounds. Specifically, we show that it is impossible to construct 2-split-state CNMC, with no CRS, for one-bit messages from any falsifiable assumption, thus establishing the lower bound. We additionally provide an upper bound by constructing 2-split-state CNMC for one-bit messages, assuming only the existence of a family of injective one way functions.

We also present a construction of 4-split-state CNMC for multi-bit messages in CRS model from the same assumptions. Additionally, we present definitions of the following new primitives: (1) One-to-one commitments, and (2) Continuous Non-Malleable Randomness Encoders, which may be of independent interest.

Category / Keywords: foundations / Continuous non-malleable codes, black box impossibility, split-state

Original Publication (with minor differences): IACR-PKC-2019

Date: received 25 May 2018, last revised 30 Jan 2019

Contact author: mukul at terpmail umd edu

Available format(s): PDF | BibTeX Citation

Note: Updated to the full version of PKC 2019 paper.

Version: 20190131:031516 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]