Paper 2006/091
The Complexity of Online Memory Checking
Moni Naor and Guy Rothblum
Abstract
Suppose you want to store a large file on a remote and unreliable server. You would like to verify that your file has not been corrupted, so you store a small private (randomized)``fingerprint'' of the file on your own computer. This is the setting for the well-studied authentication problem, and the size of the required private fingerprint is well understood. We study the problem of sub-linear authentication: suppose you would like to encode and store your file in a way that allows you to verify that it has not been corrupted, but without reading all of it. If you only want to read t bits of the file, how large does the size s of the fingerprint need to be? We define this problem formally, and show a tight lower bound on the relationship between s and t when the adversary is not computationally bounded, namely: s x t= Omega(n) where n is the file size. This is an easier case of the online memory checking problem, introduced by Blum, Evans, Gemmel, Kannan and Naor in 1991, and hence the same (tight) lower bound applies also to this problem. It was previously shown that when the adversary is not computationally bounded, under the assumption that one-way functions exist, it is possible to construct much better online memory checkers and sub-linear authentication schemes. We show that the existence of one-way functions is also a necessary condition: even slightly breaking the s x t= Omega(n) lower bound in a computational setting implies the existence of one-way functions.
Metadata
- Available format(s)
-
PDF PS
- Category
- Foundations
- Publication info
- Published elsewhere. Unknown where it was published
- Keywords
- memory checkingone-way functionauthentication
- Contact author(s)
- rothblum @ csail mit edu
- History
- 2006-03-09: received
- Short URL
- https://ia.cr/2006/091
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2006/091, author = {Moni Naor and Guy Rothblum}, title = {The Complexity of Online Memory Checking}, howpublished = {Cryptology {ePrint} Archive, Paper 2006/091}, year = {2006}, url = {https://eprint.iacr.org/2006/091} }