CryptoDB
Upper and Lower Bounds for Continuous Non-Malleable Codes
| Authors: | |
|---|---|
| Download: | |
| Conference: | PKC 2019 |
| 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 a continuous way instead of one-time tampering. They also showed that CNMC with information theoretic security cannot be constructed in the 2-split-state tampering model, and presented a construction in the common reference string (CRS) model from 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. 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 note that in a recent work, Ostrovsky et al. (CRYPTO’18) considered the construction of a relaxed notion of 2-split-state CNMC from minimal assumptions.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. |
BibTeX
@inproceedings{pkc-2019-29292,
title={Upper and Lower Bounds for Continuous Non-Malleable Codes},
booktitle={Public-Key Cryptography – PKC 2019},
series={Lecture Notes in Computer Science},
publisher={Springer},
volume={11442},
pages={519-548},
doi={10.1007/978-3-030-17253-4_18},
author={Dana Dachman-Soled and Mukul Kulkarni},
year=2019
}