Paper 2010/541

One-time Computable and Uncomputable Functions

Stefan Dziembowski, Tomasz Kazana, and Daniel Wichs


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).

Available format(s)
Publication info
Published elsewhere. Unknown where it was published
Contact author(s)
stefan @ dziembowski net
2010-10-25: received
Short URL
Creative Commons Attribution


      author = {Stefan Dziembowski and Tomasz Kazana and Daniel Wichs},
      title = {One-time Computable and Uncomputable Functions},
      howpublished = {Cryptology ePrint Archive, Paper 2010/541},
      year = {2010},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.