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

Dana Dachman-Soled, Mukul Kulkarni, and 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).

Available format(s)
Publication info
Keywords
non-malleable codestamper-resilient cryptographyleakage-resilient cryptography.
Contact author(s)
mukul @ terpmail umd edu
ariash @ terpmail umd edu
History
Short URL
https://ia.cr/2017/015

CC BY

BibTeX

@misc{cryptoeprint:2017/015,
author = {Dana Dachman-Soled and Mukul Kulkarni and Aria Shahverdi},
title = {Tight Upper and Lower Bounds for Leakage-Resilient, Locally Decodable and Updatable Non-Malleable Codes},
howpublished = {Cryptology ePrint Archive, Paper 2017/015},
year = {2017},
note = {\url{https://eprint.iacr.org/2017/015}},
url = {https://eprint.iacr.org/2017/015}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.