Uncertainty relations lie at the very core of quantum mechanics, and form the cornerstone of essentially all quantum cryptographic applications. In particular, they play an important role in cryptographic protocols in the bounded-quantum-storage model, where proving the security of all existing protocols ultimately reduces to bounding such relations. Yet, very little is known about such uncertainty relations for more than two measurements. Here, we prove optimal entropic uncertainty relations for anti-commuting binary observables for the Shannon entropy, and nearly optimal relations for the collision entropy. Our results have immediate applications to quantum cryptography.