Aarhus University Seal

Cryptography In The Bounded Quantum-Storage Model

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

  • Ivan Bjerre Damgård
  • Louis Salvail, Denmark
  • Christian Schaffner, Denmark
  • Serge Fehr, CWI, Amsterdam, Netherlands
  • Department of Computer Science
We initiate the study of two-party cryptographic primitives with unconditional security, assuming that the adversary's 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.
Original languageEnglish
Title of host publicationProceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science
Number of pages10
Publication year2005
ISBN (print)0-7695-2468-0
Publication statusPublished - 2005
EventIEEE Symposium on Foundations of Computer Science. FOCS '05 - Pittsburgh, PA, United States
Duration: 23 Oct 200525 Oct 2005
Conference number: 46


ConferenceIEEE Symposium on Foundations of Computer Science. FOCS '05
LandUnited States
ByPittsburgh, PA

See relations at Aarhus University Citationformats

ID: 389968