Entropic uncertainty relations are quantitative characterizations of
Heisenberg’s uncertainty principle, which make use of an entropy
measure to quantify uncertainty. We propose a new entropic uncertainty
relation. It is the first such uncertainty relation that lower bounds
the uncertainty in the measurement outcome for all but one choice for
the measurement from an arbitrary (and in particular an arbitrarily
large) set of possible measurements, and, at the same time, uses the
min-entropy as entropy measure, rather than the Shannon entropy. This
makes it especially suited for quantum cryptography.  As application,
we propose a new quantum identification scheme in the
bounded-quantum-storage model. It makes use of our new uncertainty
relation at the core of its security proof. In contrast to the
original quantum identification scheme proposed by Damgaard et al.,
our new scheme also offers some security in case the
bounded-quantum-storage assumption fails to hold. Specifically, our
scheme remains secure against an adversary that has unbounded storage
capabilities but is restricted to (non-adaptive) single-qubit
operations. The scheme by Damgaard et al., on the other hand,
completely breaks down under such an attack.