  We analyze uncertainty relations on finite dimensional Hilbert spaces
expressed in terms of classical fidelity, which are stronger then metric
uncertainty relations introduced by Fawzi, Hayden and Sen. We establish
validity of fidelity uncertainty relations for random unitary matrices with
optimal parameters (up to universal constants) which improves upon known
results for the weaker notion of metric uncertainty. This result is then
applied to locking classical information in quantum states and allows to obtain
optimal locking in Hellinger distance, improving upon previous results on
locking in the total variation distance, both by strengthening the metric used
and by improving the dependence on parameters. We also show that general
probabilistic estimates behind the main theorem can be used to prove existence
of data hiding schemes with Bayesian type guarantees. As a byproduct of our
approach we obtain existence of almost Euclidean subspaces of the matrix spaces
$\ell_1^n(\ell_2^m)$ with a better dimension/distortion dependence than allowed
in previously known constructions.
