### The complexity of online memory checkingThe complexity of online memory checking

Access Restriction
Subscribed

 Author Naor, Moni ♦ Rothblum, Guy N Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2009 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Memory checking ♦ Authentication Abstract We consider the problem of storing a large file on a remote and unreliable server. To verify that the file has not been corrupted, a user could store a small private (randomized) “fingerprint” on his own computer. This is the setting for the well-studied authentication problem in cryptography, and the required fingerprint size is well understood. We study the problem of sublinear authentication: suppose the user would like to encode and store the file in a way that allows him to verify that it has not been corrupted, but without reading the entire file. If the user only wants to read $\textit{q}$ bits of the file, how large does the size $\textit{s}$ of the private fingerprint need to be? We define this problem formally, and show a tight lower bound on the relationship between $\textit{s}$ and $\textit{q}$ when the adversary is not computationally bounded, namely: $\textit{s}$ × $\textit{q}$ = $Ω(\textit{n}),$ where $\textit{n}$ is the file size. This is an easier case of the online memory checking problem, introduced by Blum et al. [1991], and hence the same (tight) lower bound applies also to that problem. It was previously shown that, when the adversary is computationally bounded, under the assumption that one-way functions exist, it is possible to construct much better online memory checkers. The same is also true for sublinear authentication schemes. We show that the existence of one-way functions is also a necessary condition: even slightly breaking the $\textit{s}$ × $\textit{q}$ = $Ω(\textit{n})$ lower bound in a computational setting implies the existence of one-way functions. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2009-02-03 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 56 Issue Number 1 Page Count 46 Starting Page 1 Ending Page 46

#### Open content in new tab

Source: ACM Digital Library