  Entropic uncertainty relations are quantitative characterizations of
Heisenberg's uncertainty principle, which make use of an entropy measure to
quantify uncertainty. In quantum cryptography, they are often used as
convenient tools in security proofs. 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 arbitrarily large (but specifically chosen) 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 Damg{\aa}rd et al., our new scheme also
offers some security in case the bounded quantum storage assumption fails 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 Damg{\aa}rd et al., on the other hand, completely breaks down
under such an attack.
