Cryptographic primitives such as oblivious transfer and bit commitment
are impossible to realize if unconditional security is required
against adversaries who are unbounded in running time and memory size.
Therefore, it is a great challenge to come up with restrictions on the
adversary's capabilities such that on one hand interesting
cryptographic primitives become possible, but on the other hand the
model is still realistic and as close to practice as possible.
The bounded-quantum-storage model is a prime example of such a
cryptographic model. In this thesis, we initiate the study of
cryptographic primitives with unconditional security under the sole
assumption that the adversary's quantum memory is of bounded size.
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 to store at least a large fraction of the
total number of transmitted qubits in order to break the protocol.
This is in sharp contrast to the classical bounded-memory model, where
we can only tolerate adversaries with memory of size polynomially
larger than the honest players' memory size.
On the practical side, our protocols are efficient, non-interactive
and can be adapted to cope with various kinds of noise in the
transmission. In fact, they can be implemented using today's
technology.
On the theoretical side, new entropic uncertainty relations involving
min-entropy are established and used to prove the security of
protocols in the bounded-quantum-storage model according to new strong
security definitions. The uncertainty relations lower bound the
min-entropy of the encoding used in most quantum-cryptographic
protocols and therefore contribute to the understanding of the quantum
effects which these protocols are based upon. The most direct way to
make use of this lower bound is by assuming a quantum-memory bound on
the adversary. For instance, in the realistic setting of Quantum Key
Distribution (QKD) against quantum-memory-bounded eavesdroppers, the
uncertainty relation allows to prove the security of QKD protocols
while tolerating considerably higher error rates compared to the
standard model with unbounded adversaries.
In addition, though not directly related to the
bounded-quantum-storage model, a classical result about
unconditionally secure 1-out-of-2 Oblivious Transfer (1-2 OT) is
obtained. It is pointed out that the standard security requirement for
1-2 OT of bits, namely that the receiver only learns one of the bits
sent, holds if and only if the receiver has no information on the XOR
of the two bits. This result generalizes to 1-2 OT of strings, in
which case the security can be characterized in terms of binary linear
functions. More precisely, it is shown that the receiver learns only
one of the two strings sent, if and only if he has no information on
the result of applying any binary linear function which non-trivially
depends on both inputs to the two strings. This result not only gives
new insight into the nature of \OT, but it in particular provides a
powerful tool for analyzing 1-2 OT protocols. With this
characterization at hand, the reducibility of 1-2 OT of strings to a
wide range of weaker primitives follows by a very simple argument.