Paper 2015/238

One Time Programs with Limited Memory

Konrad Durnoga, Stefan Dziembowski, Tomasz Kazana, and Michał Zając

Abstract

We reinvestigate a notion of {\em one-time programs} introduced in the CRYPTO 2008 paper by Goldwasser {\it et~al.} A one-time program is a device containing a program $C$, with the property that the program $C$ can be executed on at most one input. Goldwasser {\it et~al.}~show how to implement one-time programs on devices equipped with special hardware gadgets called {\em one-time memory} tokens. We provide an alternative construction that does not rely on the hardware gadgets. Instead, it is based on the following assumptions: (1) the total amount of data that can leak from the device is bounded, and (2) the total memory on the device (available both to the honest user and to the attacker) is also restricted, which is essentially the model used recently by Dziembowski {\it et al.}\ (TCC 2011, CRYPTO 2011) to construct one-time computable {\em pseudorandom} functions and key-evolution schemes.

Metadata
Available format(s)
PDF
Category
Applications
Publication info
Published elsewhere. Springer, Lecture Notes in Computer Science, Vol. 8567
Keywords
one time programyao garbled circuitsrandom oraclegarbling
Contact author(s)
m zajac @ mimuw edu pl
History
2015-03-13: received
Short URL
https://ia.cr/2015/238
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/238,
      author = {Konrad Durnoga and Stefan Dziembowski and Tomasz Kazana and Michał Zając},
      title = {One Time Programs with Limited Memory},
      howpublished = {Cryptology ePrint Archive, Paper 2015/238},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/238}},
      url = {https://eprint.iacr.org/2015/238}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.