A method for a re-issuance of an attribute-based credential of an issuer of the attribute-based credential for a user may be provided. The user is holding backup values derived from a first credential previously obtained from the issuer, wherein the first credential is built using at least a first value of at least one authentication pair. The method comprises receiving by the issuer from the user a set of values derived from the backup values comprising a second value of the at least one authentication pair, validating by the issuer that the second value is a valid authentication answer with respect to the first value and whether the set of values was derived from a valid first credential, and providing by the issuer a second credential to the user based on the first set of values.