Cryptography In the Bounded Quantum-Storage Model
--------------------------------------------------------------
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.