Paper 2005/291

Cryptography In the Bounded Quantum-Storage Model

Ivan Damgård, Serge Fehr, Louis Salvail, and Christian Schaffner

Abstract

We initiate the study of two-party cryptographic primitives with unconditional security, assuming that the adversary's {\em quantum}memory is of bounded size. We show that oblivious transfer and bit commitment can be implemented in this model using protocols where honest parties need no quantum memory, whereas an adversarial player needs quantum memory of size at least $n/2$ in order to break the protocol, where $n$ is the number of qubits transmitted. This is in sharp contrast to the classical bounded-memory model, where we can only tolerate adversaries with memory of size quadratic in honest players' memory size. Our protocols are efficient, non-interactive and can be implemented using today's technology. On the technical side, a new entropic uncertainty relation involving min-entropy is established.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. FOCS 2005
Keywords
quantum cryptographyoblivious transferbit commitmentquantum bounded-storage modeltwo-party computationuncertainty relation
Contact author(s)
chris @ brics dk
History
2005-09-01: received
Short URL
https://ia.cr/2005/291
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2005/291,
      author = {Ivan Damgård and Serge Fehr and Louis Salvail and Christian Schaffner},
      title = {Cryptography In the Bounded Quantum-Storage Model},
      howpublished = {Cryptology ePrint Archive, Paper 2005/291},
      year = {2005},
      note = {\url{https://eprint.iacr.org/2005/291}},
      url = {https://eprint.iacr.org/2005/291}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.