International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Cryptography In the Bounded Quantum-Storage Model

Ivan Damgård
Serge Fehr
Louis Salvail
Christian Schaffner
Search ePrint
Search Google
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.
  title={Cryptography In the Bounded Quantum-Storage Model},
  booktitle={IACR Eprint archive},
  keywords={cryptographic protocols / quantum cryptography, oblivious transfer, bit commitment, quantum bounded-storage model, two-party computation, uncertainty relation},
  note={FOCS 2005 13025 received 30 Aug 2005},
  author={Ivan Damgård and Serge Fehr and Louis Salvail and Christian Schaffner},