Welcome to the resource topic for 2010/541
Title:
One-time Computable and Uncomputable Functions
Authors: Stefan Dziembowski, Tomasz Kazana, Daniel Wichs
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).
ePrint: https://eprint.iacr.org/2010/541
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .