Paper 2015/1072

Quantum One-Time Memories from Stateless Hardware

Anne Broadbent, Sevag Gharibian, and Hong-Sheng Zhou

Abstract

A central tenet of theoretical cryptography is the study of the minimal assumptions required to implement a given cryptographic primitive. One such primitive is the one-time memory (OTM), introduced by Goldwasser, Kalai, and Rothblum [CRYPTO 2008], which is a classical functionality modeled after a non-interactive 1-out-of-2 oblivious transfer, and which is complete for one-time classical and quantum programs. It is known that secure OTMs do not exist in the standard model in both the classical and quantum settings. Here, we show how to use quantum information, together with the assumption of stateless (i.e., reusable) hardware tokens, to build statistically secure OTMs. This is in sharp contrast with the classical case, where stateless hardware tokens alone cannot yield OTMs. In addition, our scheme is technologically simple. We prove security in the quantum universal composability framework, employing semi-definite programming results of Molina, Vidick and Watrous [TQC 2013] and combinatorial techniques of Pastawski et al. [Proc. Natl. Acad. Sci. 2012].

Note: This paper claimed security against a polynomial number of token queries. However, a subtle, but important bug in the proof has been found by an anonymous referee. We withdraw this paper; a new version is available from the authors, and will be posted as a new ePrint entry.

Metadata
Available format(s)
-- withdrawn --
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Contact author(s)
hongsheng zhou @ gmail com
History
2018-10-09: withdrawn
2015-11-05: received
See all versions
Short URL
https://ia.cr/2015/1072
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.