Paper 2017/015

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).

Metadata
Available format(s)
PDF
Publication info
Published by the IACR in PKC 2017
Keywords
non-malleable codestamper-resilient cryptographyleakage-resilient cryptography.
Contact author(s)
danadach @ ece umd edu
mukul @ terpmail umd edu
ariash @ terpmail umd edu
History
2017-01-11: received
Short URL
https://ia.cr/2017/015
License
Creative Commons Attribution
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.