Cryptography In the Bounded Quantum-Storage Model
--------------------------------------------------------------
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 and noninteractive and can be
implemented using today's technology. On the technical side, a new
entropic uncertainty relation involving min-entropy is established.