Paper 2010/541 Original: eprint.iacr.org/2010/541 ↗

One-time Computable and Uncomputable Functions

Abstract

This paper studies the design of cryptographic schemes that are secure even if implemented on untrusted machines, whose internals can be partially observed/controlled by an adversary. For example, this includes machines that are infected with a software virus. 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).