Abstract: We study the intrinsic uncertainty of the measurement outcome when measuring an arbitrary n-qubit quantum state in a basis that is chosen at random from some fixed family of bases. We discuss several canonical cases and obtain (tight) lower bounds on the uncertainty of the measurement outcome, where the uncertainty is measured in terms of min-entropy. The bounds are obtained by means of an elegant interplay between probability theory and linear algebra. In the end, we briefly point out how these entropic quantum uncertainty relations can be used for proving the security of certain quantum cryptographic schemes.