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).
Part of this work was carried out during the tenure of an ERCIM fellowship. This work was partly supported by the IST-3-016004-IP-09 Sensoria project and the KBN grant 4 T11C 042 25. Part of this work was done at the Institute of Mathematics, Polish Academy of Sciences. Current address of the author: Dipartimento di Informatica – Università La Sapienza, Via Salaria 113, 00198 Roma, Italy.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Aumann, Y., Ding, Y.Z., Rabin, M.O.: Everlasting security in the Bounded Storage Model. IEEE Transactions on Information Theory 48(6), 1668–1680 (2002)
Bellare, M., Rogaway, P.: Random oracles are practical: A paradigm for designing efficient protocols. In: ACM Conference on Computer and Communications Security, pp. 62–73 (1993)
Cachin, C., Crepeau, C., Marcil, J.: Oblivious transfer with a memory-bounded receiver. In: 39th Annual Symposium on Foundations of Computer Science, pp. 493–502 (1998)
Cachin, C., Maurer, U.M.: Unconditional security against memory-bounded adversaries. In: Kaliski Jr., B.S. (ed.) CRYPTO 1997. LNCS, vol. 1294, pp. 292–306. Springer, Heidelberg (1997)
Cash, D., Ding, Y.Z., Dodis, Y., Lee, W., Lipton, R., Walfish, S.: Intrusion-resilient authentication in the Limited Communication Model. Cryptology ePrint Archive, Report 2005/409 (2005), http://eprint.iacr.org/
Chor, B., Goldreich, O., Kushilevitz, E., Sudan, M.: Private Information Retrieval. Journal of the ACM 45(6), 965–981 (1998)
Di Crescenzo, G., Lipton, R.J., Walfish, S.: Perfectly Secure Password Protocols in the Bounded Retrieval Model. In: Halevi, S., Rabin, T. (eds.) TCC 2006. LNCS, vol. 3876, pp. 225–244. Springer, Heidelberg (2006)
Di Crescenzo, G., Malkin, T.G., Ostrovsky, R.: Single Database Private Information Retrieval Implies Oblivious Transfer. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 122–138. Springer, Heidelberg (2000)
Dagon, D., Lee, W., Lipton, R.J.: Protecting secret data from insider attacks. In: S. Patrick, A., Yung, M. (eds.) FC 2005. LNCS, vol. 3570, pp. 16–30. Springer, Heidelberg (2005)
Ding, Y.Z., Harnik, D., Rosen, A., Shaltiel, R.: Constant-Round Oblivious Transfer in the Bounded Storage Model. In: Naor, M. (ed.) TCC 2004. LNCS, vol. 2951, pp. 446–472. Springer, Heidelberg (2004)
Dubrov, B., Ishai, Y.: On the randomness complexity of efficient sampling. In: ACM Symposium on Theory of Computing, pp. 711–720 (2006)
Dziembowski, S.: Intrusion-Resilience Via the Bounded-Storage Model. In: Halevi, S., Rabin, T. (eds.) TCC 2006. LNCS, vol. 3876, pp. 207–224. Springer, Heidelberg (2006)
Dziembowski, S.: On Forward-Secure Storage. Cryptology ePrint Archive (2006), http://eprint.iacr.org
Dziembowski, S., Maurer, U.M.: On Generating the Initial Key in the Bounded-Storage Model. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 126–137. Springer, Heidelberg (2004)
Dziembowski, S., Maurer, U.: Optimal randomizer efficiency in the Bounded-Storage Model. Journal of Cryptology 17(1), 5–26 (2004)
Harnik, D., Naor, M.: On the compressibility of NP instances and cryptographic applications. Electronic Colloquium on Computational Complexity, Report TR06-022 (2006)
Harnik, D., Naor, M.: On everlasting security in the hybrid bounded storage model. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006. LNCS, vol. 4052, pp. 192–203. Springer, Heidelberg (2006)
Håstad, J., Impagliazzo, R., Levin, L.A., Luby, M.: A pseudorandom generator from any one-way function. SIAM J. Comput. 28(4), 1364–1396 (1999)
Impagliazzo, R., Rudich, S.: Limits on the provable consequences of one-way permutations. In: ACM Symposium on Theory of Computing, pp. 44–61 (1989)
Kelsey, J., Schneier, B.: Authenticating secure tokens using slow memory access. In: USENIX Workshop on Smart Card Technology, pp. 101–106 (1999)
Kushilevitz, E., Ostrovsky, R.: Replication is not needed: Single database, Computationally-Private Information Retrieval. In: 38th Annual Symposium on Foundations of Computer Science, pp. 364–373 (1997)
Kushilevitz, E., Ostrovsky, R.: One-Way Trapdoor Permutations Are Sufficient for Non-trivial Single-Server Private Information Retrieval. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 104–121. Springer, Heidelberg (2000)
Lu, C.-J.: Encryption against storage-bounded adversaries from on-line strong extractors. Journal of Cryptology 17(1), 27–42 (2004)
Maurer, U.: Conditionally-perfect secrecy and a provably-secure randomized cipher. Journal of Cryptology 5(1), 53–66 (1992)
Moran, T., Shaltiel, R., Ta-Shma, A.: Non-interactive Timestamping in the Bounded Storage Model. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 460–476. Springer, Heidelberg (2004)
Pietrzak, K.: Composition implies adaptive security in minicrypt. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 328–338. Springer, Heidelberg (2006)
Rivest, R.L.: All-or-nothing encryption and the package transform. In: Biham, E. (ed.) FSE 1997. LNCS, vol. 1267, pp. 210–218. Springer, Heidelberg (1997)
Vadhan, S.P.: Constructing locally computable extractors and cryptosystems in the Bounded-Storage Model. Journal of Cryptology 17(1), 43–77 (2004)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Dziembowski, S. (2006). On Forward-Secure Storage. In: Dwork, C. (eds) Advances in Cryptology - CRYPTO 2006. CRYPTO 2006. Lecture Notes in Computer Science, vol 4117. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11818175_15
Download citation
DOI: https://doi.org/10.1007/11818175_15
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-37432-9
Online ISBN: 978-3-540-37433-6
eBook Packages: Computer ScienceComputer Science (R0)