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 locally decodable and updatable non-malleable codes in the split-state model, that are secure against bounded retrieval adversaries. Specifically, given leakage parameter l, 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 l, and one-time tampering via any polynomial-time 3-split-state tampering function. The locality we achieve is polylogarithmic in the security parameter.Category / Keywords: bounded retrieval model, non-malleable codes, locally decodable codes, tamper-resilient cryptography, leakage-resilient cryptography. Date: received 4 Apr 2017, last revised 4 Apr 2017 Contact author: mukul at terpmail umd edu, danadach at ece umd edu, ariash at terpmail umd edu Available format(s): PDF | BibTeX Citation Version: 20170410:133900 (All versions of this report) Short URL: ia.cr/2017/303 Discussion forum: Show discussion | Start new discussion