**Tight Upper and Lower Bounds for Leakage-Resilient, Locally Decodable and Updatable Non-Malleable Codes**

*Dana Dachman-Soled, Mukul Kulkarni, Aria Shahverdi*

**Abstract: **In a recent result, Dachman-Soled et al.~(TCC '15) proposed a new notion called locally decodable and updatable non-malleable codes, which informally, provides the security guarantees of a non-malleable code while also allowing for efficient random access. They also considered locally decodable and updatable non-malleable codes that are leakage-resilient, allowing for adversaries who continually leak information in addition to tampering. Unfortunately, the locality of their construction in the continual setting was Omega(log n), meaning that if the original message size was n, then Omega(log n) positions of the codeword had to be accessed upon each decode and update instruction.

In this work, we ask whether super-constant locality is inherent in this setting. We answer the question affirmatively by showing tight upper and lower bounds. Specifically, in any threat model which allows for a rewind attack-wherein the attacker leaks a small amount of data, waits for the data to be overwritten and then writes the original data back-we show that a locally decodable and updatable non-malleable code with block size Chi in poly(lambda) number of bits requires locality delta(n) in omega(1), where n = poly(lambda) is message length and lambda is security parameter. On the other hand, we re-visit the threat model of Dachman-Soled et al.~(TCC '15)-which indeed allows the adversary to launch a rewind attack-and present a construction of a locally decodable and updatable non-malleable code with block size Chi in Omega(lambda^{1/mu}) number of bits (for constant 0 < mu < 1) with locality delta(n), for any delta(n) in omega(1), and n = poly(lambda).

**Category / Keywords: **non-malleable codes, locally updatable and locally decodable codes, tamper-resilient cryptography, leakage-resilient cryptography.

**Original Publication**** (in the same form): **IACR-PKC-2017

**Date: **received 9 Jan 2017

**Contact author: **danadach at ece umd edu, mukul@terpmail umd edu, ariash@terpmail umd edu

**Available format(s): **PDF | BibTeX Citation

**Version: **20170111:132158 (All versions of this report)

**Short URL: **ia.cr/2017/015

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]