Paper 2009/399
LeakageResilient Storage
Francesco Davì, Stefan Dziembowski, and Daniele Venturi
Abstract
We study a problem of secure data storage on hardware that may leak information. We introduce a new primitive, that we call {\em leakageresilient storage} (LRS), which is an (unkeyed) scheme for encoding messages, and can be viewed as a generalization of the {\em AllOrNothing Transform} (AONT, Rivest 1997). The standard definition of AONT requires that it should be hard to reconstruct a message $m$ if not all the bits of its encoding $\Encode(m)$ are known. LRS is defined more generally, with respect to a class $\Gamma$ of functions. The security definition of LRS requires that it should be hard to reconstruct $m$ even if some values $g_1(\Encode(m)),\ldots,$ $g_t(\Encode(m))$ are known (where $g_1,\ldots,g_t \in \Gamma$), as long as the total length of $g_1(\Encode(m)),\ldots,g_t(\Encode(m))$ is smaller than some parameter $c$. 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 leakageresilient storage and a theory of the compressibility of NPinstances.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Published elsewhere. Unknown where it was published
 Contact author(s)
 stefan @ dziembowski net
 History
 20100413: last of 2 revisions
 20090815: received
 See all versions
 Short URL
 https://ia.cr/2009/399
 License

CC BY
BibTeX
@misc{cryptoeprint:2009/399, author = {Francesco Davì and Stefan Dziembowski and Daniele Venturi}, title = {LeakageResilient Storage}, howpublished = {Cryptology ePrint Archive, Paper 2009/399}, year = {2009}, note = {\url{https://eprint.iacr.org/2009/399}}, url = {https://eprint.iacr.org/2009/399} }