International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Guy N. Rothblum

Affiliation: Weizmann

Publications

Year
Venue
Title
2017
CRYPTO
2017
TCC
2017
JOFC
2016
CRYPTO
2015
ASIACRYPT
2014
TCC
2014
JOFC
2013
CRYPTO
2012
CRYPTO
2011
ASIACRYPT
2011
JOFC
2010
TCC
2010
TCC
2010
CRYPTO
2009
TCC
2009
TCC
2008
CRYPTO
2007
TCC
2007
TCC
2006
EPRINT
The Complexity of Online Memory Checking
Moni Naor Guy Rothblum
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.

Program Committees

Eurocrypt 2019
TCC 2017
TCC 2016
Crypto 2013
PKC 2011
TCC 2011