We construct an LRS scheme that is secure with respect to $\Gamma$ being a set of functions that can depend only on some restricted part of the memory. More precisely: we assume that the memory is divided in $2$ parts, and the functions in $\Gamma$ can be just applied to one of these parts. We also construct a scheme that is secure if the cardinality of $\Gamma$ is restricted (but still it can be exponential in the length of the encoding). This construction implies security in the case when the set $\Gamma$ consists of functions that are computable by Boolean circuits of a small size.
We also discuss the connection between the problem of constructing leakage-resilient storage and a theory of the compressibility of NP-instances.Category / Keywords: foundations / Date: received 13 Aug 2009, last revised 13 Apr 2010 Contact author: stefan at dziembowski net Available formats: PDF | BibTeX Citation Version: 20100413:095323 (All versions of this report) Discussion forum: Show discussion | Start new discussion