Stefan Dziembowski
A Lower Bound on the Key Length of Information-Theoretic Forward-Secure Storage Schemes
The 4th International Conference on Information Theoretic Security, 2009
Abstract Forward-Secure Storage (FSS) was introduced by Dziembowski (CRYPTO 2006). Informally, FSS is an encryption scheme (Encr,Decr) that has the following non-standard property: even if the adversary learns the value of some function h of the ciphertext C = Encr(K,M), he should have essentially no information on the corresponding plaintext M, even if he knows the key K. The only restriction is that h is input-shrinking, i.e. |h(R)| < σ, where σ is some parameter such that σ < |C|.
We study the problem of minimizing the length of the secret key in the IT-secure FSS, and we establish an almost optimal lower bound on the length of the secret key. The secret key of the FSS scheme of Dziembowski has length |M|+O(log σ).We show that in every FSS the secret key needs to have length at least |M| + log_2 σ - O(log_2 log_2 σ).
Available files: [ PDF]
A Lower Bound on the Key Length of Information-Theoretic Forward-Secure Storage Schemes
The 4th International Conference on Information Theoretic Security, 2009
Abstract Forward-Secure Storage (FSS) was introduced by Dziembowski (CRYPTO 2006). Informally, FSS is an encryption scheme (Encr,Decr) that has the following non-standard property: even if the adversary learns the value of some function h of the ciphertext C = Encr(K,M), he should have essentially no information on the corresponding plaintext M, even if he knows the key K. The only restriction is that h is input-shrinking, i.e. |h(R)| < σ, where σ is some parameter such that σ < |C|.
We study the problem of minimizing the length of the secret key in the IT-secure FSS, and we establish an almost optimal lower bound on the length of the secret key. The secret key of the FSS scheme of Dziembowski has length |M|+O(log σ).We show that in every FSS the secret key needs to have length at least |M| + log_2 σ - O(log_2 log_2 σ).
Available files: [ PDF]