×

One-time computable self-erasing functions. (English) Zbl 1295.94061

Ishai, Yuval (ed.), Theory of cryptography. 8th theory of cryptography conference, TCC 2011, Providence, RI, USA, March 28–30, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-19570-9/pbk). Lecture Notes in Computer Science 6597, 125-143 (2011).
Summary: This paper studies the design of cryptographic schemes that are secure even if implemented on untrusted machines that fall under adversarial control. For example, this includes machines that are infected by a software virus.
We introduce a new cryptographic notion that we call a one-time computable pseudorandom function (PRF), which is a PRF \(F_{K }(\cdot )\) that can be evaluated on at most one input, even by an adversary who controls the device storing the key \(K\), as long as: (1) the adversary cannot “leak” the key \(K\) out of the device completely (this is similar to the assumptions made in the 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 only way to evaluate \(F _{K }(x)\) on such device, is to overwrite part of the key \(K\) during the computation, thus preventing all future evaluations of \(F _{K }(\cdot )\) at any other point \(x^{\prime} \neq x\). We show that this primitive can be used to construct schemes for 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 graphs pebbling problems.
We show that our techniques can also be used to construct another primitive, called uncomputable hash functions, which are hash functions that have a short description but require a large amount of space to compute on any input. We show that this tool can be used to improve the communication complexity of proofs-of-erasure schemes, introduced recently by D. Perito and G. Tsudik [Computer Security – ESORICS 2010, Lect. Notes Comput. Sci. 6345, 643–662 (2010; Zbl 1295.94128)).
For the entire collection see [Zbl 1213.94005].

MSC:

94A60 Cryptography

Citations:

Zbl 1295.94128
Full Text: DOI