Stefan Dziembowski
On Forward-Secure Storage
Advances in Cryptology - CRYPTO '06, Lecture Notes in Computer Science, Springer-Verlag, August 2006
Abstract We study a problem of secure data storage in a recently introduced Limited Communication Model. We propose a new cryptographic primitive that we call a Forward-Secure Storage (FSS). This primitive is a special kind of an encryption scheme, which produces huge (5 GB, say) ciphertexts, even from small plaintexts, and has the following non-standard security property. Suppose an adversary gets access to a ciphertext C = E(K,M) and he is allowed to compute any function h of C, with the restriction that |h(C)| ≪|C| (say: |h(C)| = 1 GB). We require that h(C) should give the adversary no information about M, even if he later learns K.
Available files: [ PDF] [BibTeX] [Slides-PPT]
On Forward-Secure Storage
Advances in Cryptology - CRYPTO '06, Lecture Notes in Computer Science, Springer-Verlag, August 2006
Abstract We study a problem of secure data storage in a recently introduced Limited Communication Model. We propose a new cryptographic primitive that we call a Forward-Secure Storage (FSS). This primitive is a special kind of an encryption scheme, which produces huge (5 GB, say) ciphertexts, even from small plaintexts, and has the following non-standard security property. Suppose an adversary gets access to a ciphertext C = E(K,M) and he is allowed to compute any function h of C, with the restriction that |h(C)| ≪|C| (say: |h(C)| = 1 GB). We require that h(C) should give the adversary no information about M, even if he later learns K.
A practical application of this concept is as
follows. Suppose a ciphertext C is stored on a machine on which
an adversary can install a virus. In many cases it is completely
infeasible for the virus to retrieve 1 GB of data from the infected
machine. So if the adversary (at some point later) learns K,
then M remains secret.
We
provide a formal definition of the FSS, propose some FSS schemes, and
show that FSS can be composed sequentially in a secure way. We also
show connections of the FSS to the theory of compressibility of
NP-instances (recently developed by Harnik and Naor).
Available files: [ PDF] [BibTeX] [Slides-PPT]