With the COVID-19 pandemic entering a second phase and vaccination strategies being applied by countries and governments worldwide, there is an increasing expectation by people to return to normal life. There is currently a debate about immunity passports, privacy, and the enablement of individuals to safely enter everyday social life, workplace, and travel. Such digital immunity passports and vaccination certificates should meet people's expectations for privacy while enabling them to present to 3rd party verifiers tamper-evident credentials. This paper provides a comprehensive answer to the technological, ethical and security challenges, by proposing an architecture that provides to individuals, employers, and government agencies, a digital, decentralized, portable, immutable, and non-refutable health status cryptographic proof. It can be used to evaluate the risk of allowing individuals to return to work, travel, and public life activities.