Methods, systems, and computer programs for validating a batch of implicit certificates are described. Data for a batch of implicit certificates are received and validated. In some aspect, the data include key-pair-validation values that can be used to validate the public and private keys for each implicit certificate. For example, the key-pair-validation values can include a private key, a public key reconstruction value, a public key of the certificate authority, and a hash of the implicit certificate. The key-pair-validation values are either valid or invalid according to a key-pair-validation function. In some cases, modification values are obtained independent of the key-pair-validation values, and the modification values are combined with the key-pair-validation values in a batch-validation function. The batch-validation function is evaluated for the batch of implicit certificates. Evaluating the batch-validation function identifies whether the key-pair-validation data include key-pair-validation values that are invalid according to the key-pair-validation function.