We introduce a new cryptographic notion that we call a {\em one-time computable pseudorandom function (PRF)}, which is a PRF $F_K(\cdot)$ that can be evaluated \emph{at most once} on a machine which stores the (long) key $K$, as long as: (1) the adversary cannot retrieve the key $K$ out of the machine completely (this is similar to the assumptions made in the so-called {\em Bounded-Retrieval Model}), and (2) the local read/write memory of the machine is restricted, and not too much larger than the size of $K$. In particular, the \emph{only way} to evaluate $F_K(x)$ on such device, is to overwrite part of the key $K$, preventing all future evaluations of $F_K(\cdot)$ at any other point $x' \neq x$. We show that this primitive can be used to construct schemes for \emph{password protected storage} that are secure against dictionary attacks, even by a virus that infects the machine. Our constructions rely on the random-oracle model, and lower-bounds for {\em graphs pebbling} problems.
We show that our techniques can also be used to construct another primitive, that we call {\em uncomputable hash functions}, which are hash funcitons that cannot be computed if the local storage has some restricted size $s$, but {\em can} be computed if they are given slightly more storage than $s$. We show that this tool can be used to improve the communication complexity of {\em proofs-of-erasure} schemes, introduced recently by Perito and Tsudik (ESORICS 2010).
Category / Keywords: foundations / Date: received 21 Oct 2010 Contact author: stefan at dziembowski net Available format(s): PDF | BibTeX Citation Version: 20101025:151111 (All versions of this report) Short URL: ia.cr/2010/541 Discussion forum: Show discussion | Start new discussion