Cryptographic Techniques for Verifiable Credentials with Applications to Authentication Procedures

Verifiable credentials (VCs) serve as the digital counterparts to physical credentials, with their security assured through cryptographic methods. The interest on VCs has been renewed by the publication of the European Regulation eIDAS 2.0 that instructs the member states to provide their citizens with a digital wallet (EUDI Wallet) that stores such credentials and that the citizens can use all across the European Union. A great effort has been placed in the definition of common standards that are described in the EUDI Architecture and Reference Framework (ARF), that will be used for the design of the EUDI Wallet. One of the crucial aspects is the identification of the formats and types of VCs supported to be stored in it. The goal of this thesis is twofold: first, to provide a systematic description and analysis of the two VC formats that have been the primary candidates for support by the EUDI Wallet, and second, to propose cryptographic protocols and primitives that facilitate the addition of new features to these credential formats or improve the existing ones. The two VC formats that have been the primary candidates in the development of the EUDI ARF covers (1) the VCs based on hiding commitments that are signed by the issuer using a general purpose digital signature algorithm, and (2) the anonymous credentials generated using the framework of Camenisch and Lysyanskaya, that make use of special digital signature schemes supporting NIZKP that allow one to prove knowledge of a signature created by the issuer. We describe and characterize these formats with a special focus on the cryptographic aspects underlying their design. Then, we introduce a novel cryptographic primitive that can be used to increase the security of the storage of anonymous credentials. We call this primitive multi-holder anonymous credential, and it allows a holder to split an anonymous credential in shares and store them on multiple devices. To present the credential, the holder will need the contribution of a given threshold of the devices. This ensures that as long as an adversary does not compromise enough devices, reaching the threshold, it cannot steal the credential and use it to impersonate the holder. We instantiate a multi-holder anonymous credential that is compatible with the BBS anonymous credential scheme, and we prove its security. Finally, we present a cryptographic commitment scheme whose security is proven in the standard model under assumptions on cryptographic group actions, which are quantum resistant. This commitment scheme, unlike the more efficient commitment based on hashing and salting, supports algorithms and non-interactive zero knowledge proofs to prove predicates about the committed messages, which is an important feature for privacy-preserving applications. To be more specific, when our scheme is used to create VCs, it enables holders to create predicate proofs about the attributes included in their VC, increasing their ability to minimize the disclosure of data.