  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.
