Access Restriction

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

   Open content in new tab
Source: ACM Digital Library