×

Leakage-resilient storage. (English) Zbl 1285.94053

Garay, Juan A. (ed.) et al., Security and cryptography for networks. 7th international conference, SCN 2010, Amalfi, Italy, September 13–15, 2010. Proceedings. Berlin: Springer (ISBN 978-3-642-15316-7/pbk). Lecture Notes in Computer Science 6280, 121-137 (2010).
Summary: We study a problem of secure data storage on hardware that may leak information. We introduce a new primitive, that we call leakage-resilient storage (LRS), which is an (unkeyed) scheme for encoding messages, and can be viewed as a generalization of the All-Or-Nothing 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)),\dots , g _{t }(Encode(m))\) are known (where \(g _{1},\dots ,g _{t } \in \Gamma \)), as long as the total length of \(g _{1}(Encode(m)),\dots ,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 leakage-resilient storage and a theory of the compressibility of NP-instances.
For the entire collection see [Zbl 1195.68003].

MSC:

94A60 Cryptography
68P25 Data encryption (aspects in computer science)
PDFBibTeX XMLCite
Full Text: DOI