With the increasing use of online services, the protection of the privacy of users becomes more and more important. This is particularly critical as authentication and authorization, as realized on the Internet nowadays, typically rely on centralized identity management solutions. Although those are very convenient from a user’s perspective, they are quite intrusive from a privacy perspective and are currently far from implementing the concept of data minimization. Fortunately, cryptography offers exciting primitives such as zero-knowledge proofs and advanced signature schemes to realize various forms of so-called anonymous credentials. Such primitives enable online authentication and authorization with a high level of built-in privacy protection (what we call privacy-preserving authentication). Though these primitives have already been researched for various decades and are well understood in the research community, unfortunately, they lack widespread adoption. In this paper, we look at the problems, what cryptography can do, some deployment examples, and barriers to widespread adoption, which we discuss using the example of the EU Digital Identity Wallet (EUDIW) and the recent discussion and feedback from cryptography experts around this topic. We also briefly comment on the transition to post-quantum cryptography.