Abstract
We consider the problem of memory checking, where a user wants to maintain a large database on a remote server but has only limited local storage. The user wants to use the small (but trusted and secret) local storage to detect faults in the large (but public and untrusted) remote storage. A memory checker receives from the user store and retrieve operations to the large database. The checker makes its own requests to the (untrusted) remote storage and receives answers to these requests. It then uses these responses, together with its small private and reliable local memory, to ascertain that all requests were answered correctly, or to report faults in the remote storage (the public memory).
A fruitful line of research investigates the complexity of memory checking in terms of the number of queries the checker issues per user request (query complexity) and the size of the reliable local memory (space complexity). Blum et al., who first formalized the question, distinguished between online checkers (that report faults as soon as they occur) and offline checkers (that report faults only at the end of a long sequence of operations). In this work we revisit the question of memory checking, asking how efficient can memory checking be?
For online checkers, Blum et al. provided a checker with logarithmic query complexity in n, the database size. Our main result is a lower bound: we show that for checkers that access the remote storage in a deterministic and non-adaptive manner (as do all known memory checkers), their query complexity must be at least Ω(logn /loglogn). To cope with this negative result, we show how to trade off the read and write complexity of online memory checkers: for any desired logarithm base d, we construct an online checker where either reading or writing is inexpensive and has query complexity O(log d n). The price for this is that the other operation (write or read respectively) has query complexity O(d ·log d n). Finally, if even this performance is unacceptable, offline memory checking may be an inexpensive alternative. We provide a scheme with O(1) amortized query complexity, improving Blum et al.’s construction, which only had such performance for long sequences of at least n operations.
The original version of the book was revised: The copyright line was incorrect. The Erratum to the book is available at DOI: 10.1007/978-3-642-00457-5_36
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
Aho, A.V., Hopcroft, J.E., Ullman, J.D.: The Design and Analysis of Computer Algorithms. Addison-Wesley Series in Computer Science and Information Processing. Addison Wesley, Reading (1974)
Ajtai, M.: The invasiveness of off-line memory checking. In: STOC, pp. 504–513 (2002)
Amato, N.M., Loui, M.C.: Checking linked data structures. In: Proceedings of the 24th Annual International Symposium on Fault-Tolerant Computing (FTCS), pp. 164–173 (1994)
Ateniese, G., Burns, R., Curtmola, R., Herring, J., Kissner, L., Peterson, Z., Song, D.: Provable data possession at untrusted stores. Cryptology ePrint Archive, Report 2007/202 (2007)
Bentley, J.: Programming Pearls. ACM, New York (1986)
Blum, M., Evans, W.S., Gemmell, P., Kannan, S., Naor, M.: Checking the correctness of memories. Algorithmica 12(2/3), 225–244 (1994)
Briggs, P., Torczon, L.: An efficient representation for sparse sets. ACM Letters on Programming Languages and Systems 2, 59–69 (1993)
Clarke, D.E., Suh, G.E., Gassend, B., Sudan, A., van Dijk, M., Devadas, S.: Towards constant bandwidth overhead integrity checking of untrusted data. In: IEEE Symposium on Security and Privacy, pp. 139–153 (2005)
Cox, R.: http://research.swtch.com/2008/03/using-uninitialized-memory-for-fun-and.html
Goldreich, O.: The Foundations of Cryptography, vol. 1. Cambridge University Press, Cambridge (2001)
Goldreich, O.: The Foundations of Cryptography, vol. 2. Cambridge University Press, Cambridge (2004)
Goldreich, O., Goldwasser, S., Micali, S.: How to construct pseudorandom functions. Journal of the ACM 33(2), 792–807 (1986)
Juels, A., Kaliski, B.: Pors: proofs of retrievability for large files. In: CCS 2007: Proceedings of the 14th ACM conference on Computer and communications security, pp. 584–597. ACM, New York (2007)
Naor, J., Naor, M.: Small-bias probability spaces: Efficient constructions and applications. SIAM J. Comput. 22(4), 838–856 (1993)
Naor, M., Rothblum, G.N.: The complexity of online memory checking. In: FOCS, pp. 573–584 (2005)
Oprea, A., Reiter, M.K.: Integrity checking in cryptographic file systems with constant trusted storage. In: USENIX Security Symposium (2007)
Shacham, H., Waters, B.: Compact proofs of retrievability. In: Pieprzyk, J. (ed.) ASIACRYPT 2008. LNCS, vol. 5350, pp. 90–107. Springer, Heidelberg (2008)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Dwork, C., Naor, M., Rothblum, G.N., Vaikuntanathan, V. (2009). How Efficient Can Memory Checking Be?. In: Reingold, O. (eds) Theory of Cryptography. TCC 2009. Lecture Notes in Computer Science, vol 5444. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-00457-5_30
Download citation
DOI: https://doi.org/10.1007/978-3-642-00457-5_30
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-00456-8
Online ISBN: 978-3-642-00457-5
eBook Packages: Computer ScienceComputer Science (R0)