International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Local Non-malleable Codes in the Bounded Retrieval Model

Dana Dachman-Soled
Mukul Kulkarni
Aria Shahverdi
DOI: 10.1007/978-3-319-76581-5_10
Search ePrint
Search Google
Conference: PKC 2018
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.The bounded retrieval model (BRM) (cf. Alwen et al. (CRYPTO ’09) and Alwen et al. (EUROCRYPT ’10)) has been studied extensively in the setting of leakage resilience for cryptographic primitives. This threat model assumes that an attacker can learn information about the secret key, subject only to the constraint that the overall amount of leaked information is upper bounded by some value. The goal is then to construct cryptosystems whose secret key length grows with the amount of leakage, but whose runtime (assuming random access to the secret key) is independent of the leakage amount.In this work, we combine the above two notions and construct local non-malleable codes in the split-state model, that are secure against bounded retrieval adversaries. Specifically, given leakage parameter $$\ell $$ℓ, we show how to construct an efficient, 3-split-state, locally decodable and updatable code (with CRS) that is secure against one-time leakage of any polynomial time, 3-split-state leakage function whose output length is at most $$\ell $$ℓ, and one-time tampering via any polynomial-time 3-split-state tampering function. The locality we achieve is polylogarithmic in the security parameter.
  title={Local Non-malleable Codes in the Bounded Retrieval Model},
  booktitle={Public-Key Cryptography – PKC 2018},
  series={Public-Key Cryptography – PKC 2018},
  author={Dana Dachman-Soled and Mukul Kulkarni and Aria Shahverdi},