A method for verifying digital signatures in the presence of root key rollover includes issuing a cross-certificate to a rekeyed root certificate, validating the cross-certificate and the rekeyed root certificate with respect to an original trusted root certificate, and validating a digital media signature using the cross-certificate and the rekeyed root certificate. The method may also include adding the rekeyed root certificate to an end user's trusted root certificate store. The digital media signature validated via the method may correspond to a program signature. Validating the cross-certificate and the rekeyed root certificate may include verifying certificates within a program's certificate chain. A computer program product and a computer system corresponding to the method are also disclosed.